[Python知识库]python实现一个功能完整的查找树

直接上代码

# 创建时间 2021/4/2 21:49
# coding=utf-8
class SearchTree(object):
    """
    构造一个查找树
    """

    def __init__(self, key=-1, tree_dict=None):
        if tree_dict is None:
            tree_dict = {}
        self.key = key
        self.tree_dict = tree_dict

    def tree_insert(self, point):
        """
        插入节点
        输入: 节点值
        输出: null
        """
        self.key += 1
        if len(self.tree_dict) == 0:
            self.tree_dict[self.key] = {'point': point, 'left': None, 'right': None, 'parent': None}  # point为节点值,其余为索引值
        else:
            p1, p2 = 0, 0
            while p1 is not None:
                p2 = p1
                if point <= self.tree_dict[p1]['point']:
                    p1 = self.tree_dict[p1]['left']
                else:
                    p1 = self.tree_dict[p1]['right']
            if point <= self.tree_dict[p2]['point']:
                self.tree_dict[p2]['left'] = self.key
                self.tree_dict[self.key] = {'point': point, 'left': None, 'right': None, 'parent': p2}
            else:
                self.tree_dict[p2]['right'] = self.key
                self.tree_dict[self.key] = {'point': point, 'left': None, 'right': None, 'parent': p2}

    def inorder_tree_walk(self, x):
        """
        中序遍历,可以输出排序的值
        """
        if not x is None:
            self.inorder_tree_walk(self.tree_dict[x]['left'])
            print(self.tree_dict[x]['point'])
            self.inorder_tree_walk(self.tree_dict[x]['right'])

    def tree_search(self, x, point):
        """
        查找树中的值,返回第一个找到的值的key
        """
        if x is None or self.tree_dict[x]['point'] == point:
            return x
        if point < self.tree_dict[x]['point']:
            return self.tree_search(self.tree_dict[x]['left'], point)
        else:
            return self.tree_search(self.tree_dict[x]['right'], point)

    def tree_minimum(self, x):
        """
        传入一个标签, 寻找树中该标签以下的最小值标签
        """
        while not self.tree_dict[x]['left'] is None:
            x = self.tree_dict[x]['left']
        return x

    def tree_maximum(self, x):
        """
        传入一个标签, 寻找树中该标签以下的最大值标签
        """
        while not self.tree_dict[x]['right'] is None:
            x = self.tree_dict[x]['right']
        return x

    def tree_successor(self, x):
        """
        传入一个标签, 寻找树中该标签的后继标签
        """
        if not self.tree_dict[x]['right'] is None:
            return self.tree_minimum(self.tree_dict[x]['right'])
        y = self.tree_dict[x]['parent']
        while not y is None and x == self.tree_dict[y]['right']:
            x = y
            y = self.tree_dict[y]['parent']
        return y

    def tree_delete(self, z):
        """
        传入一个标签, 删除标签所指向的节点
        """
        def transplant(u, v):
            """传入标签, 用子树v代替子树u"""
            if u == 0:
                self.tree_dict[0] = self.tree_dict[v]
            elif u == self.tree_dict[self.tree_dict[u]['parent']]['left']:
                self.tree_dict[self.tree_dict[u]['parent']]['left'] = v
            else:
                self.tree_dict[self.tree_dict[u]['parent']]['right'] = v
            if not v is None:
                self.tree_dict[v]['parent'] = self.tree_dict[u]['parent']

        if self.tree_dict[z]['left'] is None:
            transplant(z, self.tree_dict[z]['right'])
            del self.tree_dict[z]
        elif self.tree_dict[z]['right'] is None:
            transplant(z, self.tree_dict[z]['left'])
            del self.tree_dict[z]
        else:
            y = self.tree_minimum(self.tree_dict[z]['right'])
            if self.tree_dict[y]['parent'] != z:
                transplant(y, self.tree_dict[y]['right'])
                self.tree_dict[y]['right'] = self.tree_dict[z]['right']
                self.tree_dict[self.tree_dict[y]['right']]['parent'] = y
            transplant(z, y)
            self.tree_dict[y]['left'] = self.tree_dict[z]['left']
            self.tree_dict[self.tree_dict[y]['left']]['parent'] = y
            del self.tree_dict[z]

1.程序依照算法导论黑皮书编写, 在原来伪代码的基础上做了一些调整.
2. 由于python没有指针, 所以用一个标签key代表每个节点的位置, 把每个节点的属性放在一个字典里, 又把这些节点放在一个字典里, 对整个字典操作.如下:
{key1: {节点}…}
3.目前还没有想到更好实现查找树的方法, 如有大佬知晓, 还请不吝赐教.