二叉树遍历（前序、中序、后序、层次、深度优先、广度优先遍历）

骑猪看日落 2023-07-10 08:30 20阅读 0赞

**目录**

*  [二叉树][Link 1]
    
     *  [概念][Link 2]
     *  [四种基本的遍历思想][Link 3]
     *  [一、前序遍历][Link 4]
     *  [二、中序遍历][Link 5]
     *  [三、后序遍历][Link 6]
     *  [四、层次遍历][Link 7]
     *  [五、深度优先遍历][Link 8]
     *  [六、后序遍历的简单思路][Link 9]

--------------------

转载：[二叉树遍历（前序、中序、后序、层次、深度优先、广度优先遍历）][Link 10]

[【数据结构和算法】全面剖析树的各类遍历方法][Link 11]

[回到顶部][Link 12]

## 二叉树 ##

### 概念 ###

二叉树是一种非常重要的数据结构，非常多其他数据结构都是基于二叉树的基础演变而来的。对于二叉树，有深度遍历和广度遍历，深度遍历有前序、中序以及后序三种遍历方法，广度遍历即我们寻常所说的层次遍历。由于树的定义本身就是递归定义，因此採用递归的方法去实现树的三种遍历不仅easy理解并且代码非常简洁，而对于广度遍历来说，须要其他数据结构的支撑。比方堆了。所以。对于一段代码来说，可读性有时候要比代码本身的效率要重要的多。

### 四种基本的遍历思想 ###

前序遍历：根结点 ---> 左子树 ---> 右子树

中序遍历：左子树---> 根结点 ---> 右子树

后序遍历：左子树 ---> 右子树 ---> 根结点

层次遍历：仅仅需按层次遍历就可以

比如。求以下二叉树的各种遍历

![format_png][]

![format_png 1][]

前序遍历：1  2  4  5  7  8  3  6

中序遍历：4  2  7  5  8  1  3  6

后序遍历：4  7  8  5  2  6  3  1

层次遍历：1  2  3  4  5  6  7  8

### 一、前序遍历 ###

1）依据上文提到的遍历思路：根结点 ---> 左子树 ---> 右子树，非常easy写出递归版本号：

![复制代码][aHR0cHM6Ly9jb21tb24uY25ibG9ncy5jb20vaW1hZ2VzL2NvcHljb2RlLmdpZg]

public void preOrderTraverse1(TreeNode root) {  
            if (root != null) {  
                System.out.print(root.val+"  ");  
                preOrderTraverse1(root.left);  
                preOrderTraverse1(root.right);  
            }  
        }

![复制代码][aHR0cHM6Ly9jb21tb24uY25ibG9ncy5jb20vaW1hZ2VzL2NvcHljb2RlLmdpZg]

2）如今讨论非递归的版本号：

依据前序遍历的顺序，优先訪问根结点。然后在訪问左子树和右子树。所以。对于随意结点node。第一部分即直接訪问之，之后在推断左子树是否为空，不为空时即反复上面的步骤，直到其为空。若为空。则须要訪问右子树。注意。在訪问过左孩子之后。须要反过来訪问其右孩子。所以，须要栈这样的数据结构的支持。对于随意一个结点node，详细过程例如以下：

a)訪问之，并把结点node入栈。当前结点置为左孩子；

b)推断结点node是否为空，若为空。则取出栈顶结点并出栈，将右孩子置为当前结点；否则反复a)步直到当前结点为空或者栈为空（能够发现栈中的结点就是为了訪问右孩子才存储的）

代码例如以下：

![复制代码][aHR0cHM6Ly9jb21tb24uY25ibG9ncy5jb20vaW1hZ2VzL2NvcHljb2RlLmdpZg]

public void preOrderTraverse2(TreeNode root) {  
            Stack<TreeNode> stack = new Stack<>();  
            TreeNode pNode = root;  
            while (pNode != null || !stack.isEmpty()) {  
                if (pNode != null) {  
                    System.out.print(pNode.val+"  ");  
                    stack.push(pNode);  
                    pNode = pNode.left;  
                } else { //pNode == null && !stack.isEmpty()  
                    TreeNode node = stack.pop();  
                    pNode = node.right;  
                }  
            }  
        }

![复制代码][aHR0cHM6Ly9jb21tb24uY25ibG9ncy5jb20vaW1hZ2VzL2NvcHljb2RlLmdpZg]

### 二、中序遍历 ###

1)依据上文提到的遍历思路：左子树 ---> 根结点 ---> 右子树，非常easy写出递归版本号：

![复制代码][aHR0cHM6Ly9jb21tb24uY25ibG9ncy5jb20vaW1hZ2VzL2NvcHljb2RlLmdpZg]

public void inOrderTraverse1(TreeNode root) {  
            if (root != null) {  
                inOrderTraverse1(root.left);  
                System.out.print(root.val+"  ");  
                inOrderTraverse1(root.right);  
            }  
        }

![复制代码][aHR0cHM6Ly9jb21tb24uY25ibG9ncy5jb20vaW1hZ2VzL2NvcHljb2RlLmdpZg]

2）非递归实现，有了上面前序的解释，中序也就比較简单了。同样的道理。仅仅只是訪问的顺序移到出栈时。代码例如以下：

![复制代码][aHR0cHM6Ly9jb21tb24uY25ibG9ncy5jb20vaW1hZ2VzL2NvcHljb2RlLmdpZg]

public void inOrderTraverse2(TreeNode root) {  
            Stack<TreeNode> stack = new Stack<>();  
            TreeNode pNode = root;  
            while (pNode != null || !stack.isEmpty()) {  
                if (pNode != null) {  
                    stack.push(pNode);  
                    pNode = pNode.left;  
                } else { //pNode == null && !stack.isEmpty()  
                    TreeNode node = stack.pop();  
                    System.out.print(node.val+"  ");  
                    pNode = node.right;  
                }  
            }  
        }

![复制代码][aHR0cHM6Ly9jb21tb24uY25ibG9ncy5jb20vaW1hZ2VzL2NvcHljb2RlLmdpZg]

### 三、后序遍历 ###

1）依据上文提到的遍历思路：左子树 ---> 右子树 ---> 根结点。非常easy写出递归版本号：

![复制代码][aHR0cHM6Ly9jb21tb24uY25ibG9ncy5jb20vaW1hZ2VzL2NvcHljb2RlLmdpZg]

public void postOrderTraverse1(TreeNode root) {  
            if (root != null) {  
                postOrderTraverse1(root.left);  
                postOrderTraverse1(root.right);  
                System.out.print(root.val+"  ");  
            }  
        }

![复制代码][aHR0cHM6Ly9jb21tb24uY25ibG9ncy5jb20vaW1hZ2VzL2NvcHljb2RlLmdpZg]

2）

后序遍历的非递归实现是三种遍历方式中最难的一种。由于在后序遍历中，要保证左孩子和右孩子都已被訪问而且左孩子在右孩子前訪问才干訪问根结点，这就为流程的控制带来了难题。以下介绍两种思路。

第一种思路：对于任一结点P，将其入栈，然后沿其左子树一直往下搜索。直到搜索到没有左孩子的结点，此时该结点出如今栈顶，可是此时不能将其出栈并訪问，因此其右孩子还为被訪问。

所以接下来依照同样的规则对其右子树进行同样的处理，当訪问完其右孩子时。该结点又出如今栈顶，此时能够将其出栈并訪问。这样就保证了正确的訪问顺序。能够看出，在这个过程中，每一个结点都两次出如今栈顶，仅仅有在第二次出如今栈顶时，才干訪问它。因此须要多设置一个变量标识该结点是否是第一次出如今栈顶。

![复制代码][aHR0cHM6Ly9jb21tb24uY25ibG9ncy5jb20vaW1hZ2VzL2NvcHljb2RlLmdpZg]

void postOrder2(BinTree *root)    //非递归后序遍历
    {
        stack<BTNode*> s;
        BinTree *p=root;
        BTNode *temp;
        while(p!=NULL||!s.empty())
        {
            while(p!=NULL)              //沿左子树一直往下搜索。直至出现没有左子树的结点 
            {
                BTNode *btn=(BTNode *)malloc(sizeof(BTNode));
                btn->btnode=p;
                btn->isFirst=true;
                s.push(btn);
                p=p->lchild;
            }
            if(!s.empty())
            {
                temp=s.top();
                s.pop();
                if(temp->isFirst==true)     //表示是第一次出如今栈顶 
                 {
                    temp->isFirst=false;
                    s.push(temp);
                    p=temp->btnode->rchild;    
                }
                else                        //第二次出如今栈顶 
                 {
                    cout<<temp->btnode->data<<" ";
                    p=NULL;
                }
            }
        }    
    }

![复制代码][aHR0cHM6Ly9jb21tb24uY25ibG9ncy5jb20vaW1hZ2VzL2NvcHljb2RlLmdpZg]

另外一种思路：要保证根结点在左孩子和右孩子訪问之后才干訪问，因此对于任一结点P。先将其入栈。假设P不存在左孩子和右孩子。则能够直接訪问它；或者P存在左孩子或者右孩子。可是其左孩子和右孩子都已被訪问过了。则相同能够直接訪问该结点。若非上述两种情况。则将P的右孩子和左孩子依次入栈。这样就保证了每次取栈顶元素的时候，左孩子在右孩子前面被訪问。左孩子和右孩子都在根结点前面被訪问。

![复制代码][aHR0cHM6Ly9jb21tb24uY25ibG9ncy5jb20vaW1hZ2VzL2NvcHljb2RlLmdpZg]

void postOrder3(BinTree *root)     //非递归后序遍历
    {
        stack<BinTree*> s;
        BinTree *cur;                      //当前结点 
        BinTree *pre=NULL;                 //前一次訪问的结点 
        s.push(root);
        while(!s.empty())
        {
            cur=s.top();
            if((cur->lchild==NULL&&cur->rchild==NULL)||
               (pre!=NULL&&(pre==cur->lchild||pre==cur->rchild)))
            {
                cout<<cur->data<<" ";  //假设当前结点没有孩子结点或者孩子节点都已被訪问过 
                  s.pop();
                pre=cur; 
            }
            else
            {
                if(cur->rchild!=NULL)
                    s.push(cur->rchild);
                if(cur->lchild!=NULL)    
                    s.push(cur->lchild);
            }
        }    
    }

![复制代码][aHR0cHM6Ly9jb21tb24uY25ibG9ncy5jb20vaW1hZ2VzL2NvcHljb2RlLmdpZg]

### 四、层次遍历 ###

层次遍历的代码比較简单。仅仅须要一个队列就可以。先在队列中增加根结点。之后对于随意一个结点来说。在其出队列的时候，訪问之。同一时候假设左孩子和右孩子有不为空的。入队列。代码例如以下：

![复制代码][aHR0cHM6Ly9jb21tb24uY25ibG9ncy5jb20vaW1hZ2VzL2NvcHljb2RlLmdpZg]

public void levelTraverse(TreeNode root) {  
            if (root == null) {  
                return;  
            }  
            LinkedList<TreeNode> queue = new LinkedList<>();  
            queue.offer(root);  
            while (!queue.isEmpty()) {  
                TreeNode node = queue.poll();  
                System.out.print(node.val+"  ");  
                if (node.left != null) {  
                    queue.offer(node.left);  
                }  
                if (node.right != null) {  
                    queue.offer(node.right);  
                }  
            }  
        }

![复制代码][aHR0cHM6Ly9jb21tb24uY25ibG9ncy5jb20vaW1hZ2VzL2NvcHljb2RlLmdpZg]

### 五、深度优先遍历 ###

事实上深度遍历就是上面的前序、中序和后序。可是为了保证与广度优先遍历相照顾，也写在这。代码也比較好理解，事实上就是前序遍历，代码例如以下：

![复制代码][aHR0cHM6Ly9jb21tb24uY25ibG9ncy5jb20vaW1hZ2VzL2NvcHljb2RlLmdpZg]

public void depthOrderTraverse(TreeNode root) {  
            if (root == null) {  
                return;  
            }  
            Stack<TreeNode> stack = new Stack<>();  
            stack.push(root);  
            while (!stack.isEmpty()) {  
                TreeNode node = stack.pop();  
                System.out.print(node.val+"  ");  
                if (node.right != null) {  
                    stack.push(node.right);  
                }  
                if (node.left != null) {  
                    stack.push(node.left);  
                }  
            }  
        }

![复制代码][aHR0cHM6Ly9jb21tb24uY25ibG9ncy5jb20vaW1hZ2VzL2NvcHljb2RlLmdpZg]

### 六、后序遍历的简单思路 ###

前序遍历的非递归版本，访问顺序依次是根节点->左子树->右子树，如果将压栈顺序改动一下，可以很容易得到根节点->右子树->左子树，观察这个顺序和后序遍历左子树->右子树->根节点正好反序。

![复制代码][aHR0cHM6Ly9jb21tb24uY25ibG9ncy5jb20vaW1hZ2VzL2NvcHljb2RlLmdpZg]

vector<int> postorderTraversal(TreeNode* root) {
        vector<int> ret;
        if(root==NULL) return ret;
        stack<TreeNode*> st;
        st.push(root);
        while(!st.empty())
        {
           TreeNode* tmp = st.top();
           ret.push_back(tmp->val);//先访问根节点
           st.pop();
           if(tmp->left!=NULL) st.push(tmp->left);//再访问左子树
           if(tmp->right!=NULL) st.push(tmp->right);//最后访问右子树
        }
        reverse(ret.begin(),ret.end());//将结果反序输出
        return ret;
    }

![复制代码][aHR0cHM6Ly9jb21tb24uY25ibG9ncy5jb20vaW1hZ2VzL2NvcHljb2RlLmdpZg]

![复制代码][aHR0cHM6Ly9jb21tb24uY25ibG9ncy5jb20vaW1hZ2VzL2NvcHljb2RlLmdpZg]

public void postOrderTraverse(Node node) {
            if (node == null) {
                return;
            }
            Node temp = node;
            Stack<Node> stack = new Stack<>();
            List<Node> nodes = new ArrayList<>();
            while (temp != null || !stack.isEmpty()) {
                if (temp != null) {
                    nodes.add(temp);
                    stack.push(temp);
                    temp = temp.rightChild;
                } else {
                    Node popNode = stack.pop();
                    temp = popNode.leftChild;
                }
            }
            
            for (int i = nodes.size() - 1; i >= 0; i--) {
                System.out.print(nodes.get(i).data + " ");
            }
        }

![复制代码][aHR0cHM6Ly9jb21tb24uY25ibG9ncy5jb20vaW1hZ2VzL2NvcHljb2RlLmdpZg]

[Link 1]: https://www.cnblogs.com/fanguangdexiaoyuer/p/10493104.html#_label0
[Link 2]: https://www.cnblogs.com/fanguangdexiaoyuer/p/10493104.html#_label0_0
[Link 3]: https://www.cnblogs.com/fanguangdexiaoyuer/p/10493104.html#_label0_1
[Link 4]: https://www.cnblogs.com/fanguangdexiaoyuer/p/10493104.html#_label0_2
[Link 5]: https://www.cnblogs.com/fanguangdexiaoyuer/p/10493104.html#_label0_3
[Link 6]: https://www.cnblogs.com/fanguangdexiaoyuer/p/10493104.html#_label0_4
[Link 7]: https://www.cnblogs.com/fanguangdexiaoyuer/p/10493104.html#_label0_5
[Link 8]: https://www.cnblogs.com/fanguangdexiaoyuer/p/10493104.html#_label0_6
[Link 9]: https://www.cnblogs.com/fanguangdexiaoyuer/p/10493104.html#_label0_7
[Link 10]: https://www.cnblogs.com/llguanli/p/7363657.html
[Link 11]: https://blog.csdn.net/terence1212/article/details/52182836
[Link 12]: https://www.cnblogs.com/fanguangdexiaoyuer/p/10493104.html#_labelTop
[format_png]: https://imgconvert.csdnimg.cn/aHR0cDovL2ltZy5ibG9nLmNzZG4ubmV0LzIwMTUwMjA0MTAxOTA0NjQ5?x-oss-process=image/format,png
[format_png 1]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly93d3cuY25ibG9ncy5jb20vbGxndWFubGkvcC83MzYzNjU3Lmh0bWw?x-oss-process=image/format,png
[aHR0cHM6Ly9jb21tb24uY25ibG9ncy5jb20vaW1hZ2VzL2NvcHljb2RlLmdpZg]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9jb21tb24uY25ibG9ncy5jb20vaW1hZ2VzL2NvcHljb2RlLmdpZg

发表评论取消回复

表情：

评论列表（有 0 条评论，20人围观）

还没有评论，来说两句吧...

相关阅读

相关二叉树的前序遍历、中序遍历、后序遍历

一.前序遍历前序遍历按照“根结点-左子节点-右子节点”的顺序进行访问。 ![ffd12a9aa33b47b4b5cbf77bf74ce1e6.png][] 二.中

╰+攻爆jí腚メ/ 2024年03月23日 13:16/ 0 赞/ 75 阅读

相关二叉树遍历（前序、中序、后序、层次、深度优先、广度优先遍历）

目录 [二叉树][Link 1] [概念][Link 2] [四种基本的遍历思想][Link 3] [一、前序遍历]

骑猪看日落/ 2023年07月10日 08:30/ 0 赞/ 21 阅读

相关二叉树的前序遍历、中序遍历、后序遍历

Python代码实现二叉树以下的实现思想是借鉴的尚硅谷-韩顺平数据结构与算法的java实现，[韩顺平老师视频地址-https://www.bilibili.com/vi

╰半夏微凉°/ 2023年03月13日 05:54/ 0 赞/ 172 阅读

相关二叉树的前序遍历中序遍历后序遍历

树的遍历一般是从左至右，按照根结点在前中后的顺序分为了前序遍历，中序遍历和后序遍历前序遍历: 根结点 --》左节点--》右节点

淩亂°似流年/ 2022年12月25日 13:53/ 0 赞/ 272 阅读

相关前序遍历、中序遍历、后序遍历、层次遍历

public class Tree { public static void main(String[] args) { TreeN

布满荆棘的人生/ 2022年10月27日 00:30/ 0 赞/ 330 阅读

相关二叉树的遍历（前序遍历、中序遍历、后序遍历）

二叉树在计算机科学中，二叉树是每个节点最多有两个子树的树结构。通常子树被称作左子树和右子树。树是一种重要的非线性数据结构，直观地看，它是数据元素（在树中称为结

短命女/ 2022年07月15日 16:07/ 0 赞/ 368 阅读

相关二叉树遍历（前序、中序、后序、层次、深度优先、广度优先遍历）

二叉树是一种非常重要的[数据结构][Link 1]，很多其它数据结构都是基于二叉树的基础演变而来的。对于二叉树，有深度遍历和广度遍历，深度遍历有前序、中序以及后序三种遍历方法，

红太狼/ 2022年07月11日 13:25/ 0 赞/ 190 阅读

相关树的基本概念和遍历规则数据结构和算法二叉树遍历（前序、中序、后序、层次、深度优先、广度优先遍历）

[zsychanpin][] [博客园][Link 1] [首页][zsychanpin] [新随笔][Link 2] [联系][Link 3]

深藏阁楼爱情的钟/ 2022年04月10日 05:52/ 0 赞/ 181 阅读

相关二叉树遍历（前序、中序、后序、层次、深度优先、广度优先遍历）

二叉树是一种非常重要的[数据结构][Link 1]，非常多其他数据结构都是基于二叉树的基础演变而来的。对于二叉树，有深度遍历和广度遍历，深度遍历有前序、中序以及后序三种遍历方法

「爱情、让人受尽委屈。」/ 2022年03月18日 03:44/ 0 赞/ 199 阅读

相关二叉树前序遍历，中序遍历，后序遍历以及层次遍历实现

一、二叉树的层次遍历　　1. 非递归实现：利用队列，存储每一层次的结点进队列，再通过出队操作完成层次遍历。代码： 1 / 2 Definitio

青旅半醒/ 2021年10月19日 03:32/ 0 赞/ 458 阅读