#



#



http://www.laurentluce.com/posts/binary-search-tree-library-in-python/comment-page-1/

###

Wikipedia:http://en.wikipedia.org/wiki/Binary_tree

http://zh.wikipedia.org/wiki/%E4%BA%8C%E5%85%83%E6%90%9C%E5%B0%8B%E6%A8%B9



>>

>>1. 
>>2. 
>>3. 
>>4. no duplicate nodes

>>O(log n)multiset

>>O(n),,O(logn),SBT,AVL,.

###python



![](./pics/binarytree1.png)

**Node **

Node

	class Node:
	    """
	    
	    """
	    def __init__(self, data):
	        """
	        
	
	        """
	        self.left = None
	        self.right = None
	        self.data = data

8None

    root = Node(8)



![](./pics/binarytree2.png)

****



    def insert(self, data):
        """
        
        """
        if data < self.data:
            if self.left is None:
                self.left = Node(data)
            else:
                self.left.insert(data)
        elif data > self.data:
            if self.right is None:
                self.right = Node(data)
            else:
                self.right.insert(data)



    root.insert(3)
    root.insert(10)
    root.insert(1)

3,

- rootinsert()data=3
- 3838None

10,

- data=10
- 108,None,

1,

- data=1
- 18,
- 3,insert()13,13None



![](./pics/binarytree3.png)



    root.insert(6)
    root.insert(4)
    root.insert(7)
    root.insert(14)
    root.insert(13)



![](./pics/binarytree4.png)

****

None

    def lookup(self, data, parent=None):
        """
        
        """
        if data < self.data:
            if self.left is None:
                return None, None
            return self.left.lookup(data, self)
        elif data > self.data:
            if self.right is None:
                return None, None
            return self.right.lookup(data, self)
        else:
            return self, parent

6

    node, parent = root.lookup(6)

lookup()

1. lookup()data=6,parent=None
2. data=68
3. :data=6,parent=8,lookup()
4. data=63
5. 3data=6,parent=3,lookup()
6. 6,3

****



    def delete(self, data):
        """
        
        """
        node, parent = self.lookup(data)        #
        if node is not None:
            children_count = node.children_count()      #
            if children_count == 0:
                # 
                if parent.left is node:
                    parent.left = None
                else:
                    parent.right = None
                del node
            elif children_count == 1:
                # )
                if node.left:
                    n = node.left
                else:
                    n = node.right
                if parent:
                    if parent.left is node:
                        parent.left = n
                    else:
                        parent.right = n
                del node
            else:
                # 
                parent = node
                successor = node.right
                while successor.left:
                    parent = successor
                    successor = successor.left
                node.data = successor.data
                if parent.left == successor:
                    parent.left = successor.right
                else:
                    parent.right = successor.right



- 
- 
- 



    def children_count(self):
        """
        
        """
        cnt = 0
        if self.left:
            cnt += 1
        if self.right:
            cnt += 1
        return cnt

1131

    root.delete(1)

![](./pics/binarytree5.png)

2141013,13

    root.delete(14)

![](./pics/binarytree6.png)

3364,7successor336463
    
    root.delete(3)

![](./pics/binarytree7.png)

****

False

    def compare_trees(self, node):
        """
        
        """
        if node is None:
            return False
        if self.data != node.data:
            return False
        res = True
        if self.left is None:
            if node.left:
                return False
        else:
            res = self.left.compare_trees(node.left)
        if res is False:
            return False
        if self.right is None:
            if node.right:
                return False
        else:
            res = self.right.compare_trees(node.right)
        return res

tree(3,8,10)tree(3,8,11)

    #root2 tree(3,8,11)
    #root tree(3,8,10)
    root.compare_trees(root2)



1. rootcompare_trees()
2. rootcompare_trees()
3. true
4. False

****



    def print_tree(self):
        """
        
        """
        if self.left:
            self.left.print_tree()
        print self.data,
        if self.right:
            self.right.print_tree()



    root.print_tree()

 1, 3, 4, 6, 7, 8, 10, 13, 14

****

yield

    def tree_data(self):
        """
        
        """
        stack = []
        node = self
        while stack or node: 
            if node:
                stack.append(node)
                node = node.left
            else: 
                node = stack.pop()
                yield node.data
                node = node.right



    for data in root.tree_data():
        print data

![](./pics/binarytree1.png)