Java二叉樹的四種遍歷（遞歸與非遞歸）

更新時(shí)間：2021年10月07日 08:37:45 作者：funtrin

這篇文章小編給大家分享的是Java二叉樹的四種遍歷，主要是遞歸與非遞歸，下面文章加u來詳細(xì)介紹，感興趣的小伙伴一起來學(xué)習(xí)吧

一、先序遍歷與后序遍歷

先序遍歷根節(jié)點(diǎn)，再遍歷左子樹，再遍歷右子樹。

后序遍歷先遍歷左子樹，再遍歷右子樹，再遍歷根節(jié)點(diǎn)。

先序遍歷遞歸實(shí)現(xiàn)：

public static void preOrderByRecursion(TreeNode root) {
    // 打印節(jié)點(diǎn)值
    System.out.println(root.value);
    preOrder(root.left);
    preOrder(root.right);
}

先序遍歷的非遞歸實(shí)現(xiàn)：

非遞歸實(shí)現(xiàn)需要借助棧這樣一個(gè)數(shù)據(jù)結(jié)構(gòu)，實(shí)際上遞歸實(shí)現(xiàn)也是依靠棧，只不過是隱式的。

先將根節(jié)點(diǎn)壓入棧中。
彈出棧中的節(jié)點(diǎn)，將彈出節(jié)點(diǎn)的右子節(jié)點(diǎn)壓入棧中，再將彈出節(jié)點(diǎn)的左子樹壓入棧中。
重復(fù)步驟2，直到棧為空。

public static void preOrder(TreeNode root) {
    if (root == null) {
        return;
    }
    Stack<TreeNode> stack = new Stack<>();
    stack.push(root);
    while (!stack.empty()) {
        TreeNode node = stack.pop();
        // 打印節(jié)點(diǎn)值
        System.out.print(node.value + " ");
        if (node.right != null) {
            stack.push(node.right);
        }
        if (node.left != null) {
            stack.push(node.left);
        }
    }
}

后序遍歷遞歸實(shí)現(xiàn)：先序遍歷反過來，就不贅述了。

public static void postOrderByRecursion(TreeNode root) {
    postOrderByRecursion(root.left);
    postOrderByRecursion(root.right);
    System.out.println(root.value);
}

后序遍歷非遞歸實(shí)現(xiàn)：后序遍歷就是先序遍歷反過來，所以需要兩個(gè)棧，多出來的棧用來反向輸出。

public static void postOrder(TreeNode root) {
    if (root == null) {
        return;
    }
    Stack<TreeNode> s1 = new Stack<>();
    Stack<TreeNode> s2 = new Stack<>();
    s1.push(root);
    while (!s1.empty()) {
        TreeNode node = s1.pop();
        s2.push(node);
        if (node.left != null) {
            s1.push(node.left);
        }
        if (node.right != null) {
            s1.push(node.right);
        }
    }
    while (!s2.empty()) {
        System.out.println(s2.pop().value);
    }
}

二、中序遍歷

中序遍歷先遍歷左子樹，再遍歷根節(jié)點(diǎn)，再遍歷右子樹。

遞歸遍歷：

public static void inOrderByRecursion(TreeNode root) {
    if (root == null) {
        return;
    }
    inOrderByRecursion(root.left);
    // 打印節(jié)點(diǎn)值
    System.out.println(root.value);
    inOrderByRecursion(root.right);
}

非遞歸遍歷：

將二叉樹的左側(cè)“邊”從上到下依次壓入棧中。
從棧中彈出節(jié)點(diǎn)
對(duì)以彈出節(jié)點(diǎn)的右子節(jié)點(diǎn)為根節(jié)點(diǎn)的子樹，重復(fù)步驟1。
重復(fù)2、3步驟，直到棧為空。

public static void inOrder(TreeNode root) {
    if (root == null) {
        return;
    }
    Stack<TreeNode> stack = new Stack<>();
    TreeNode cur = root;

    while (cur != null) {
        stack.push(cur);
        cur = cur.left;
    }

    while (!stack.empty()) {
        TreeNode node = stack.pop();
        System.out.println(node.value);
        cur = node.right;
        while (cur != null) {
            stack.push(cur);
            cur = cur.left;
        }
    }
}

三、層序遍歷

層序遍歷顧名思義就是一層一層，從左到右的遍歷二叉樹。需要用到隊(duì)列這一數(shù)據(jù)結(jié)構(gòu)。

將根節(jié)點(diǎn)推入隊(duì)列。
從隊(duì)列中取出一個(gè)節(jié)點(diǎn)。
先將取出節(jié)點(diǎn)的左子節(jié)點(diǎn)推入隊(duì)列，再將取出節(jié)點(diǎn)的右子節(jié)點(diǎn)推入隊(duì)列。
重復(fù)2、3步驟直到隊(duì)列中無節(jié)點(diǎn)可取。

public static void floorOrder(TreeNode root) {
    if (root == null) {
        return;
    }
    Queue<TreeNode> queue = new LinkedList<>();
    queue.add(root);
    while (!queue.isEmpty()) {
        TreeNode node = queue.poll();
        System.out.println(node.value);
        if (node.left != null) {
            queue.add(node.left);
        }
        if (node.right != null) {
            queue.add(node.right);
        }
    }
}

到此這篇關(guān)于Java二叉樹的四種遍歷（遞歸與非遞歸）的文章就介紹到這了,更多相關(guān)Java二叉樹的四種遍歷內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: