バイナリツリー巡回(DFS)


説明:


バイナリツリーの前列、中列、後列の順序を直接実現します.

コード#コード#

public class DFS {

    Node root;

    public static void main(String[] args) {
        DFS tree = new DFS();
        tree.root = new Node(1);
        tree.root.lt = new Node(2);
        tree.root.rt = new Node(3);
        tree.root.lt.lt = new Node(4);
        tree.root.lt.rt = new Node(5);
        tree.root.rt.lt = new Node(6);
        tree.root.rt.rt = new Node(7);
        DFS(tree.root);
        System.out.println();
        DFS2(tree.root);
        System.out.println();
        DFS3(tree.root);
        System.out.println();
    }

    //전위 순회
    public static void DFS(Node root){
        if(root==null) return ;
        System.out.print(root.data+" ");
        DFS(root.lt);
        DFS(root.rt);
    }

    //중위 순회
    public static void DFS2(Node root){
        if(root==null) return ;
        DFS(root.lt);
        System.out.print(root.data+" ");
        DFS(root.rt);
    }
    //후위 순회
    public static void DFS3(Node root){
        if(root==null) return ;
        DFS(root.lt);
        DFS(root.rt);
        System.out.print(root.data+" ");
    }
}
class Node{
    int data;
    Node lt,rt;

    public Node(int val) {
        data = val;
        lt=rt = null;
    }
}
전위1 2 4 5 3 6 7중위4 2 5 1 6 3 7후위4 5 2 6 7 3 1
main作成ノードの構造

Javaのクラスの構造と前衛中尉の後列のコードからStackFrameの概念を理解すると、上記の実行結果を理解するのに役立ちます.
Stack Frame