用python从二叉树中删除一个节点

Question

通过将一个节点从树中删除，该节点(情形1)可以是具有单臂(右或左)的节点，也可以是具有两个分支的节点。如果要删除的节点是具有两个分支的中间节点，则有两种不同的方法。方法一:左臂上最大的结或右臂上最小的结，并方法2:实现分支中深度(或元素数量)更大的节点，使右臂或左臂平衡。这两个方法必须用单独的函数编码。

这两种方法怎么做?

class Node:
def __init__(self, data):
self.left   = None
self.right  = None
self.parent = None  # new
self.data   = data
def insert(self, data):
if self.data:                       # add by comparison
if data < self.data:            # left if small     
if self.left is None:           # add left if left is blank
self.left = Node(data)
self.left.parent = self     # new
else:
self.left.insert(data)      # if left is not empty add to left sub-tree
elif data > self.data:          # right if greater
if self.right is None:          # add right if right is blank
self.right = Node(data)
self.right.parent = self    # new
else:                           # if right is not empty add to sub-tree right
self.right.insert(data)
else:
self.data = data        # the first dream of the tree

# print Tree
def PrintTree(self):
print( self.data,end='-')
if self.left:
self.left.PrintTree()
if self.right:
self.right.PrintTree()

def sizeTree(self): 
if self.left and self.right:
return 1 + self.left.sizeTree() + self.right.sizeTree()
elif self.left:
return 1 + self.left.sizeTree()
elif self.right:
return 1 + self.right.sizeTree()
else:
return 1
def depth(self):
if self.left and self.right:
l = self.left.depth()
r = self.right.depth()
return 1 + max(l,r)
elif self.left:
return 1 + self.left.depth()
elif self.right:
return 1 + self.right.depth()
else:
return 1
# Use the insert method to add nodes
root = Node(25)
root.insert(12)
root.insert(10)
root.insert(22)
root.insert(5)
root.insert(36)
root.insert(30)
root.insert(40)
root.insert(28)
root.insert(38)
root.insert(48)
root.PrintTree()

"""
# 25,36,20,10,5,22,40,48,38,30,22,12,28
root = Node(25)
root.insert(36)
root.insert(20)
root.insert(10)
root.insert(5)
root.insert(22)
root.insert(40)
root.insert(48)
root.insert(38)
root.insert(30)
root.insert(12)
root.insert(28)
print("n",root.sizeTree(),root.depth())
"""

Answer 1

前一段时间我在玩这个，想出了这个代码:

def search(self, value):
"""
Recursively looks to the left and right of Tree depending on the provided value
and returns it if it is present within Tree.
Args:
value (int): value to be searched for within Tree
Returns:
value if value exists in Tree otherwise None
"""
if value < self.data:
if self.left is None:
return None
return self.left.search(value)
elif value > self.data:
if self.right is None:
return None
return self.right.search(value)
else:
return self.data
def _findNodeToDelete(self, value, previous=None):
"""
Recursively looks to the left and right of Tree depending on the provided value
and returns it if it is present within Tree.
Args:
value (int): value to be searched for within Tree
Returns:
value if value exists in Tree otherwise None
"""
if value < self.data:
if self.left is None:
return None
return self.left._findNodeToDelete(value, self)
elif value > self.data:
if self.right is None:
return None
return self.right._findNodeToDelete(value, self)
else:
return self, previous

def _mergeNodes(self, target):
self.data = target.data
self.left = target.left
self.right = target.right

def deleteNode(self, value, start=None):

if self.search(value):

to_delete, parent = self._findNodeToDelete(value, start)

if to_delete.right and to_delete.left:
new_value = to_delete.right.min
to_delete.data = new_value
to_delete.right.deleteNode(new_value, to_delete)

elif to_delete.left:
to_delete._mergeNodes(to_delete.left)

elif to_delete.right:
to_delete._mergeNodes(to_delete.right)

else:
if parent:
if parent.data > value:
parent.left = None
else:
parent.right = None
else:
self.data = None

注意，我没有使用parent属性，而是在删除时计算它。