删除二叉树中的一个分支(链表实现)

Question

我正在尝试使用链表创建二叉树。我想在二叉树中删除一个节点，我实现的方式是将我想要删除的分支的地址(指针)设置为None，但是当我运行遍历方法时，分支仍然显示。

这是我的代码

class tree:
def __init__(self,val):
self.val=val
self.left=None
self.right=None

def preorder(root):
if root is None:
return 
print(root.val)
tree.preorder(root.left)
tree.preorder(root.right)


def inorder(root):
if root is None:
return
tree.inorder(root.left)
print(root.val)
tree.inorder(root.right)

def postorder(root):
if root is None:
return
tree.postorder(root.left)
tree.postorder(root.right)
print(root.val)
def levelorder(root):
if root is None:
return
Q=[]
Q.append(root)
while Q!=[]:
l=len(Q)
for i in range(l):
print(Q[i].val)
temp=[]
for i in Q:
if i.left is not None:
temp.append(i.left)
if i.right is not None:
temp.append(i.right) 
Q.clear()
Q=temp.copy()
def search(root,value):
o=[]
o.append(tree.levelorder(root))
if value in o:
return "Found"
else:
return "Not Found"
def insert(root,value,where):
if root is None:
return
Q=[]
Q.append(root)
value=tree(value)
while Q!=[]:
for i in Q:
if i.val==where:
if i.left is not None:
i.right=value
else:
i.left=value
return
temp=[]
for i in Q:
if i.left is not None:
temp.append(i.left)
if i.right is not None:
temp.append(i.right) 
Q.clear()
Q=temp.copy()

def delete(root,value):
if root is None:
return
Q=[]
Q.append(root)
value=tree(value)
while Q!=[]:
for i in Q:
if i.left is not None and i.left.val==value:
i.left.val=None
i.left=None
if i.right is not None and i.right.val==value:
i.right.val=None
i.right=None
return

temp=[]
for i in Q:
if i.left is not None:
temp.append(i.left)
if i.right is not None:
temp.append(i.right) 
Q.clear()
Q=temp.copy()

下面是我创建树的方法

base=tree("drinks")
L=tree("hot")
R=tree("cold")
LL=tree("coffe")
LR=tree("tea")
LRL=tree("w milk")
LRR=tree("wo milk")
base.left=L
base.right=R
L.left=LL
L.right=LR
LR.left=LRL
LR.right=LRR

现在当我运行delete方法时，应该被删除的对象仍然出现。

tree.delete(base,"w milk")
tree.levelorder(base)
drinks
hot
cold
coffe
tea
ice cream
w milk
wo milk <=== the node i am trying to delete

Answer 1

主要问题:

• delete方法的while循环将立即退出，因为return语句
• 要比较的值不应该变成value=tree(value)
的节点

代码注释:

• 您将永远不能删除树的根节点，因为您只检查子节点的值。为了允许删除根目录并表示空树，您应该考虑创建第二个类。当前类可以重命名为Node，新类可以重命名为Tree。

• 对于类名使用首字母大写是一种常见的习惯，而对于变量名则总是以小写字母开头。所以不是Q，而是q。

• 打印这些类的内部方法不是很好的做法:这些方法应该只是提供遍历节点的工具，而不应该打印它们。用yield代替。

  例如，search应该在找到节点时返回，None则返回节点。不打印结果

• 当where节点的左子节点和右子节点都已被占用时，insert方法实际上可能会删除节点。最好拒绝这样的插入。

• 在OOP模式中，调用实例方法的第一个参数self是被广泛接受的。在OOP中，你可以用点符号来调用这些方法:所以你可以用root.left.postorder()来代替tree.postorder(root.left)。

• 你有相当多的代码重复:主要是遍历，并且你使用队列算法两次。尽量避免。

下面是你如何修改你的代码以符合这些建议的方法:

class Node:
def __init__(self, val):
self.val = val
self.left = None
self.right = None

def traverse(self, kind=0, parent=None):
if kind == 0:  # pre-order
yield (self, parent)  # don't print in methods
if self.left:
yield from self.left.traverse(kind, self)
if kind == 1:  # in-order
yield (self, parent)
if self.right:
yield from self.right.traverse(kind, self)
if kind == 2:  # post-order
yield (self, parent)

class Tree:
def __init__(self):
self.root = None  # Representing an empty tree
def traversevalues(self, kind=0):
if self.root:
for node, parent in self.root.traverse(kind):
yield node.val
def preorder(self):
yield from self.traversevalues(0)
def inorder(self):
yield from self.traversevalues(1)

def postorder(self):
yield from self.traversevalues(2)

def levelorder(self):
if self.root:
q = [self.root]
while q:
temp = []
for node in q:
yield node.val
if node.left:
temp.append(node.left)
if node.right:
temp.append(node.right) 
q = temp
def search(self, value):
if self.root:
return next((edge for edge in self.root.traverse() if edge[0].val == value), None)
def insert(self, value, where=None):
if not where:
if self.root:
raise ValueError("Must call insert with second argument")
else:
self.root = Node(value)
else:
edge = self.search(where)
if edge:
parent = edge[0]
if not parent.left:
parent.left = Node(value)
elif not parent.right:
parent.right = Node(value)
else:
raise ValueError(f"Node {where} already has 2 children")
else:
raise ValueError(f"Node {where} not found")

def deletesubtree(self, value):
edge = self.search(value)
if edge:
node, parent = edge
if parent.left == node:
parent.left = None
else:
parent.right = None
else:
raise ValueError(f"Node {value} not found")
tree = Tree()
tree.insert("drinks")
tree.insert("hot", "drinks")
tree.insert("cold", "drinks")
tree.insert("coffee", "hot")
tree.insert("tea", "hot")
tree.insert("with milk", "tea")
tree.insert("without milk", "tea")
print(*tree.levelorder())
tree.deletesubtree("without milk")
print(*tree.levelorder())