Java二叉樹遍歷算法都有哪些？動力節(jié)點小編來給大家總結(jié)一下。

二叉樹的遍歷(traversing binary tree)是指從根結(jié)點出發(fā)，按照某種次序依次訪問二叉樹中所有的結(jié)點，使得每個結(jié)點被訪問依次且僅被訪問一次。

四種遍歷方式分別為：先序遍歷、中序遍歷、二叉樹后序遍歷、層序遍歷。

首先來看前序遍歷，所謂的前序遍歷就是先訪問根節(jié)點，再訪問左節(jié)點，最后訪問右節(jié)點，

如上圖所示，前序遍歷結(jié)果為：

ABDFECGHI

實現(xiàn)代碼如下：

/**
     * 二叉樹前序遍歷   根-> 左-> 右
     * @param node    二叉樹節(jié)點
     */
    public static void preOrderTraveral(TreeNode node){
        if(node == null){
            return;
        }
        System.out.print(node.data+" ");
        preOrderTraveral(node.leftChild);
        preOrderTraveral(node.rightChild);
    }

再者就是中序遍歷，所謂的中序遍歷就是先訪問左節(jié)點，再訪問根節(jié)點，最后訪問右節(jié)點，

如上圖所示，中序遍歷結(jié)果為：

DBEFAGHCI

實現(xiàn)代碼如下：

/**
     * 二叉樹中序遍歷   左-> 根-> 右
     * @param node   二叉樹節(jié)點
     */
    public static void inOrderTraveral(TreeNode node){
        if(node == null){
            return;
        }
        inOrderTraveral(node.leftChild);
        System.out.print(node.data+" ");
        inOrderTraveral(node.rightChild);
    }

最后就是后序遍歷，所謂的后序遍歷就是先訪問左節(jié)點，再訪問右節(jié)點，最后訪問根節(jié)點。

如上圖所示，后序遍歷結(jié)果為：

DEFBHGICA

實現(xiàn)代碼如下：

/**
     * 二叉樹后序遍歷   左-> 右-> 根
     * @param node    二叉樹節(jié)點
     */
    public static void postOrderTraveral(TreeNode node){
        if(node == null){
            return;
        }
        postOrderTraveral(node.leftChild);
        postOrderTraveral(node.rightChild);
        System.out.print(node.data+" ");
    }

講完上面三種遞歸的方法，下面再給大家講講非遞歸是如何實現(xiàn)前中后序遍歷的。

還是一樣，先看非遞歸前序遍歷

1.首先申請一個新的棧，記為stack;

2.聲明一個結(jié)點treeNode，讓其指向node結(jié)點;

3.如果treeNode的不為空，將treeNode的值打印，并將treeNode入棧，然后讓treeNode指向treeNode的右結(jié)點，

4.重復(fù)步驟3，直到treenode為空;

5.然后出棧，讓treeNode指向treeNode的右孩子

6.重復(fù)步驟3，直到stack為空.

實現(xiàn)代碼如下：

public static void preOrderTraveralWithStack(TreeNode node){
        Stack<TreeNode> stack = new Stack<TreeNode>();
        TreeNode treeNode = node;
        while(treeNode!=null || !stack.isEmpty()){
            //迭代訪問節(jié)點的左孩子，并入棧
            while(treeNode != null){
                System.out.print(treeNode.data+" ");
                stack.push(treeNode);
                treeNode = treeNode.leftChild;
            }
            //如果節(jié)點沒有左孩子，則彈出棧頂節(jié)點，訪問節(jié)點右孩子
            if(!stack.isEmpty()){
                treeNode = stack.pop();
                treeNode = treeNode.rightChild;
            }
        }
    }

中序遍歷非遞歸，在此不過多敘述具體步驟了。如果大家對此比較感興趣，想了解更多相關(guān)知識，不妨來關(guān)注一下動力節(jié)點的Java教程，里面有更豐富的知識等著大家去學(xué)習(xí)，相信對大家會有所幫助的。