リーフだけを含む文字列にツリーを変換します

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