Python中的二叉排序树和平衡二叉树是什么[python高级]

Z时代
2024-01-10
分类：综合

二叉排序树

二叉排序树又称为二叉查找树。它或者是一颗空树，或者是具有下列性质的二叉树：

若它的左子树不为空，则左子树上所有节点的值均小于它的根结构的值；若它的右子树不为空，则右子树上所有节点的值均大于它的根结构的值；它的左、右子树也分别为二叉排序树。

构造一颗二叉排序树的目的，往往不是为了排序，而是为了提高查找和插入删除关键字的速度。

二叉排序树的操作：

查找：对比节点的值和关键字，相等则表明找到了；小了则往节点的左子树去找，大了则往右子树去找，这么递归下去，最后返回布尔值或找到的节点。插入：从根节点开始逐个与关键字进行对比，小了去左边，大了去右边，碰到子树为空的情况就将新的节点链接。删除：如果要删除的节点是叶子，直接删；如果只有左子树或只有右子树，则删除节点后，将子树链接到父节点即可；如果同时有左右子树，则可以将二叉排序树进行中序遍历，取将要被删除的节点的前驱或者后继节点替代这个被删除的节点的位置。

"""

定义一个二叉树节点类。

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

"""

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("

", bs_tree.search(4))

相关推荐：《Python相关教程》

二叉排序树总结：

二叉排序树以链式进行存储，保持了链接结构在插入和删除操作上的优点。在极端情况下，查询次数为1，但最大操作次数不会超过树的深度。也就是说，二叉排序树的查找性能取决于二叉排序树的形状，也就引申出了后面的平衡二叉树。给定一个元素集合，可以构造不同的二叉排序树，当它同时是一个完全二叉树的时候，查找的时间复杂度为O(log(n))，近似于二分查找。当出现最极端的斜树时，其时间复杂度为O(n)，等同于顺序查找，效果最差。