Python - 將n元樹轉換爲二叉樹

Question

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 

Answer 1

帝斯曼的評論幫助我瞭解到底發生了什麼。在convert_to_binary_tree方法的第一部分中選擇left_child和right_child之後，您並未將它們從子項列表中刪除。這意味着，稍後，當您將所有當前節點的子節點添加到新父母中時，您將自己（或彼此）添加左側和右側兒童。當你遞歸到這些孩子，你可以無限循環。

我並不真正瞭解您的left_child和right_child選擇的邏輯，所以我沒有固定的代碼向您推薦。一個快速但難看的解決方法是將一個if child in (left_child, right_child): continue語句放在for循環的頂部，在那裏將其他孩子分配給新父母。

請注意，您的當前代碼中存在另一個錯誤，其中左側和右側子代的後代計數將不正確。那是因爲當你把他們的一些前兄弟姐妹作爲孩子時，他們並沒有更新計數。