算法：二叉搜索树的两种实现

2020-12-18 12:36:03 编辑 2 阅读量:429

二叉搜索树的python实现如下：

方式一：节点中不包含父节点信息

```python
# coding:utf-8

class Node(object):
    def __init__(self, data=None, left=None, right=None):
        self.data = data
        self.left = left
        self.right = right
        
class BinarySearchTree(object):
    def __init__(self, datalist=None):
        self.root = Node()
        if datalist:
            self.create(datalist)
        
    def create(self, datalist):
        for data in datalist:
            self.insert(data)
        return self.root
            
    def insert(self, data):
        if self.root.data is None:
            self.root = Node(data)
            return self.root
        current = self.root
        while current:
            if data == current.data:
                raise ValueError('Ther value to insert is already in the search tree') 
            father = current
            if data < current.data:
                current = current.left
            else:
                current = current.right
        if data < father.data:
            father.left = Node(data)
        else:
            father.right = Node(data)
        return self.root
        
    def search(self, data):
        if data is None:
            return False
        if self.root is None:
            return False
        current = self.root
        while current:
            if data == current.data:
                return current
            elif data < current.data:
                current = current.left
            else:
                current = current.right
        return False
        
    def _min(self, node):
        if not node:
            return False
        current = node
        while current.left:
            current = current.left
        return current
        # while current:
            # minpoint = current.left
            # current = minpoint
        # return minpoint
        
    def min(self):
        return self._min(self.root)
        
    def _max(self, node):
        if not node:
            return False
        current = node
        while current.right:
            current = current.right
        return current
        
    def max(self):
        return self._max(self.root)
        
    def delete(self, data):
        def delete_no_child(current, father):
            if father:
                if current.data < father.data:
                    father.left = None
                else:
                    father.right = None
            else:
                current.data = None
                
        def delete_one_child(current, father):
            if father:
                # 仅有右子树
                if current.right:
                    if current.data < father.data:
                        father.left = current.right
                    else:
                        father.right = current.right
                # 仅有左子树
                elif current.left:
                    if current.data < father.data:
                        father.left = current.left
                    else:
                        father.right = current.left
            else:
                if current.right:
                    next_point = current.right
                if current.left:
                    next_point = current.left
                current.data = next_point.data
                current.left = next_point.left
                current.right = next_point.right
                    
        def delete_two_child(current, father):
            # 左、右子树均存在,需要找到右子树的最小值的节点
            minpoint = current.right
            minpoint_father = current
            while minpoint.left:
                minpoint_father = minpoint
                minpoint = minpoint.left
            # minpoint肯定无左子树,有可能有右子树,当它是父节点的左子树时，需要处理它的右子树
            if minpoint.right and minpoint_father.left == minpoint:
                minpoint_father.left = minpoint.right
                    
            if father:
                if current.data < father.data:
                    father.left = minpoint
                else:
                    father.right = minpoint
                minpoint.right = minpoint_father
            else:
                current.data = minpoint.data
                current.right = minpoint.right
            
        def _delete(current, father):
            # 无子节点，直接删除该节点即可
            if not current.left and not current.right:
                delete_no_child(current, father)
            # 左、右子树均存在,需要找到右子树的最小值的节点
            elif current.left and current.right:
                delete_two_child(current, father)
            # 仅有一个子树
            elif current.right or current.left:
                delete_one_child(current, father)
            return True
                
        if data is None:
            return False
        if not self.root:
            return False
            
        current = self.root
        
        if data == current.data:
            return _delete(current, father=None)
        father = current
        # 根节点时
        
        while current:
            if data == current.data:
                return _delete(current, father)
            father = current
            if data < current.data:
                current = current.left
            else:
                current = current.right
        return False
        
    def preorder(self, node):
        if node:
            print node.data
            self.preorder(node.left)
            self.preorder(node.right)
        else:
            return
            
    def inorder(self, node):
        if node:
            self.inorder(node.left)
            print node.data
            self.inorder(node.right)
        else:
            return
            
    def postorder(self, node):
        if node:
            self.postorder(node.left)
            self.postorder(node.right)
            print node.data
        else:
            return
            
    def show(self):
        print 'preorder'
        self.preorder(self.root)
        print 'inorder'
        self.inorder(self.root)
        print 'postorder'
        self.postorder(self.root)

bst = BinarySearchTree([15,5,3,12,10,13,6,7,16,20,18,23])
# preorder: [15,5,3,12,10,6,7,13,16,20,18,23]
# inorder: [3,5,6,7,10,12,13,15,16,18,20,23]
# postorder: [3,7,6,10,13,12,5,18,23,20,16,15]
bst.show()
try:
    bst.insert(18)
except ValueError, e:
    print e
p = bst.search(12)
print p.data
assert(p.left.data == 10)
assert(p.left.left.data == 6)
assert(p.right.data == 13)

bst.insert(19)
p = bst.search(18)
print p.data
assert(p.right.data == 19)

bt.delete(18)
bt.delete(15)
bst.show()
```

方式二：节点中包含父节点信息：

```python
# coding:utf-8

class Node(object):
    def __init__(self, data=None, left=None, right=None, father=None):
        self.data = data
        self.left = left
        self.right = right
        self.father = father
        
class BinarySearchTree(object):
    def __init__(self, datalist=None):
        self.root = Node()
        if datalist:
            self.create(datalist)
        
    def create(self, datalist):
        for data in datalist:
            self.insert(data)
        return self.root
            
    def check_node(self, node):
        if node.data is None:
            raise ValueError("The node shouldn't be None")
    
    def check_data(self, data):
        if data is None:
            raise ValueError("Data shouldn't be None")
            
    def check_root(self, root):
        if root.data is None:
            raise ValueError("The binary tree is empty")
            
    def is_left(self, node):
        if node.data < node.father.data:
            return True
        return False
        
    def is_right(self, node):
        if node.data > nod.father.data:
            return True
        return False
        
    def delete(self, data):
        current = self.search(data)
        if not current.left and not current.right:
            if self.is_left(current):
                current.father.left = None
            else:
                current.father.right = None
                
        elif not current.left:
            if self.is_left(current):
                current.father.left = current.right
            else:
                current.father.right = current.right
        elif not current.right:
            if self.is_left(current):
                current.father.left = current.left
            else:
                current.father.right = current.left
                
        else:
            min_point = self._min(current.right)
            if min_point.father != current:
                if min_point.right:
                    min_point.father.left = min_point.right
                else:
                    min_point.father.left = None
                    current.data = min_point.data
            else:
                current.data = min_point.data
                current.right = min_point.right
            
        
    def insert(self, data):
        if self.root.data is None:
            self.root = Node(data)
            return self.root
        current = self.root
        while current:
            if data == current.data:
                raise ValueError('Ther value to insert is already in the search tree')
            elif data < current.data:
                if current.left:
                    current = current.left
                else:
                    current.left = Node(data, father=current)
                    break
            else:
                if current.right:
                    current = current.right
                else:
                    current.right = Node(data, father=current)
                    break
        return True
        
    def _max(self, node):
        self.check_node(node)
        current = node
        while current.right:
            current = current.right
        return current
        
    def max(self):
        self.check_root(self.root)
        self._max(self.root)
        
    def _min(self, node):
        self.check_node(node)
        current = node
        while current.left:
            current = current.left
        return current
        
    def min(self):
        self.check_root(self.root)
        return self._min(self.root)
        
    def search(self, data):
        self.check_data(data)
        self.check_root(self.root)
        current = self.root
        while current:
            if data == current.data:
                return current
            elif data < current:
                current = current.left
            else:
                current = current.right
        return False
        
    def preorder(self, node):
        if node:
            print node.data
            self.preorder(node.left)
            self.preorder(node.right)
        else:
            return
            
    def inorder(self, node):
        if node:
            self.inorder(node.left)
            print node.data
            self.inorder(node.right)
        else:
            return
            
    def postorder(self, node):
        if node:
            self.postorder(node.left)
            self.postorder(node.right)
            print node.data
        else:
            return
            
    def show(self):
        print 'preorder'
        self.preorder(self.root)
        print 'inorder'
        self.inorder(self.root)
        print 'postorder'
        self.postorder(self.root)
```

附件:

binarysearchtree.py
bstwithfather.py