wie man eine Baumdatenstruktur analysiert?

Question

Ich habe eine Baumdatenstruktur, bestehend aus Knoten, die ich in einen Ausdrucksbaum analysieren muss. Meine Knoten wie folgt aussehen (vereinfacht):

public class Node 
    { 
     public Node Left { get; set; } 
     public Node Right { get; set; } 
     public Operation OperationType { get; set; } 
     public object Value { get; set; } 
    } 

Was ist die beste/richtige Weg, um die Unterseite des Baumes zu finden und arbeiten rückwärts den Ausdrucksbaum aufzubauen? Parsierst du zuerst links oder rechts?

Answer 1

Ich glaube nicht, dass es wichtig ist, in welche Richtung man zuerst geht. In einer Welt, in der Sprache von links nach rechts dominiert, würde jedoch jemand Ihren Code intuitiver verstehen, wenn Sie zuerst nach links gingen.

Answer 2

Wenn Sie zuerst zum Ende des Baumes kommen möchten, dann führen Sie eine 'In-Order' oder vielleicht 'Post-Order' Suche durch. Bei einer Suche in der richtigen Reihenfolge wird zuerst der unterste Knoten ganz links, dann der übergeordnete Knoten dieses Knotens und dann der rechte Unterknoten des übergeordneten Knotens gesucht. Eine Suche nach der Bestellung "besucht" sowohl den linken Kindknoten als auch den rechten Kindknoten, bevor er den Elternknoten besucht.

Betrachten Sie den Ausdruck 'x + y'. Eine in Ordnung ergäbe Suche:

'x', '+', 'y' 

während eine Post-Order-Suche ergeben würde:

'x', 'y', '+' 

Answer 3

Wie bereits erwähnt, ist es nicht wirklich wichtig, wo man zuerst gehen. Aber die üblichsten tree traversal Algorithmen. Wenn dieser Baum ist die Art und Weise organisiert Ich denke, inorder wäre zu empfehlen:

(aus Wikipedia) in Inorder einen nicht leeren binären Baum zu durchlaufen, führen Sie die folgenden Operationen rekursiv an jedem Knoten:

1. Traverse der linke Teilbaum.
2. Besuchen Sie die Wurzel.
3. Durchqueren Sie den rechten Teilbaum.