Python中的二叉排序树和平衡二叉树是什么

  """

定义一个二叉树节点类。

以讨论算法为主，忽略了一些诸如对数据类型进行判断的问题。

"""

def __init__(self, data, left=None, right=None):

    """

    初始化

    :param data: 节点储存的数据

    :param left: 节点左子树

    :param right: 节点右子树

    """

    self.data = data

    self.left = left

    self.right = rightclass BinarySortTree:

"""

基于BSTNode类的二叉排序树。维护一个根节点的指针。

"""

def __init__(self):

    self._root = None

def is_empty(self):

    return self._root is None

def search(self, key):

    """

    关键码检索

    :param key: 关键码

    :return: 查询节点或None

    """

    bt = self._root        while bt:

        entry = bt.data            if key < entry:

            bt = bt.left            elif key > entry:

            bt = bt.right            else:                return entry        return None

def insert(self, key):

    """

    插入操作

    :param key:关键码

    :return: 布尔值

    """

    bt = self._root        if not bt:

        self._root = BSTNode(key)            return

    while True:

        entry = bt.data            if key < entry:                if bt.left is None:

                bt.left = BSTNode(key)                    return

            bt = bt.left            elif key > entry:                if bt.right is None:

                bt.right = BSTNode(key)                    return

            bt = bt.right            else:

            bt.data = key                return

def delete(self, key):

    """

    二叉排序树最复杂的方法

    :param key: 关键码

    :return: 布尔值

    """

    p, q = None, self._root     # 维持p为q的父节点，用于后面的链接操作

    if not q:

        print("空树！")            return

    while q and q.data != key:

        p = q            if key < q.data:

            q = q.left            else:

            q = q.right            if not q:               # 当树中没有关键码key时，结束退出。

            return

    # 上面已将找到了要删除的节点，用q引用。而p则是q的父节点或者None（q为根节点时）。

    if not q.left:            if p is None:

            self._root = q.right            elif q is p.left:

            p.left = q.right            else:

            p.right = q.right            return

    # 查找节点q的左子树的最右节点，将q的右子树链接为该节点的右子树

    # 该方法可能会增大树的深度，效率并不算高。可以设计其它的方法。

    r = q.left        while r.right:

        r = r.right

    r.right = q.right        if p is None:

        self._root = q.left        elif p.left is q:

        p.left = q.left        else:

        p.right = q.left    def __iter__(self):

    """

    实现二叉树的中序遍历算法,

    展示我们创建的二叉排序树.

    直接使用python内置的列表作为一个栈。

    :return: data

    """

    stack = []

    node = self._root        while node or stack:            while node:

            stack.append(node)

            node = node.left

        node = stack.pop()            yield node.data

        node = node.rightif __name__ == '__main__':

lis = [62, 58, 88, 48, 73, 99, 35, 51, 93, 29, 37, 49, 56, 36, 50]

bs_tree = BinarySortTree()    for i in range(len(lis)):

    bs_tree.insert(lis[i])    # bs_tree.insert(100)

bs_tree.delete(58)    for i in bs_tree:

    print(i, end=" ")    # print("\n", bs_tree.search(4))