树和二叉树的转换代码python_Python - 将n-ary树转换为二叉树

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()

我必须将给定的树转换为二叉树 . 如果树中的节点有超过2个子节点，我必须将具有最多后代的子节点分配为左节点，将具有第二大后代数量的子节点分配为右子节点 . 其余子项添加如下：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