快捷導(dǎo)航

Java開發(fā)深入分析講解二叉樹的遞歸和非遞歸遍歷方法

更新時(shí)間：2022年05月16日 10:17:50 作者：有什么奇怪！

樹是一種重要的非線性數(shù)據(jù)結(jié)構(gòu)，直觀地看，它是數(shù)據(jù)元素（在樹中稱為結(jié)點(diǎn)）按分支關(guān)系組織起來的結(jié)構(gòu)，很象自然界中的樹那樣。樹結(jié)構(gòu)在客觀世界中廣泛存在，如人類社會(huì)的族譜和各種社會(huì)組織機(jī)構(gòu)都可用樹形象表示，本篇介紹二叉樹的遞歸與非遞歸遍歷的方法

前言

二叉樹的遍歷方法分為前序遍歷，中序遍歷，后續(xù)遍歷，層序遍歷。

1.遞歸遍歷

對于遞歸，就不得不說遞歸三要素：以前序遍歷為例

遞歸入?yún)?shù)和返回值

因?yàn)橐蛴〕銮靶虮闅v節(jié)點(diǎn)的數(shù)值，所以參數(shù)里需要傳入List在放節(jié)點(diǎn)的數(shù)值，除了這一點(diǎn)就不需要在處理什么數(shù)據(jù)了也不需要有返回值，所以遞歸函數(shù)返回類型就是void，代碼如下：

public void preorder(TreeNode root, List<Integer> result)

確定終止條件

在遞歸的過程中，如何算是遞歸結(jié)束了呢，當(dāng)然是當(dāng)前遍歷的節(jié)點(diǎn)是空了，那么本層遞歸就要要結(jié)束了，所以如果當(dāng)前遍歷的這個(gè)節(jié)點(diǎn)是空，就直接return

if (root == null) return;

單層循環(huán)邏輯

前序遍歷是中左右的循序，所以在單層遞歸的邏輯，是要先取中節(jié)點(diǎn)的數(shù)值，代碼如下：

result.add(root.val);
preorder(root.left, result);
preorder(root.right, result);

// 前序遍歷·遞歸·LC144_二叉樹的前序遍歷
class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<Integer>();
        preorder(root, result);
        return result;
    }
    public void preorder(TreeNode root, List<Integer> result) {
        if (root == null) {
            return;
        }
        result.add(root.val);//先保存中間節(jié)點(diǎn)
        preorder(root.left, result); //處理左邊節(jié)點(diǎn)
        preorder(root.right, result); //處理右邊節(jié)點(diǎn)
    }
}
// 中序遍歷·遞歸·LC94_二叉樹的中序遍歷
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        inorder(root, res);
        return res;
    }
    void inorder(TreeNode root, List<Integer> list) {
        if (root == null) {
            return;
        }
        inorder(root.left, list); //先處理左邊節(jié)點(diǎn)
        list.add(root.val);       //保存中間當(dāng)前的節(jié)點(diǎn)
        inorder(root.right, list);//先處理右邊節(jié)點(diǎn)
    }
}
// 后序遍歷·遞歸·LC145_二叉樹的后序遍歷
class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        postorder(root, res);
        return res;
    }
    void postorder(TreeNode root, List<Integer> list) {
        if (root == null) {
            return;
        }
        postorder(root.left, list);  //先處理左邊節(jié)點(diǎn)
        postorder(root.right, list); //再處理右邊節(jié)點(diǎn)
        list.add(root.val);          //保存最后  
    }
}

2.非迭代遍歷

//前序遍歷
class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        Stack<TreeNode> stack = new Stack();
        if (root == null) return res;
        stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            res.add(node.val);
            if (node.right != null) { //先將右孩子入棧，因?yàn)樗谧詈?
                stack.push(node.right);
            }
            if (node.left != null) { //左孩子入棧再出棧
                stack.push(node.left);
            }
        }
        return res;
    }
}
//中序遍歷
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        if (root == null) return res;
        Stack<TreeNode> stack = new Stack();
        TreeNode cur = root;
        while (cur != null || !stack.isEmpty()) {
            //如果可以，一直往左下探
            if (cur != null) {
                stack.push(cur);
                cur = cur.left;
            } else {
                cur = stack.pop(); //彈出來的肯定是葉子節(jié)點(diǎn)或中間節(jié)點(diǎn)
                res.add(cur.val); //將這個(gè)節(jié)點(diǎn)加入list
                cur = cur.right; //查看當(dāng)前節(jié)點(diǎn)是否有右節(jié)點(diǎn)，如果右，肯定是中間節(jié)點(diǎn)，如果沒有，就是葉子節(jié)點(diǎn)，繼續(xù)彈出就可以
            }
        }
        return res;
    }
}
//后序遍歷
//再來看后序遍歷，先序遍歷是中左右，后續(xù)遍歷是左右中，那么我們只需要調(diào)整一下先序遍歷的代碼順序，就變成中右左的遍歷順序，然后在反轉(zhuǎn)result數(shù)組，輸出的結(jié)果順序就是左右中
class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        if (root == null) return res;
        Stack<TreeNode> stack = new Stack();
        stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            res.add(node.val);
            if (node.left != null) stack.push(node.left); // 相對于前序遍歷，這更改一下入棧順序 （空節(jié)點(diǎn)不入棧）
            if (node.right != null) stack.push(node.right);// 空節(jié)點(diǎn)不入棧 
        }
        Collections.reverse(res); // 將結(jié)果反轉(zhuǎn)之后就是左右中的順序了
        return res;
    }
}

3.二叉樹的統(tǒng)一迭代法

//前序遍歷
class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> result = new LinkedList<>();
        Stack<TreeNode> st = new Stack<>();
        if (root != null) st.push(root);
        while (!st.empty()) {
            TreeNode node = st.peek();
            if (node != null) {
                st.pop(); // 將該節(jié)點(diǎn)彈出，避免重復(fù)操作，下面再將右中左節(jié)點(diǎn)添加到棧中
                if (node.right!=null) st.push(node.right);  // 添加右節(jié)點(diǎn)（空節(jié)點(diǎn)不入棧）
                if (node.left!=null) st.push(node.left);    // 添加左節(jié)點(diǎn)（空節(jié)點(diǎn)不入棧）
                st.push(node);                          // 添加中節(jié)點(diǎn)
                st.push(null); // 中節(jié)點(diǎn)訪問過，但是還沒有處理，加入空節(jié)點(diǎn)做為標(biāo)記。
            } else { // 只有遇到空節(jié)點(diǎn)的時(shí)候，才將下一個(gè)節(jié)點(diǎn)放進(jìn)結(jié)果集
                st.pop();           // 將空節(jié)點(diǎn)彈出
                node = st.peek();    // 重新取出棧中元素
                st.pop();
                result.add(node.val); // 加入到結(jié)果集
            }
        }
        return result;
    }
}
//中序遍歷
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> result = new LinkedList<>();
        Stack<TreeNode> st = new Stack<>();
        if (root != null) st.push(root);
        while (!st.empty()) {
            TreeNode node = st.peek();
            if (node != null) {
                st.pop(); // 將該節(jié)點(diǎn)彈出，避免重復(fù)操作，下面再將右中左節(jié)點(diǎn)添加到棧中
                if (node.right!=null) st.push(node.right);  // 添加右節(jié)點(diǎn)（空節(jié)點(diǎn)不入棧）
                st.push(node);                          // 添加中節(jié)點(diǎn)
                st.push(null); // 中節(jié)點(diǎn)訪問過，但是還沒有處理，加入空節(jié)點(diǎn)做為標(biāo)記。
                if (node.left!=null) st.push(node.left);    // 添加左節(jié)點(diǎn)（空節(jié)點(diǎn)不入棧）
            } else { // 只有遇到空節(jié)點(diǎn)的時(shí)候，才將下一個(gè)節(jié)點(diǎn)放進(jìn)結(jié)果集
                st.pop();           // 將空節(jié)點(diǎn)彈出
                node = st.peek();    // 重新取出棧中元素
                st.pop();
                result.add(node.val); // 加入到結(jié)果集
            }
        }
        return result;
    }
}
//后序遍歷
class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> result = new LinkedList<>();
        Stack<TreeNode> st = new Stack<>();
        if (root != null) st.push(root);
        while (!st.empty()) {
            TreeNode node = st.peek();
            if (node != null) {
                st.pop(); // 將該節(jié)點(diǎn)彈出，避免重復(fù)操作，下面再將右中左節(jié)點(diǎn)添加到棧中
                st.push(node);                          // 添加中節(jié)點(diǎn)
                st.push(null); // 中節(jié)點(diǎn)訪問過，但是還沒有處理，加入空節(jié)點(diǎn)做為標(biāo)記。
                if (node.right!=null) st.push(node.right);  // 添加右節(jié)點(diǎn)（空節(jié)點(diǎn)不入棧）
                if (node.left!=null) st.push(node.left);    // 添加左節(jié)點(diǎn)（空節(jié)點(diǎn)不入棧）         
            } else { // 只有遇到空節(jié)點(diǎn)的時(shí)候，才將下一個(gè)節(jié)點(diǎn)放進(jìn)結(jié)果集
                st.pop();           // 將空節(jié)點(diǎn)彈出
                node = st.peek();    // 重新取出棧中元素
                st.pop();
                result.add(node.val); // 加入到結(jié)果集
            }
        }
        return result;
    }
}

到此這篇關(guān)于Java開發(fā)深入分析講解二叉樹的遞歸和非遞歸遍歷方法的文章就介紹到這了,更多相關(guān)Java二叉樹的遞歸內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: