inorder traversal von Baum

Question

Ich schaue auf eine inkorrekte intraorale Traversale einer Baumimplementierung und frage mich, wie ich das Ergebnis in einer Liste speichern und aus der rekursiven Funktion zurückgeben kann. Ich habe Probleme, diese Liste während des Abwickelns des Stapels beizubehalten.

So habe ich den Code wie:

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

def recursive_inorder(root): 
    if not root: 
     return 

    nodes = list() 

    recursive_inorder(root.left) 
    nodes.append(root.value) 
    print root.value 
    recursive_inorder(root.right) 
    return nodes 

Und ich nenne dies als:

three = BinaryTreeNode(3) 
five = BinaryTreeNode(5) 
one = BinaryTreeNode(1) 
four = BinaryTreeNode(4) 
two = BinaryTreeNode(2) 
six = BinaryTreeNode(6) 

three.left = five 
five.left = one 
five.right = four 

three.right = two 
two.left = six 

nodes = recursive_inorder(three) 

Die Knoten werden in der richtigen Reihenfolge durchlaufen, aber Ich habe Probleme, herauszufinden, wie zu sparen das Ergebnis in die nodes Liste.

Answer 1

Verwenden Sie den Rückgabewert des rekursiven Aufrufs, um Ihre Knoten Liste zu erweitern. Auch eine leere Liste zurück, wenn Sie einen None Wert haben, so dass Ihre Funktion garantiert wird immer eine Liste zurück:

def recursive_inorder(root): 
    if not root: 
     return [] 

    nodes = list() 

    nodes.extend(recursive_inorder(root.left)) 
    nodes.append(root.value) 
    nodes.extend(recursive_inorder(root.right)) 
    return nodes 

Oder etwas prägnanter:

def recursive_inorder(root): 
    if not root: 
     return [] 

    return recursive_inorder(root.left) + [root.value] + recursive_inorder(root.right)