Python数据结构之二叉树查、删、修数据结构之二叉树查、删、修
Python数据结构之二叉树增、查、删、修数据结构之二叉树增、查、删、修
增加增加
一层一层添加数据(层序遍历原则),使用队列对结点进行存储,从左向右增加结点,最终可形成完全二叉树。
def add(self, val):
"""添加树节点实现完全二叉树"""
node = Node(val)
if self.root is None:
self.root = node
return
# 使用队列来实现节点存储
queue = [self.root] while queue:
tmp_node = queue.pop(0) # 先进先出
# 左子树
if tmp_node.left_child is None:
tmp_node.left_child = node
return
else:
queue.append(tmp_node.left_child)
# 右子树
if tmp_node.right_child is None:
tmp_node.right_child = node
return
else:
queue.append(tmp_node.right_child)
查找查找
查找当前结点查找当前结点
层序查找
def bro_search(self, val):
"""查找指定数据的父亲结点"""
if self.root.val == val: # 根节点无父亲节点
return self.root
# 层序遍历,寻找节点
queue = [self.root]
while queue:
tmp_node = queue.pop(0)
if tmp_node.left_child and tmp_node.left_child.val == val:
return tmp_node.left_child
if tmp_node.right_child and tmp_node.right_child.val == val:
return tmp_node.right_child
# 往下一层进行寻找
if tmp_node.left_child:
queue.append(tmp_node.left_child)
if tmp_node.right_child:
queue.append(tmp_node.right_child)
return None
前序查找
def pre_search(self, node, val):
"""先序遍历"""
if node is None:
return
if node.val == val: