Java二叉樹(shù)的四種遍歷方式詳解

更新時(shí)間：2021年11月05日 11:38:46 作者：林海杜

這篇文章主要介紹了Java二叉樹(shù)的四種遍歷,二叉樹(shù)的遍歷可以分為前序、中序、后序、層次遍歷,需要的朋友可以參考下

二叉樹(shù)的四種遍歷方式：

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

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

遍歷之前，我們首先介紹一下，如何創(chuàng)建一個(gè)二叉樹(shù)，在這里用的是先建左樹(shù)在建右樹(shù)的方法，

首先要聲明結(jié)點(diǎn)TreeNode類，代碼如下：

public class TreeNode {
    public int data;
    public TreeNode leftChild;
    public TreeNode rightChild;
    public TreeNode(int data){
        this.data = data;
    }
}

再來(lái)創(chuàng)建一顆二叉樹(shù)：

/**
     * 構(gòu)建二叉樹(shù)
     * @param list   輸入序列
     * @return
     */
    public static TreeNode createBinaryTree(LinkedList<Integer> list){
        TreeNode node = null;
        if(list == null || list.isEmpty()){
            return null;
        }
        Integer data = list.removeFirst();
        if(data!=null){
            node = new TreeNode(data);
            node.leftChild = createBinaryTree(list);
            node.rightChild = createBinaryTree(list);
        }
        return node;
    }

接下來(lái)按照上面列的順序一一講解，

首先來(lái)看前序遍歷，所謂的前序遍歷就是先訪問(wèn)根節(jié)點(diǎn)，再訪問(wèn)左節(jié)點(diǎn)，最后訪問(wèn)右節(jié)點(diǎn)，

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

ABDFECGHI

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

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

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

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

DBEFAGHCI

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

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

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

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

DEFBHGICA

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

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

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

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

1.首先申請(qǐng)一個(gè)新的棧，記為stack；

2.聲明一個(gè)結(jié)點(diǎn)treeNode，讓其指向node結(jié)點(diǎn)；

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

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

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

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

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

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

中序遍歷非遞歸，在此不過(guò)多敘述具體步驟了，

具體過(guò)程：

1.申請(qǐng)一個(gè)新棧，記為stack，申請(qǐng)一個(gè)變量cur，初始時(shí)令treeNode為頭節(jié)點(diǎn)；

2.先把treeNode節(jié)點(diǎn)壓入棧中，對(duì)以treeNode節(jié)點(diǎn)為頭的整棵子樹(shù)來(lái)說(shuō)，依次把整棵樹(shù)的左子樹(shù)壓入棧中，即不斷令treeNode=treeNode.leftChild，然后重復(fù)步驟2；

3.不斷重復(fù)步驟2，直到發(fā)現(xiàn)cur為空，此時(shí)從stack中彈出一個(gè)節(jié)點(diǎn)記為treeNode，打印node的值，并讓treeNode= treeNode.right，然后繼續(xù)重復(fù)步驟2；

4.當(dāng)stack為空并且cur為空時(shí)結(jié)束。

public static void inOrderTraveralWithStack(TreeNode node){
        Stack<TreeNode> stack = new Stack<TreeNode>();
        TreeNode treeNode = node;
        while(treeNode!=null || !stack.isEmpty()){
            while(treeNode != null){
                stack.push(treeNode);
                treeNode = treeNode.leftChild;
            }
            if(!stack.isEmpty()){
                treeNode = stack.pop();
                System.out.print(treeNode.data+" ");
                treeNode = treeNode.rightChild;
            }
        }
    }

后序遍歷非遞歸實(shí)現(xiàn)，后序遍歷這里較前兩者實(shí)現(xiàn)復(fù)雜一點(diǎn)，我們需要一個(gè)標(biāo)記位來(lái)記憶我們此時(shí)節(jié)點(diǎn)上一個(gè)節(jié)點(diǎn)，具體看代碼注釋

public static void postOrderTraveralWithStack(TreeNode node){
        Stack<TreeNode> stack = new Stack<TreeNode>();
        TreeNode treeNode = node;
        TreeNode lastVisit = null;   //標(biāo)記每次遍歷最后一次訪問(wèn)的節(jié)點(diǎn)
        while(treeNode!=null || !stack.isEmpty()){//節(jié)點(diǎn)不為空，結(jié)點(diǎn)入棧，并且指向下一個(gè)左孩子
            while(treeNode!=null){
                stack.push(treeNode);
                treeNode = treeNode.leftChild;
            }
            //棧不為空
            if(!stack.isEmpty()){
                //出棧
                treeNode = stack.pop();
                /**
                 * 這塊就是判斷treeNode是否有右孩子，
                 * 如果沒(méi)有輸出treeNode.data，讓lastVisit指向treeNode，并讓treeNode為空
                 * 如果有右孩子，將當(dāng)前節(jié)點(diǎn)繼續(xù)入棧，treeNode指向它的右孩子,繼續(xù)重復(fù)循環(huán)
                 */
                if(treeNode.rightChild == null || treeNode.rightChild == lastVisit) {
                    System.out.print(treeNode.data + " ");
                    lastVisit = treeNode;
                    treeNode  = null;
                }else{
                    stack.push(treeNode);
                    treeNode = treeNode.rightChild;
                }
            }
        }
    }

最后再給大家介紹一下層序遍歷

具體步驟如下：

1.首先申請(qǐng)一個(gè)新的隊(duì)列，記為queue；

2.將頭結(jié)點(diǎn)head壓入queue中；

3.每次從queue中出隊(duì)，記為node，然后打印node值，如果node左孩子不為空，則將左孩子入隊(duì)；如果node的右孩子不為空，則將右孩子入隊(duì)；

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

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

public static void levelOrder(TreeNode root){
        LinkedList<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while(!queue.isEmpty()){
            root = queue.pop();
            System.out.print(root.data+" ");
            if(root.leftChild!=null) queue.add(root.leftChild);
            if(root.rightChild!=null) queue.add(root.rightChild);
        }
    }