[数据结构]二叉树的前中后序遍历(递归+迭代实现) - Amαdeus
source link: https://www.cnblogs.com/MAKISE004/p/17073925.html
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
二叉树的遍历
主要的三种遍历方式
二叉树主要的遍历方式有前序遍历、中序遍历和后序遍历。
（1）前序遍历：根节点-->左子树-->右子树
（2）中序遍历：左子树-->根节点-->右子树
（3）后序遍历：左子树-->右子树-->根节点
其实还有一种比较基础的遍历方式是层次遍历，但是在本篇文章中不会涉及层次遍历的内容。
两种基础的实现方法
1|0递归
以前序遍历为例，按照根节点-->左子树-->右子树的顺序遍历。先访问根节点，然后再分别对当前根节点的左子树和右子树重复同样的操作。中序遍历和后序遍历也都是类似的，由此可以看出二叉树遍历本身就具有递归的性质。
1|0迭代
我们也可以用迭代的方式来实现递归的过程，递归本质上隐式地维护了一个栈，所以可以用栈这个结构来模拟整个二叉树遍历的过程。
前序遍历
前序遍历（递归）
1|0递归实现前序遍历思路
我们只需要写一个递归函数来实现前序遍历。先考虑下递归函数停止递归的边界条件，很明显在遇到空指针NULL时，我们需要停止递归操作，此时直接return即可。
结合前序遍历的遍历顺序和上文中递归方法的图解，递归函数只需要先执行打印根节点数据的操作，然后再依次执行递归访问左子树、递归访问右子树就可以了。
假设递归函数名为 preorder，则顺序为:
（1）print(root->data)
（2）preorder(root->left)
（3）preorder(root->right)
1|0递归实现前序遍历图解
以下为二叉树前序遍历实例的递归版图解
1|0（1）
1|0（2）
1|0（3）
1|0（4）
1|0（5）
1|0（6）
1|0（7）
1|0（8）
为了方便快速手写出二叉树前序遍历，我们可以形象地把前序遍历看作是一个小人以根节点为起点沿着二叉树的外围跑一圈，小人依次经过的节点就是前序遍历的结果。（重复经过的节点不再放入前序遍历结果序列中）
1|0递归实现前序遍历代码
前序遍历（迭代）
1|0迭代实现前序遍历思路
我们使用栈来模拟递归的过程，先定义一个遍历指针 t 并指向 root，栈用来存储当前遍历到的节点，整个过程用一个while循环来进行迭代。大致过程就是先打印当前节点数据，再一直往左走，边走边打印节点数据，同时将当前节点入栈，一直遍历到最左边的节点为止；然后取出栈顶节点，访问其右子树，再重复上述操作。
大致操作如下：
（1）打印节点数据；
（2）一直向左遍历，将节点入栈，并重复步骤（1），直到到达最左边；
（2）取栈顶节点，前往右子树，重复上述操作。
我们再来考虑停止迭代的边界条件，当 t 不为空指针NULL时，很显然需要访问当前 t 指向的节点；那么如果当前 t 为NULL，难道就可以退出循环吗？答案显然是否定的，例如当我们遍历到二叉树的某个叶子节点时，已经到达当前子树的最左边，转而前往右边，而此时右边也是NULL，那么此时 t 变为NULL，但是栈中还有节点未弹出，整个二叉树的前序遍历还没有完成。所以当栈不为空时，也要继续遍历。综上所述，停止迭代的边界条件为 t == NULL 并且 stack为空。
1|0迭代实现前序遍历图解
1|0（1）
1|0（2）
1|0（3）
1|0（4）
1|0（5）
1|0（6）
1|0（7）
1|0（8）
1|0（9）
1|0（10）
1|0（11）
1|0（12）
1|0（13）
1|0（14）
1|0（15）
1|0迭代实现前序遍历代码
中序遍历
中序遍历（递归）
1|0递归实现中序遍历思路
写一个递归函数，递归结束的边界条件很简单，也是遇到空指针NULL。
按照中序遍历的顺序，先递归访问左子树，再打印根节点数据，最后再递归访问右子树即可。
假设递归函数名为 infixorder，则顺序为:
（1）infixorder(root->left)
（2）print(root->data)
（3）infixorder(root->right)
1|0递归实现中序遍历图解
1|0（1）
1|0（2）
1|0（3）
1|0（4）
1|0（5）
1|0（6）
1|0（7）
1|0（8）
1|0（9）
1|0（10）
中序遍历的结果同样也可以用一种方式来快速写出，将每个节点垂直下降至统一平面，得到的序列就是中序遍历的结果。
1|0递归实现中序遍历代码
中序遍历（迭代）
1|0迭代实现中序遍历思路
同样使用栈来模拟递归的过程，先定义一个遍历指针 t 指向 root，栈用来存储当前遍历到的节点。大致过程就是先一直往左走，同时将当前节点入栈，一直遍历到最左边的节点为止；然后取出栈顶节点，打印节点数据，访问其右子树，再重复上述操作。可以看出迭代版中序遍历和前序遍历的思路只在打印数据的地方有一点差别。
大致操作如下：
（1）一直向左遍历，将节点入栈，直到到达最左边；
（2）取栈顶节点，打印节点数据；
（2）前往右子树，重复上述操作。
整个迭代的过程和前序遍历大致一致，只有打印数据位置不同，停止迭代的条件和前序遍历一样，也是 t == NULL 并且 stack为空。
1|0迭代实现中序遍历图解
1|0（1）
1|0（2）
1|0（3）
1|0（4）
1|0（5）
1|0（6）
1|0（7）
1|0（8）
1|0（9）
1|0（10）
1|0（11）
1|0（12）
1|0（13）
1|0（14）
1|0（15）
1|0迭代实现中序遍历代码
后序遍历
后序遍历（递归）
1|0递归实现后序遍历思路
写一个递归函数，遇到空指针NULL结束递归。
按照后序遍历的顺序，先递归访问左子树，再递归访问右子树，最后打印根节点数据。
假设递归函数名为 postorder，则顺序为:
（1）postorder(root->left)
（2）postorder(root->right)
（3）print(root->data)
1|0递归实现后序遍历图解
1|0（1）
1|0（2）
1|0（3）
1|0（4）
1|0（5）
1|0（6）
1|0（7）
1|0（8）
1|0（9）
1|0（10）
1|0（11）
为了方便快速写出后序遍历的结果，可以将后序遍历看做是剪葡萄一样，将节点一个一个剪下。
1|0递归实现后序遍历代码
后序遍历（迭代）
1|0迭代实现后序遍历思路
后序遍历的迭代写法比前面的两种要稍微复杂一点，同样使用栈来模拟递归的过程，先定义一个遍历指针 t 指向 root，栈用来存储当前遍历到的节点。
同时还需要定义一个指针 last 标记上一次访问过的节点。
我们依旧需要先一直往左走，并且将走过的节点入栈，直到到达最左边。然后取出当前栈顶节点，讨论是否访问当前出栈节点。后序遍历的顺序是左子树-->右子树-->根节点，其实讨论的就是当前出栈的这个子树根节点是否能够被访问。当当前出栈节点的右子树为NULL时，则当前出栈节点可以访问，那么仅此一种情况吗？并不是，假如某个出栈子树的根节点，存在右子树，但是这个右子树已经遍历完毕了，那么也没有再访问右子树的需要，此时同样可以访问出栈节点。满足这个条件只会在左子树已经访问过并且右子树根节点为上一个访问过的节点情况下出现，所以我们只需要用一个 last 来记录当前访问过的节点就行了，为了防止出现死循环，还需要将 t 置NULL。如果这两个条件都不满足，那么当前出栈节点不能访问，需要重新入栈，并且转而访问右子树。
大致操作如下：
（1）一直向左遍历，将节点入栈，直到到达最左边；
（2）取栈顶节点，讨论是否可以访问当前出栈节点；
（3）如果 t == NULL 或者 t == last，则可以访问，并用 last 记录当前访问的节点，将 t 置NULL；
否则不能访问，将当前出栈节点重新入栈，转而前往右子树。
停止迭代的条件和前序遍历、中序遍历一样，也是 t == NULL 并且 stack为空。
1|0迭代实现后序遍历图解
1|0（1）
1|0（2）
1|0（3）
1|0（4）
1|0（5）
1|0（6）
1|0（7）
1|0（8）
1|0（9）
1|0（10）
1|0（11）
1|0（12）
1|0（13）
1|0（14）
1|0（15）
1|0（16）
1|0（17）
1|0（18）
1|0迭代实现后序遍历代码
程序测试
完整程序代码
#include<stdio.h> #include<stdlib.h> #include<stack> #include<iostream> using namespace std;
typedef char Elemtype; typedef struct BiNode{
Elemtype data; struct BiNode *leftchild; //左儿子 struct BiNode *rightchild; //右儿子
}Node, *BinaryTree;
//递归初始化二叉树 赋值二叉树 BinaryTree Create_BinaryTree(){ Elemtype data; BinaryTree T; scanf("%c", &data); //输入节点数据 getchar();
if(data == '#') //输入#停止创建子树 return NULL; T = (BinaryTree)malloc(sizeof(Node)); T->data = data;
printf("输入 %c 的左子树数据: ", data); //递归创建左子树 T->leftchild = Create_BinaryTree(); printf("输入 %c 的右子树数据: ", data); //递归创建右子树 T->rightchild = Create_BinaryTree();
return T; }
//前序 递归遍历二叉树 void Show_Pre_Order(BinaryTree root){ if(root == NULL) return; printf("%c ", root->data); Show_Pre_Order(root->leftchild); Show_Pre_Order(root->rightchild); }
//中序 递归遍历二叉树 void Show_Infix_Order(BinaryTree root){ if(root == NULL) return; Show_Infix_Order(root->leftchild); printf("%c ", root->data); Show_Infix_Order(root->rightchild); }
//后序 递归遍历二叉树 void Show_Post_Order(BinaryTree root){ if(root == NULL) return; Show_Post_Order(root->leftchild); Show_Post_Order(root->rightchild); printf("%c ", root->data); }
//利用栈前序遍历 STL stack void Show_Pre_OrderII(BinaryTree root){ stack<BinaryTree> s; BinaryTree t = root; while(t || !s.empty()){ while(t){ printf("%c ", t->data); s.push(t); t = t->leftchild; //一直往左边走 } t = s.top(); s.pop(); t = t->rightchild; } }
//利用栈中序遍历 STL stack void Show_Infix_OrderII(BinaryTree root){ stack<BinaryTree> s; BinaryTree t = root; while(t || !s.empty()){ while(t){ s.push(t); t = t->leftchild; //一直往左边走 } t = s.top(); s.pop(); printf("%c ", t->data); t = t->rightchild; } }
//利用栈后序遍历 STL stack void Show_Post_OrderII(BinaryTree root){ stack<BinaryTree> s; BinaryTree t = root, last; while(t || !s.empty()){ while(t){ s.push(t); t = t->leftchild; //先到达最左侧节点 } t = s.top(); s.pop(); //如果当前节点无右子树或者右子树根节点为上一个访问过的节点 if(!t->rightchild || t->rightchild == last){ printf("%c ", t->data); last = t; //记录当前访问过的节点 t = NULL; }else{ s.push(t); //否则将当前节点重新入栈 t = t->rightchild; //转而前往其右子树 } } }
int main(){ BinaryTree T; printf("输入二叉树根节点数据: "); T = Create_BinaryTree();
printf("\n先序遍历二叉树:\n"); Show_Pre_Order(T); printf("\n");
printf("\n中序遍历二叉树:\n"); Show_Infix_Order(T); printf("\n");
printf("\n后序遍历二叉树:\n"); Show_Post_Order(T); printf("\n");
printf("\n利用栈非递归前序遍历二叉树:\n"); Show_Pre_OrderII(T); printf("\n");
printf("\n利用栈非递归中序遍历二叉树:\n"); Show_Infix_OrderII(T); printf("\n");
printf("\n利用栈非递归后序遍历二叉树:\n"); Show_Post_OrderII(T); printf("\n"); }
程序运行测试结果
__EOF__
Recommend
-
23
ARTS ARTS 是陈浩（网名左耳朵耗子）在极客时间专栏里发起的一个活动，目的是通过分享的方式来坚持学习。 每人每周写一个 ARTS：Algorithm 是一道算法题，Review 是读一篇英文文章，Technique/Tips 是分享一个小技术...
-
14
二叉树非递归后序遍历2014-06-16翻到自己以前考研时发过的帖子，真心觉得那时候比现在牛B多了...网上传的很多二叉树非递归遍历的算法，都是在结点中加了一个标记的，第二次访问到...
-
14
LeetCode 第 145 号问题：二叉树的后序遍历-程序员小吴 当前位置：程序员小吴 > LeetCodeAnimation > LeetCode 第 145 号问题：二叉树的后序遍...
-
10
LeetCode-145-二叉树的后序遍历发布于 今天 23:54 二叉树的后序遍历题目描述：给定一个二叉树，返回它的 后序 遍历。示例说...
-
9
JZ-023-二叉搜索树的后序遍历序列二叉搜索树的后序遍历序列输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则返回true,否则返回false。假...
-
17
二叉树的遍历，从编程方式上来说主要有两种写法，一种是递归的写法，一种是非递归的写法，其中递归的写法很容易，在leetcode上都是属于easy级别的题目，风格也非常一致，学会了前序遍历，调整一下代码顺序，几秒之内中序、后...
-
6
在面试时，避免不了的会遇到一些数据结构的面试题，今天我们就来了解一下二叉树的经典面试题： 已知二叉树的前序遍历顺序为ABDCEGHF，中序遍历顺序为DBAGEHCF，求该二叉树的后序遍历。 已知二叉树的中...
-
10
go 二叉树的非递归遍历 code TreeNode type TreeNode struct { Val int Left *TreeNode Right *TreeNode } 先序遍历 中左右 func preorderTravers...
-
10
二叉树链式结构 前一篇博客介绍了二叉树的顺序结构，是通数组来存储的，这里我们通过创建链式结构来存储，在堆上申请空间，结构如下： template <class DateType> struct BinaryTreeNode { DateT...
-
9
前中后序遍历 前中后序遍历的特点 1|0前序遍历 前序遍历顺序：根节点 -> 左子树 -> 右子树 前序遍历结果：[根...
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK