二叉樹遍歷小結

vvpale 發布于2019-08-16 10:37 / 2444人閱讀

摘要：對于任一重合元素，保證所在兩個局部遍歷有序，保證實現整體遍歷有序重合元素所在局部局部全部有序，遍歷該元素并出棧局部未全部有序，將未有序局部元素全部入棧。

二叉樹遍歷小結 聲明

文章均為本人技術筆記，轉載請注明出處：
[1] https://segmentfault.com/u/yzwall
[2] blog.csdn.net/j_dark/

0 二叉樹遍歷概述

二叉樹遍歷：按照既定序，對每個節點僅訪問一次；
二叉樹非遞歸遍歷思想：參考這篇博文，核心思想是存在重合元素的局部有序保證整體有序，由于二叉樹的結構特點，二叉樹中的每個節點（除根節點和葉子節點）均屬于兩個局部的重合元素。對于任一重合元素，保證所在兩個局部遍歷有序，保證實現整體遍歷有序；

重合元素所在局部：

局部全部有序，遍歷該元素并出棧；

局部未全部有序，將未有序局部元素全部入棧。由于棧是LIFO，局部元素按照逆序入棧；

二叉樹節點TreeNode聲明

public class TreeNode {
    public int val;
    public TreeNode left, right;
    public TreeNode(int val) {
        this.val = val;
        this.left = this.right = null;
    }
}

1 前序遍歷

lintcode 二叉樹的前序遍歷

1.1 非遞歸實現

public class Solution {
    private class Pair {
        public TreeNode node;
        public boolean isVisited;
        public Pair(TreeNode node, boolean isVisited) {
            this.node = node;
            this.isVisited = isVisited;
        }
    }
    
    public ArrayList preorderTraversal(TreeNode root) {
        ArrayList list = new ArrayList();
        if (root == null) {
            return list;
        }
        
        ArrayDeque stack = new ArrayDeque();
        stack.push(new Pair(root, false));
        while (!stack.isEmpty()) {
            Pair top = stack.pop();
            // 重合節點完成所有局部有序，彈出
            if (top.isVisited) {
                list.add(top.node.val);
            } else {
                // reverse: right -> left -> root
                if (top.node.right != null) {
                    stack.push(new Pair(top.node.right, false));
                }               
                if (top.node.left != null) {
                    stack.push(new Pair(top.node.left, false));
                }
                stack.push(new Pair(top.node, true));
            }
        }
        return list;
    }
}

1.2 遞歸實現

public class Solution {
    public ArrayList preorderTraversal(TreeNode root) {
        ArrayList list = new ArrayList();
        if (root == null) {
            return list;
        }
        traverse(list, root);
        return list;
    }
    
    private void traverse(ArrayListlist, TreeNode root) {
        if (root == null) {
            return;
        }
        list.add(root.val);
        traverse(list, root.left);
        traverse(list, root.right);
    }
}

2 中序遍歷

lintcode 二叉樹的中序遍歷

2.1 非遞歸實現

public class Solution {
    private class Pair {
        public TreeNode node;
        public boolean isVisited;
        public Pair(TreeNode node, boolean isVisited) {
            this.node = node;
            this.isVisited = isVisited;
        }
    }
    
    public ArrayList inorderTraversal(TreeNode root) {
        ArrayList list = new ArrayList();
        if (root == null) {
            return list;
        }
        
        ArrayDeque stack = new ArrayDeque();
        stack.push(new Pair(root, false));
        while (!stack.isEmpty()) {
            Pair top = stack.pop();
            if (top.isVisited) {
                list.add(top.node.val);
            } else {
                // reverse: right -> root -> left
                if (top.node.right != null) {
                     stack.push(new Pair(top.node.right, false));
                }
                stack.push(new Pair(top.node, true));
                if (top.node.left != null) {
                     stack.push(new Pair(top.node.left, false));
                }
            }
        }
        return list;
    }
}

2.2 遞歸實現

public class Solution {
    public ArrayList inorderTraversal(TreeNode root) {
        ArrayList list = new ArrayList();
        if (root == null) {
            return list;
        }
        traverse(list, root);
        return list;
    }
    
    private void traverse(ArrayListlist, TreeNode root) {
        if (root == null) {
            return;
        }
        traverse(list, root.left);
        list.add(root.val);
        traverse(list, root.right);
    }
}

3 后序遍歷

lintcode 二叉樹的后序遍歷

3.1 非遞歸實現

public class Solution {
    private class Pair {
        public TreeNode node;
        public boolean isVisited;
        public Pair(TreeNode node, boolean isVisited) {
            this.node = node;
            this.isVisited = isVisited;
        }
    }
    
    public ArrayList postorderTraversal(TreeNode root) {
        ArrayList list = new ArrayList();
        if (root == null) {
            return list;
        }
        
        ArrayDeque stack = new ArrayDeque();
        stack.push(new Pair(root, false));
        while (!stack.isEmpty()) {
            Pair top = stack.pop();
            if (top.isVisited) {
                list.add(top.node.val);
            } else {
                // reverse: root -> right -> left
                stack.push(new Pair(top.node, true));
                if (top.node.right != null) {
                     stack.push(new Pair(top.node.right, false));
                }
                if (top.node.left != null) {
                     stack.push(new Pair(top.node.left, false));
                }
            }
        }

        return list;
    }
}

3.2 遞歸實現

public class Solution {
    public ArrayList postorderTraversal(TreeNode root) {
        ArrayList list = new ArrayList();
        if (root == null) {
            return list;
        }
        traverse(list, root);
        return list;
    }
    
    private void traverse(ArrayList list, TreeNode root) {
        if (root == null) {
            return;
        }
        traverse(list, root.left);
        traverse(list, root.right);
        list.add(root.val);
    }
}

4 層序遍歷

lintcode 二叉樹的層序遍歷，BFS按層遍歷實現

public class Solution {
    public ArrayList> levelOrder(TreeNode root) {
        ArrayDeque queue = new ArrayDeque();
        ArrayList> list = new ArrayList>();
        if (root == null) {
            return list;
        }
        queue.offer(root);
        while (!queue.isEmpty()) {
            int level = queue.size();
            ArrayList levelList = new ArrayList();
            // 按層BFS遍歷
            for (int i = 0; i < level; i++) {
                TreeNode head = queue.poll();
                levelList.add(head.val);
                if (head.left != null) {
                    queue.offer(head.left);
                } 
                if (head.right != null) {
                    queue.offer(head.right);
                }
            }
            list.add(levelList);
        }
        return list;
    }
}

云服務器 GPU云服務器二叉樹遍歷二叉樹的遍歷 JS二叉樹遍歷非遞歸二叉樹遍歷

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/70127.html

學習數據結構與算法之二叉搜索樹

摘要：二叉搜索樹是二叉樹的一種，其特征是左側子節點存儲比父節點小的值，右側子節點存儲比父節點大或等于父節點的值。實現和這個兩個方法其實挺簡單的，最小的節點就在二叉搜索樹的最左反之，最大的就在最右。本系列所有文章：第一篇文章：學習數據結構與算法之棧與隊列第二篇文章：學習數據結構與算法之鏈表第三篇文章：學習數據結構與算法之集合第四篇文章：學習數據結構與算法之字典和散列表第五篇文章：學習數據結構...

denson 2019-08-21 11:54 評論0 收藏0
計算機二級考試-數據結構-模擬試題

摘要：數據結構試題前言這里是數據結構系列文章，主要介紹計算機二級考試中的涉及到數據結構的知識點數據結構在計算機科學中處處都有存在，例如編譯系統要使用棧散列表語法樹等操作系統要使用隊列存儲管理表目錄樹等等。數據結構試題前言這里是數據結構系列文章，主要介紹計算機二級考試中的涉及到數據結構的知識點 /數據結構在計算...

不知名網友 2021-11-26 11:05 評論0 收藏0
Java數據結構與算法——二叉樹及操作(包括二叉樹遍歷)

摘要：本篇主要介紹二叉樹的概念二叉樹的表示二叉樹的操作三種遍歷方式實現求二叉樹的子樹求節點的父節點二叉樹高度，可能是考試中的，也可能是面試中的。通常二叉樹的遍歷根據根節點的遍歷次序分為先根遍歷中根遍歷后根遍歷。聲明：碼字不易，轉載請注明出處，歡迎文章下方討論交流。前言：Java數據結構與算法專題會不定時更新，歡迎各位讀者監督。本篇主要介紹二叉樹的概念、二叉樹的表示、二叉樹的操作（三種遍歷...

muddyway 2019-08-16 11:15 評論0 收藏0
js數據結構和算法（三）二叉樹

摘要：同樣結點樹的二叉樹，完全二叉樹的深度最小。二叉樹每個結點最多有兩個孩子，所以為它設計一個數據域和兩個指針域是比較自然的想法，我們稱這樣的鏈表叫做二叉鏈表。二叉樹的概念二叉樹（Binary Tree）是n（n>=0）個結點的有限集合，該集合或者為空集（空二叉樹），或者由一個根結點和兩棵互不相交的、分別稱為根結點的左子樹和右子樹的二叉樹組成。 showImg(https://seg...

DesGemini 2019-08-21 10:20 評論0 收藏0