原文标题: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))
[版权声明]
本文标题:Python中的二叉排序树和平衡二叉树是什么作者:python学习
本文链接:http://www.ccpit.org.cn/gaoji/697.html——此文章系本站原创/整理,转载请标明出处、原标题、链接