Javaの

Question

にバイナリツリーのすべてのノードを横断

のは、私はそうのように、単純なバイナリツリーノードのクラスを持っているとしましょう：

public class BinaryTreeNode { 
    public String identifier = ""; 
    public BinaryTreeNode parent = null; 
    public BinaryTreeNode left = null; 
    public BinaryTreeNode right = null; 

    public BinaryTreeNode(BinaryTreeNode parent, String identifier) 
    { 
     this.parent = parent; //passing null makes this the root node 
     this.identifier = identifier; 
    } 

    public boolean IsRoot() { 
     return parent == null; 
    } 
} 

にはどうすれば再帰的に任意のサイズの木を横断することが可能である方法を追加します既存の各ノードを左から右に移動して、なしで、すでに通過したノードを再訪しますか？

この作品？：

public void traverseFrom(BinaryTreeNode rootNode) 
{ 
    /* insert code dealing with this node here */ 

    if(rootNode.left != null) 
     rootNode.left.traverseFrom(rootNode.left); 

    if(rootNode.right != null) 
     rootNode.traverseFrom(rootNode.right); 
} 

Answer 1

はあなたが達成することができバイナリツリートラバーサルの3種類があります：

：この次のバイナリツリーを検討

：

の例では、

Pre-order traversal sequence: F, B, A, D, C, E, G, I, H (root, left, right) 
In-order traversal sequence: A, B, C, D, E, F, G, H ,I (left, root, right) 
Post-order traversal sequence: A, C, E, D, B, H, I, G, F (left, right, root) 

コード例：

、二分木の右トラバーサルバイナリツリーの順走査でいやを左：

public void traverse (Node root){ // Each child of a tree is a root of its subtree. 
    if (root.left != null){ 
     traverse (root.left); 
    } 
    System.out.println(root.data); 
    if (root.right != null){ 
     traverse (root.right); 
    } 
} 

Answer 2

codeManは正しいです。トラバーサルは、左側のすべてのノードを訪問します。一番左のノードに達すると、右側のノードに沿って作業を開始します。これは深さ優先検索（DFS）トラバーサルです。そのため、各ノードは1回のみ訪問され、アルゴリズムはO（n）時間で実行されます。ハッピーコーディング。