老师，我根据课堂的讨论，把代码改动了一下，发现删除值为12的节点后，tree.root.left变成了值为29的节点，未明白为什么会是这个结果，麻烦老师帮忙看一下，代码如下：
NODE_LIST = [
{'data': 60, 'left': 12, 'right': 90, 'is_root': True},
{'data': 12, 'left': 4, 'right': 41, 'is_root': False},
{'data': 4, 'left': 1, 'right': None, 'is_root': False},
{'data': 1, 'left': None, 'right': None, 'is_root': False},
{'data': 41, 'left': 29, 'right': None, 'is_root': False},
{'data': 29, 'left': 23, 'right': 37, 'is_root': False},
{'data': 23, 'left': None, 'right': None, 'is_root': False},
{'data': 37, 'left': None, 'right': None, 'is_root': False},
{'data': 90, 'left': 71, 'right': 100, 'is_root': False},
{'data': 71, 'left': None, 'right': 84, 'is_root': False},
{'data': 100, 'left': None, 'right': None, 'is_root': False},
{'data': 84, 'left': None, 'right': None, 'is_root': False},
]
class Node():
def __init__(self,data=None,left=None,right=None):
self.data,self.left,self.right = data,left,right
def __str__(self):
return f'数据是:{self.data}'
class Tree():
def __init__(self,root=None):
self.root = root
def init_data(self,data_list):
node_dict = {}
for d in data_list:
node = Node(d['data'],d['left'],d['right'])
node_dict[d['data']] = node
for d in data_list:
node = node_dict[d['data']]
if node.left:
node.left = node_dict[d['left']]
if node.right:
node.right = node_dict[d['right']]
if d['is_root']:
self.root = node
def search(self,subtree,value): # 查找 #subtree表示从哪个节点开始查找
if subtree is None:
return None
elif subtree.data > value:
return self.search(subtree.left,value) # 这里return不能少
elif subtree.data < value:
return self.search(subtree.right,value) # 这里return不能少
else:
return subtree
def get_min(self,subtree): # 获取值最小的节点
if subtree is None:
return None
elif subtree.left is None:
return subtree
else:
return self.get_min(subtree.left)
def get_max(self,subtree): # 获取值最大的节点
if subtree is None:
return None
elif subtree.right is None:
return subtree
else:
return self.get_max(subtree.right)
def insert_data(self,subtree,value):
if subtree is None:
subtree = Node(value)
elif subtree.data > value:
subtree.left = self.insert_data(subtree.left,value) # 绑定节点关系，注意这句代码
else:
subtree.right = self.insert_data(subtree.right,value) # 绑定节点关系,注意这句代码
return subtree
def delete_data(self,subtree,value):
if subtree is None:
return None
elif subtree.data > value:
subtree.left = self.delete_data(subtree.left,value) # 找左分支删除，注意维持节点关系
return subtree
elif subtree.data < value:
subtree.right = self.delete_data(subtree.right,value) # 找右分支删除，注意维持节点关系
return subtree
else: # 找到节点
if subtree.left is None and subtree.right is None: # 要删除的是叶子节点
return None
elif subtree.left is None or subtree.right is None: # 要删除的节点只有1个分支
if subtree.left is not None:
return subtree.left
elif subtree.right is not None:
return subtree.right
else: # 要删除的节点含有2个分支
left_min_node = self.get_min(subtree.left) # 从要删除的节点的左分支中找到最小值
right_min_node = self.get_min(subtree.right) # 从要删除的节点的右分支中找到最小值
if left_min_node.data > right_min_node.data:
subtree.data = left_min_node.data
subtree.left = self.delete_data(subtree.left,left_min_node.data) # 从要删除的节点的左分支中删除值最小的节点,注意节点关系的维护
else:
subtree.data = right_min_node.data
subtree.right = self.delete_data(subtree.right,right_min_node.data) # 从要删除的节点的右分支中删除值最小的节点,注意节点关系的维护
return subtree
def add(self,value): # 增加数据
node = self.search(self.root,value) # 查找数据 是否已存在
if node:
return '该数据已存在'
else:
self.root = self.insert_data(self.root,value) # 绑定节点关系,注意这句代码
def remove(self,value): # 删除数据
node = self.search(self.root,value) # 查找数据 是否已存在
if node is None:
return '你要删除的数据不存在'
self.delete_data(self.root,value)
def tree_iter1(self,node): # 深度优先的遍历方法
if node:
print(node.data)
self.tree_iter1(node.left)
self.tree_iter1(node.right)
def tree_iter2(self,node): # 广度优先的遍历方法
node_list = [node]
for n in node_list:
print(n.data)
if n.left:
node_list.append(n.left)
if n.right:
node_list.append(n.right)
if __name__ == "__main__":
tree = Tree()
# tree.init_data(NODE_LIST)
# print(tree.search(tree.root,41))
# print(tree.search(tree.root,61))
# print(tree.get_min(tree.root))
# print(tree.get_max(tree.root))
# tree.add(60)
# tree.add(50)
# tree.add(70)
# tree.add(55)
# tree.add(80)
# print(tree.root)
# print(tree.root.left)
# print(tree.root.right)
# print(tree.root.left.right)
# print(tree.root.right.right)
tree.add(60)
tree.add(12)
tree.add(90)
tree.add(4)
tree.add(41)
tree.add(71)
tree.add(100)
# tree.add(1)
tree.add(2)
tree.add(29)
tree.add(84)
# tree.add(23)
tree.add(3)
tree.add(37)
print(tree.root)
print(tree.root.left)
tree.remove(12)
print(tree.root)
print(tree.root.left)
# tree.tree_iter2(tree.root)运行结果如下：
老师这什么原因 和视频里一样操作 老师一下测试成功 我的却超时了
文档没更新
,
京公网安备 11011402011233号