Python - 将n叉树转换为二叉树
class Tree:
def __init__(self, new_key):
self.__key = new_key # Root key value
self.__children = [] # List of children
self.__num_of_descendants = 0 # Number of Descendants of this node
# Prints the given tree
def printTree(self):
return self.printTreeGivenPrefix("", True)
# Prints the given tree with the given prefix for the line
# last_child indicates whether the node is the last of its parent"s child
# or not
def printTreeGivenPrefix(self, line_prefix, last_child):
print(line_prefix, end="")
if last_child:
print("â””--> ", end="")
else:
print("|--> ", end="")
print(self.__key)
if len(self.__children) > 0:
next_pre = line_prefix
if last_child:
next_pre += " "
else:
next_pre += "| "
for child_index in range(len(self.__children)-1):
self.__children[child_index].\
printTreeGivenPrefix(next_pre, False)
self.__children[-1].printTreeGivenPrefix(next_pre, True)
def __repr__(self):
return "[" + str(self.__key) + "".join(
[ repr(child) for child in self.__children ]) + "]"
# This static function will load a tree with the format of below:
# [root[child_1][child_2]...[child_n]]
# Each child_i can be a tree with the above format, too
# pos is the position in the given string
@staticmethod
def loadTree(tree_str, pos = 0):
new_node = None
while pos < len(tree_str):
if tree_str[pos] == "[":
pos += 1
new_node = Tree(tree_str[pos])
while pos < len(tree_str) and tree_str[pos + 1] != "]":
pos += 1
child_tree, pos = Tree.loadTree(tree_str, pos)
if child_tree:
new_node.__children.append(child_tree)
new_node.__num_of_descendants += \
1 + child_tree.__num_of_descendants
return new_node, pos + 1
else:
pos += 1
return new_node, pos
def find_largest(self):
if self.__num_of_descendants == 1:
return self.__children[0]
else:
largest_child = self.__children[0]
for child in self.__children:
if child.__num_of_descendants > \
largest_child.__num_of_descendants:
largest_child = child
if child.__num_of_descendants == \
largest_child.__num_of_descendants:
if child.__key > largest_child.__key:
largest_child = child
return largest_child
def convert_to_binary_tree(self):
if self.__num_of_descendants != 0:
if self.__num_of_descendants < 3:
for child in self.__children:
child.convert_to_binary_tree()
if self.__num_of_descendants > 2:
left_child = self.__children[0]
for child in self.__children[1:]:
if len(child.__children) > len(left_child.__children):
left_child = child
elif len(child.__children) == len(left_child.__children):
if child.__key > left_child.__key:
left_child = child
self.__children.remove(left_child)
self.__num_of_descendants -= 1
right_child = self.__children[0]
for child in self.__children[1:]:
if len(child.__children) > len(right_child.__children):
right_child = child
elif len(child.__children) == len(right_child.__children):
if child.__key > right_child.__key:
right_child = child
self.__children.remove(right_child)
self.__num_of_descendants -= 1
print(self.__num_of_descendants)
print(self.__children)
print(left_child)
print(right_child)
#Move remaining children two either left_child or right_child.
while self.__num_of_descendants != 0:
largest_child = self.find_largest()
print(largest_child)
if left_child.__num_of_descendants < \
right_child.__num_of_descendants:
left_child.__children.append(largest_child)
left_child.__num_of_descendants += 1
self.__children.remove(largest_child)
self.__num_of_descendants -= 1
elif left_child.__num_of_descendants > \
right_child.__num_of_descendants:
right_child.__children.append(largest_child)
right_child.__num_of_descendants += 1
self.__children.remove(largest_child)
self.__num_of_descendants -= 1
elif left_child.__num_of_descendants == \
right_child.__num_of_descendants:
if left_child.__key > right_child.__key:
left_child.__children.append(largest_child)
left_child.__num_of_descendants += 1
self.__children.remove(largest_child)
self.__num_of_descendants -= 1
else:
right_child.__children.append(largest_child)
right_child.__num_of_descendants += 1
self.__children.remove(largest_child)
self.__num_of_descendants -= 1
#Now run recursion on left and right binary children.
self.__children.append(left_child)
self.__children.append(right_child)
self.__num_of_descendants = 2
print(self.__children)
for child in self.__children:
child.convert_to_binary_tree()
def main():
tree, processed_chars = Tree.loadTree('[z[y][x][w][v]]]')
tree.convert_to_binary_tree()
tree.printTree()
print(tree)
if __name__ == "__main__":
main()
我需要把一个给定的树转换成二叉树。如果树中的一个节点有超过两个孩子，我要把拥有最多后代的孩子作为左节点，把拥有第二多后代的孩子作为右节点。剩下的孩子则按照以下步骤添加：
1) 先找出拥有最多后代的孩子。
2) 把这个孩子添加到左节点或右节点，选择当前孩子数量较少的那个。
*如果在选择拥有最多后代的孩子时，发现有两个或更多的孩子后代数量相同，我会选择键值更大的那个。
I get a print out like this...
2 #Number of 'z' children after left and right node chosen.
[[w], [v]] #Children of 'z'
[y] #Binary left child of 'z'
[x] #Binary right child of 'z'
[w] #This is a bug. It should be choosing 'v' as larger child of 'z' and assigning it to left child 'y'
[v] #This is a bug. see above.
[[y[w]], [x[v]]] #These are the children of node 'z'
â””--> z #schematic of binary tree
|--> y
| â””--> w
â””--> x
â””--> v
[z[y[w]][x[v]]] #final binary tree
1 个回答
0
DSM的评论让我明白了发生了什么。在你选择了left_child（左孩子）和right_child（右孩子）之后，你并没有把它们从孩子列表中移除。这就导致了后面在把当前节点的所有孩子添加到新父节点时，你实际上是在把左孩子和右孩子添加到它们自己（或者互相）里面。当你递归到这些孩子时，就可能会陷入无限循环。
我对你选择left_child和right_child的逻辑不是很理解，所以我没有固定的代码可以建议给你。一个快速但不太优雅的解决办法是在你把其他孩子分配给新父节点的for循环顶部加一句if child in (left_child, right_child): continue，这样可以跳过左孩子和右孩子。
另外，你的代码中还有一个bug，就是左孩子和右孩子的后代计数会变得不正确。这是因为当你把它们以前的兄弟姐妹推入它们作为孩子时，你并没有更新计数。