преобразовать дерево в строку, которая содержит только листья

Question

Я ищу алгоритм, который преобразует мою двоичную древовидную структуру: из моего собственного класса, где каждый узел имеет node.value, node.leftChild и node.rightChild. Я хочу преобразовать это дерево в формат Newick, поэтому нужно преобразовать только листья и структуру дерева.

дерево как enter image description here должно стать (B, (E, F)) (так без внутренних узлов)

Я думаю, что лучший способ это траверс моего дерева рекурсивно и построить строку, но у меня всегда есть ошибки для конкретных деревьев.

class binarynode(object): 
def __init__(self, value, left = None, right = None,parent =None): 
    self.parent = parent 
    self.value = value 
    self.left = left 
    self.right = right 

def isleaf(self): 
    return ((self.right == None) and (self.left ==None)) 


def convertTReeAux(self): 
    printValue = str(self.value) 

    if (self.isleaf() and self.parent == None): 
     ret = '('+printValue+')' 


    elif (self.isleaf() and (self.parent.left.value == self.value) and (self.parent.right.isleaf())) : 
     ret = '('+str(printValue)+',' 


    elif (self.isleaf() and self.parent.right.value==self.value and self.parent.left.isleaf() and self.parent.parent !=None and self.parent.parent.right == self.parent): 
     ret = str(printValue)+'))' 


    elif (self.isleaf() and self.parent.right.value==self.value and self.parent.left.isleaf()): 
     ret = str(printValue)+')' 


    elif (self.isleaf() and (self.parent.left.value == self.value) and (not self.parent.right.isleaf())): 
     ret = '('+str(printValue)+',' 


    elif (self.isleaf() and self.parent.right.value ==self.value and (not self.parent.left.isleaf())): 
     ret = ','+str(printValue)+')' 



    elif((not self.isleaf()) and (self.parent!= None) and (self.parent.left == self) and (not self.parent.right.isleaf())): 
     ret = "" 

    elif((not self.isleaf()) and (self.parent!= None) and (self.parent.right ==self) and (not self.parent.left.isleaf())): 
     ret=")," 


    elif((not self.isleaf()) and (self.parent!= None) and (self.parent.left ==self) and (not self.parent.left.isleaf())): 
     ret="(" 


    else: 
     ret = '' 

    if(self.left != None): 
     ret += (self.left.convertTReeAux()) 
    if(self.right != None): 
     ret += (self.right.convertTReeAux()) 
    return ret 

Answer 1

Я думаю, что следующий код - это то, что вы хотите. В классе Node я определил функцию isLeaf(), чтобы проверить, что узел является листом или нет.

class Node: 
    value = "" 
    leftChild = None 
    rightChild = None 
    def __init__(self, parent): 
     self.parent = parent 
    def isLeaf(self): 
     if (self.leftChild == None and self.rightChild == None): 
      return True 
     else: 
      return False 

def convertTreeAux(node, newick): 
    if node.isLeaf(): 
     newick.append(node.value) 
    if node.leftChild != None: 
     newick.append("(") 
     convertTreeAux(node.leftChild, newick) 
     newick.append(",") 
    if node.rightChild != None: 
     convertTreeAux(node.rightChild, newick) 
     newick.append(")") 

tree = Node(None) 
tree.value = "A" 
tree.leftChild = Node(tree) 
tree.leftChild.value = "B" 
tree.rightChild = Node(tree) 
tree.rightChild.value = "C" 
tree.rightChild.leftChild = Node(tree.rightChild) 
tree.rightChild.leftChild.value = "E" 
tree.rightChild.rightChild = Node(tree.rightChild) 
tree.rightChild.rightChild.value = "F" 

newick = [] 
convertTreeAux(tree, newick) 

print (''.join(newick))