数据结构之二叉树：二叉查找树，Python代码实现——10

数据结构之二叉查找树的代码实现

定义

• 二叉查找树（Binary Search Tree，BST），是一种内存中特殊的树类型的存储结构，它允许对存储在其结点的数据进行增删改查，或者用作动态的数据集合，或是通过key查找对应value的查找表；

创建结点

• 设计：可以使用顺序表或链表实现二叉树，这里使用链表实现，在学习堆时再使用顺序表实现

使用链表结点设计：

class Node:
    def __init__(self, key=None, value=None):
        self.key = key
        self.value = value
        self.left = None
        self.right = None

left和right分别代表左右子结点，key是可比较的，用于进行顺序匹配；value储存值

实现的功能

• 构造方法__init__()，root为根结点，默认为None，len为树的大小

1. size()获取BST中元素个数
2. put(_key, _value)向树中添加键值对元素，元素按key排序，返回添加元素后的新树
3. get(_key)通过键获取树中对应元素的值
4. delete(_key)通过键删除树中对应的元素
5. min_key()获取最小的key
6. max_key()获取最大的key

Python代码实现

import operator
class BinarySearchTree:
    def __init__(self):
        self.root = None
        self.len = 0

    def size(self):
        return self.len

    def put(self, _key, _value):
        """Put an element into this tree and return the new tree"""
        def put_into(node, _key, _value):
            if not node:
                self.len += 1
                return Node(_key, _value)
            if operator.lt(_key, node.key):
                # print(f"left: {node}")
                node.left = put_into(node.left, _key, _value)
            elif operator.gt(_key, node.key):
                # print(f"right: {node}")
                node.right = put_into(node.right, _key, _value)
            elif operator.eq(_key, node.key):
                node.value = _value
            return node
        self.root = put_into(self.root, _key, _value)
        return self.root

    def get(self, _key):
        """Get element from this tree according to the given _key"""
        def get_value_by_key(node, _key):
            if not node:
                return
            if operator.lt(_key, node.key):
                return get_value_by_key(node.left, _key)
            elif operator.gt(_key, node.key):
                return get_value_by_key(node.right, _key)
            else:
                return node.value
        return get_value_by_key(self.root, _key)

    def delete(self, _key):
        """Delete an element according to its key"""
        def delete_value_by_key(node, _key):
            # When tree(sub-tree) is none, return none
            if not node:
                return
            # When the tree is not none
            # Find the element according to its key
            # When _key is little than the current node's key, recursively find the left sub-tree
            # ,and finally return its result to the node.left
            if operator.lt(_key, node.key):
                node.left = delete_value_by_key(node.left, _key)
            # When _key is bigger than the current node's key, recursively find the right sub-tree
            # ,and finally return its result to the node.right
            elif operator.gt(_key, node.key):
                node.right = delete_value_by_key(node.right, _key)
            # ELse, we have found the to-delete-node where _key==node.key
            else:
                # Now, we could start to do the delete-action
                self.len -= 1
                to_delete_node = node
                if node == self.root:
                    self.root = None
                    return
                node = None
                # When the node we found had no left child tree, return its right child sub-tree
                if not to_delete_node.left:
                    return to_delete_node.right
                # As similar to the node's left child tree above
                elif not to_delete_node.right:
                    return to_delete_node.left
                else:
                    # Else, find the minimum-key element from its right child sub-tree
                    min_right_tree = to_delete_node.right
                    pre = min_right_tree
                    # The minimum will always be in the most left
                    while min_right_tree.left:
                        pre = min_right_tree
                        min_right_tree = min_right_tree.left
                    # Delete the minimum's edge from its parent node
                    pre.left = None
                    # Substitute the minimum with the to-delete node:
                    # Substitute the to-delete-node's left with the minimum's left
                    min_right_tree.left = to_delete_node.left
                    # Substitute the to-delete node's right with the minimum's right
                    min_right_tree.right = to_delete_node.right
                    # Return to its original node's left/right
                    return min_right_tree
        return delete_value_by_key(self.root, _key)

    def min_key(self):
        """Find the minimum key"""
        def min_node(node):
            while node.left:
                node = node.left
            return node
        return min_node(self.root).key

    def max_key(self):
        """Find the maximum key"""
        def max_node(node):
            while node.right:
                node = node.right
            return node
        return max_node(self.root).key

主要代码解释：

put()插入元素：使用递归，按照从上到下从左到右的顺序，依次和插入的元素比较

• 1.如果当前树中没有任何一个结点，则直接把新结点当做根结点使用并返回
• 2.如果当前树不为空, 则从根结点开始与传入的元素的key进行比较：
  2.1如果新结点的key小于当前结点的key ,则继续找当前结点的左子结点;
  2.2如果新结点的key大于当前结点的key ,则继续找当前结点的右子结点;
  2.3如果新结点的key等于当前结点的key ,则树中已经存在这样的结点,替换该结点的value值即可。

delete()删除元素：跟插入元素类似，也是使用递归，寻找的顺序按照从上到下从左到右的顺序，依次和插入的元素比较，如果找到key相等的元素则做删除动作

• 如果找到key相等的元素，则只需要往这个结点的右子树的左边最深处寻找，根据排序的规律，找到的元素与key相等的元素交换位置即可
  
  其中operator模块不是必要，Python中使用比较符号即可直接比较数字和字母

代码测试

if __name__ == '__main__':
    BST = BinarySearchTree()

    BST.put('e', '5')
    BST.put('b', '2')
    BST.put('g', '7')
    BST.put('a', '1')
    BST.put('d', '4')
    BST.put('f', '6')
    BST.put('h', '8')
    BST.put('c', '3')
    print([(key, BST.get(key)) for key in BST.pre_ergodic()])
    print([(key, BST.get(key)) for key in BST.mid_ergodic()])
    print([(key, BST.get(key)) for key in BST.post_ergodic()])
    print([(key, BST.get(key)) for key in BST.layer_ergodic()])
    print(f"After function put(), the size of this binary tree is {BST.size()} ")

    key = 'a'
    print(f"Get element by key[{key}]: {BST.get(key)}")

    key = 'b'
    BST.delete(key)
    print(f"After deleting an element(key[{key}]), the size of this tree: {BST.size()}")
    print(f"Get the deleted element(key[{key}]), it should be none: {BST.get(key)}")
    print(f"Get the deleted element(key[{'a'}]), it should be none: {BST.get('a')}")

测试结果

After function put(), the size of this binary tree is 8 
Get element by key[a]: 1
After deleting an element(key[b]), the size of this tree: 7
Get the deleted element(key[b]), it should be none: None
Get the deleted element(key[a]), it should be none: 1
Get the minimum key: a
Get the maximum key: h

下一节，将继续实现BST的先序遍历、中序遍历、后序遍历和层序遍历