正文
【二叉树遍历模版】前序遍历&&中序遍历&&后序遍历&&层次遍历&&Root->Right->Left遍历
小程序:扫一扫查出行
【扫一扫了解最新限行尾号】
复制小程序
【扫一扫了解最新限行尾号】
复制小程序
【二叉树遍历模版】前序遍历
1.递归实现
test.cpp:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 | #include <iostream> #include <cstdio> #include <stack> #include <vector> #include "BinaryTree.h" using namespace std; void preorder(TreeNode *root, vector<int> &path) // 树中结点含有分叉, ConnectTreeNodes(pNodeA1, pNodeA2, pNodeA3); PrintTree(pNodeA1); vector<int> ans = preorderTraversal(pNodeA1); for (int i = 0; i < ans.size(); ++i) DestroyTree(pNodeA1); |
输出结果:
8 6 9 2 4 7 1
2.非递归实现(迭代实现)
根据前序遍历访问的顺序,优先访问根结点,然后再分别访问左孩子和右孩子。即对于任一结点,其可看做是根结点,因此可以直接访问,访问完之后,若其左孩子不为空,按相同规则访问它的左子树;当访问其左子树时,再访问它的右子树。因此其处理过程如下:
对于任一结点P:
1)访问结点P,并将结点P入栈;
2)判断结点P的左孩子是否为空,若为空,则取栈顶结点并进行出栈操作,并将栈顶结点的右孩子置为当前的结点P,循环至1);若不为空,则将P的左孩子置为当前的结点P;
3)直到P为NULL并且栈为空,则遍历结束。
test.cpp:
简单的实现方式
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 | #include <iostream> #include <cstdio> #include <stack> #include <vector> #include "BinaryTree.h" using namespace std; /** while (!s.empty()) if (!tmp) s.push(tmp->right); } // 树中结点含有分叉, ConnectTreeNodes(pNodeA1, pNodeA2, pNodeA3); vector<int> ans = rootRLTraversal(pNodeA1); for (int i = 0; i < ans.size(); ++i) DestroyTree(pNodeA1); |
输出结果:
6 7 1 4 3 5 2
复杂一点但是代码风格和中序和后序一致,
test.cpp:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 | #include <iostream> #include <cstdio> #include <stack> #include <vector> #include "BinaryTree.h" using namespace std; //非递归前序遍历 // 树中结点含有分叉, ConnectTreeNodes(pNodeA1, pNodeA2, pNodeA3); PrintTree(pNodeA1); vector<int> ans = preorderTraversal(pNodeA1); for (int i = 0; i < ans.size(); ++i) DestroyTree(pNodeA1); |
输出结果:
8 6 9 2 4 7 1
【二叉树遍历模版】中序遍历
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 | #include <iostream> #include <cstdio> #include <stack> #include <vector> #include "BinaryTree.h" using namespace std; void inorder(TreeNode *root, vector<int> &path) vector<int> inorderTraversal(TreeNode *root) // 树中结点含有分叉, ConnectTreeNodes(pNodeA1, pNodeA2, pNodeA3); PrintTree(pNodeA1); vector<int> ans = inorderTraversal(pNodeA1); for (int i = 0; i < ans.size(); ++i) DestroyTree(pNodeA1); |
输出结果:
9 6 4 2 7 8 1
2.非递归实现
根据中序遍历的顺序,对于任一结点,优先访问其左孩子,而左孩子结点又可以看做一根结点,然后继续访问其左孩子结点,直到遇到左孩子结点为空的结点才进行访问,然后按相同的规则访问其右子树。因此其处理过程如下:
对于任一结点P,
1)若其左孩子不为空,则将P入栈并将P的左孩子置为当前的P,然后对当前结点P再进行相同的处理;
2)若其左孩子为空,则取栈顶元素并进行出栈操作,访问该栈顶结点,然后将当前的P置为栈顶结点的右孩子;
3)直到P为NULL并且栈为空则遍历结束
test.cpp:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 | #include <iostream> #include <cstdio> #include <stack> #include <vector> #include "BinaryTree.h" using namespace std; //非递归中序遍历 // 树中结点含有分叉, ConnectTreeNodes(pNodeA1, pNodeA2, pNodeA3); PrintTree(pNodeA1); vector<int> ans = inorderTraversal(pNodeA1); for (int i = 0; i < ans.size(); ++i) DestroyTree(pNodeA1); |
输出结果:
9 6 4 2 7 8 1
【二叉树遍历模版】后序遍历-递归实现
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 | #include <iostream> #include <cstdio> #include <stack> #include <vector> #include "BinaryTree.h" using namespace std; /** vector<int> path; // 树中结点含有分叉, ConnectTreeNodes(pNodeA1, pNodeA2, pNodeA3); PrintTree(pNodeA1); vector<int> ans = postorderTraversal(pNodeA1); for (int i = 0; i < ans.size(); ++i) DestroyTree(pNodeA1); |
9 4 7 2 6 1 8运行结果:
2.非递归实现
后序遍历的非递归实现是三种遍历方式中最难的一种。因为在后序遍历中,要保证左孩子和右孩子都已被访问并且左孩子在右孩子前访问才能访问根结点,这就为流程的控制带来了难题。下面介绍两种思路。
第一种思路:对于任一结点P,将其入栈,然后沿其左子树一直往下搜索,直到搜索到没有左孩子的结点,此时该结点出现在栈顶,但是此时不能将其出栈并访问, 因此其右孩子还为被访问。所以接下来按照相同的规则对其右子树进行相同的处理,当访问完其右孩子时,该结点又出现在栈顶,此时可以将其出栈并访问。这样就 保证了正确的访问顺序。可以看出,在这个过程中,每个结点都两次出现在栈顶,只有在第二次出现在栈顶时,才能访问它。因此需要多设置一个变量标识该结点是 否是第一次出现在栈顶。
test.cpp:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 | #include <iostream> #include <cstdio> #include <stack> #include <vector> #include "BinaryTree.h" using namespace std; /** //中介节点 //非递归后序遍历-迭代 // 树中结点含有分叉, ConnectTreeNodes(pNodeA1, pNodeA2, pNodeA3); PrintTree(pNodeA1); vector<int> ans = postTraversal(pNodeA1); for (int i = 0; i < ans.size(); ++i) DestroyTree(pNodeA1); |
输出结果:
9 4 7 2 6 1 8
【二叉树遍历模版】层次遍历
count 记录的是当前遍历的层次当中的结点个数。
depth记录的是当前遍历过的层次数。
test.cpp:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 | #include <iostream> #include <cstdio> #include <stack> #include <vector> #include "BinaryTree.h" using namespace std; /** vector<vector<int> > matrix; vector<TreeNode *> path; int count = 1; if(count == 0) // 树中结点含有分叉, ConnectTreeNodes(pNodeA1, pNodeA2, pNodeA3); PrintTree(pNodeA1); vector<vector<int> > ans = levelOrder(pNodeA1); for (int i = 0; i < ans.size(); ++i) DestroyTree(pNodeA1); |
输出结果:
8 6 1 9 2 4 7
【二叉树遍历模版】Root->Right->Left遍历
先遍历根节点,然后在遍历这个根节点的右子树的根节点,然后递归对右子树做遍历,
遍历完事儿之后再递归遍历左子树。注意这种遍历方法很常用。本质上是一种DFS。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 | #include <iostream> #include <cstdio> #include <stack> #include <vector> #include "BinaryTree.h" using namespace std; /** while (!s.empty()) if (!tmp) s.push(tmp->left); // 树中结点含有分叉, ConnectTreeNodes(pNodeA1, pNodeA2, pNodeA3); vector<int> ans = rootRLTraversal(pNodeA1); for (int i = 0; i < ans.size(); ++i) DestroyTree(pNodeA1); |
结果输出:
6 2 7 4 5 3 1
BinaryTree.h:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 | #ifndef _BINARY_TREE_H_ #define _BINARY_TREE_H_ struct TreeNode TreeNode *CreateBinaryTreeNode(int value); #endif /*_BINARY_TREE_H_*/ |
BinaryTree.cpp:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 | #include <iostream> #include <cstdio> #include "BinaryTree.h" using namespace std; /** //创建结点 return pNode; //连接结点 //打印节点内容以及左右子结点内容 if(pNode->left != NULL) if(pNode->right != NULL) printf("\n"); //前序遍历递归方法打印结点内容 if(pRoot != NULL) if(pRoot->right != NULL) void DestroyTree(TreeNode *pRoot) delete pRoot; DestroyTree(pLeft); |
【二叉树遍历模版】前序遍历&&中序遍历&&后序遍历&&层次遍历&&Root->Right->Left遍历的更多相关文章- Java实现二叉树的前序、中序、后序遍历(非递归方法)
在上一篇博客中,实现了Java中二叉树的三种遍历方式的递归实现,接下来,在此实现Java中非递归实现二叉树的前序.中序.后序遍历,在非递归实现中,借助了栈来帮助实现遍历.前序和中序比较类似,也简单 ...
- LeetCode二叉树的前序、中序、后序遍历(递归实现)
本文用递归算法实现二叉树的前序.中序和后序遍历,提供Java版的基本模板,在模板上稍作修改,即可解决LeetCode144. Binary Tree Preorder Traversal(二叉树前序遍 ...
- Java实现二叉树的前序、中序、后序、层序遍历(非递归方法)
在上一篇博客中,实现了Java中二叉树的四种遍历方式的递归实现,接下来,在此实现Java中非递归实现二叉树的前序.中序.后序.层序遍历,在非递归实现中,借助了栈来帮助实现遍历.前序和中序比较类似, ...
- 【2】【leetcode-105,106】 从前序与中序遍历序列构造二叉树,从中序与后序遍历序列构造二叉树
105. 从前序与中序遍历序列构造二叉树 (没思路,典型记住思路好做) 根据一棵树的前序遍历与中序遍历构造二叉树. 注意:你可以假设树中没有重复的元素. 例如,给出 前序遍历 preorder = [ ...
- PHP递归方法实现前序、中序、后序遍历二叉树
二叉树是每个节点最多有两个子树的树结构.通常子树被称作“左子树”(left subtree)和“右子树”(right subtree). class Node { public $value; pub ...
- leetcode 105 106 从前序与中序遍历序列构造二叉树 从中序与后序遍历序列构造二叉树
题目: 105 根据一棵树的前序遍历与中序遍历构造二叉树. 注意:你可以假设树中没有重复的元素. 例如,给出 前序遍历 preorder = [3,9,20,15,7] 中序遍历 inorder = ...
- 二叉树各种相关操作(建立二叉树、前序、中序、后序、求二叉树的深度、查找二叉树节点,层次遍历二叉树等)(C语言版)
将二叉树相关的操作集中在一个实例里,有助于理解有关二叉树的相关操作: 1.定义树的结构体: typedef struct TreeNode{ int data; struct TreeNode *le ...
- Python实现二叉树的前序、中序、后序、层次遍历
有关树的理论部分描述:<数据结构与算法>-4-树与二叉树: 下面代码均基于python实现,包含: 二叉树的前序.中序.后序遍历的递归算法和非递归算法: 层次遍历: 由前序序列.中 ...
- 数据结构-二叉树(1)以及前序、中序、后序遍历(python实现)
上篇文章我们介绍了树的概念,今天我们来介绍一种特殊的树--二叉树,二叉树的应用很广,有很多特性.今天我们一一来为大家介绍. 二叉树 顾名思义,二叉树就是只有两个节点的树,两个节点分别为左节点和右节点, ...
- 二叉树的查找(前序、中序、后序、层序遍历)--biaobiao88
建立一棵含有n个结点的二叉树,采用二叉链表存储: 输出前序.中序.后序..层序遍历该二叉树的遍历结果. 定义二叉树的数据类型——二叉树结点结构体BiNode.建立二叉链表可以采用扩展二叉树的一个遍历序 ...
随机推荐- Ubuntu下deb文件及tgz文件安装
dpkg 是Debian Package的简写,是为Debian 专门开发的套件管理系统,方便软件的安装.更新及移除.所有源自Debian的Linux发行版都使用dpkg,例如Ubuntu.Knopp ...
- 【原创】-- uboot,kennel,fs,rootfs 编译制作
环境:ubuntu14.04 内核版本 linux 3.13.0 OK6410 内核编译环境 linux 3.0.1 uboot版本 1.1.6 交叉编译工具链 arm-lin ...
- 夺命雷公狗—angularjs—8—ng-class的简单用法
我们在正常的业务处理中往往会遇到一些逻辑类的问题,比如各行换色,现在angularjs里面也给我们提供了一个小小的的class处理的方式,废话不多说,如下所示: <!doctype html&g ...
- Yii2中自带分页类实现分页
1.首先写控制器层 先引用pagination类 use yii\data\Pagination; 写自己的方法: function actionFenye(){ $data = Fie ...
- erlang和go之间桥接库相关
https://github.com/goerlang
- substring与substr
一.substring package Test; public class SubstringTest { public static void main(String[] args) { Stri ...
- [LeetCode] 032. Longest Valid Parentheses (Hard) (C++)
指数:[LeetCode] Leetcode 指标解释 (C++/Java/Python/Sql) Github: https://github.com/illuz/leetcode 032. Lon ...
- LIBPNG
libpng 库的源码包中有个 example.c ,里面包含PNG文件读/写的示例代码,参考示例代码和注释(虽然是英文的),可以了解大致的用法. 以下是读取PNG图片的图像数据的代码,使用前还需要按 ...
- ABP框架系列之十五:(Caching-缓存)
Introduction ASP.NET Boilerplate provides an abstraction for caching. It internally uses this cache ...
- Linux系统如何将某一程序设置为开机自启动
文章来源:百度知道. Linux开机启动程序详解 我们假设大家已经熟悉其它操作系统的引导过程,了解硬件的自检引导步骤,就只从Linux操作系统的引导加载程序(对个人电脑而言通常是LILO)开始,介绍L ...
在上一篇博客中,实现了Java中二叉树的三种遍历方式的递归实现,接下来,在此实现Java中非递归实现二叉树的前序.中序.后序遍历,在非递归实现中,借助了栈来帮助实现遍历.前序和中序比较类似,也简单 ...
本文用递归算法实现二叉树的前序.中序和后序遍历,提供Java版的基本模板,在模板上稍作修改,即可解决LeetCode144. Binary Tree Preorder Traversal(二叉树前序遍 ...
在上一篇博客中,实现了Java中二叉树的四种遍历方式的递归实现,接下来,在此实现Java中非递归实现二叉树的前序.中序.后序.层序遍历,在非递归实现中,借助了栈来帮助实现遍历.前序和中序比较类似, ...
105. 从前序与中序遍历序列构造二叉树 (没思路,典型记住思路好做) 根据一棵树的前序遍历与中序遍历构造二叉树. 注意:你可以假设树中没有重复的元素. 例如,给出 前序遍历 preorder = [ ...
二叉树是每个节点最多有两个子树的树结构.通常子树被称作“左子树”(left subtree)和“右子树”(right subtree). class Node { public $value; pub ...
题目: 105 根据一棵树的前序遍历与中序遍历构造二叉树. 注意:你可以假设树中没有重复的元素. 例如,给出 前序遍历 preorder = [3,9,20,15,7] 中序遍历 inorder = ...
将二叉树相关的操作集中在一个实例里,有助于理解有关二叉树的相关操作: 1.定义树的结构体: typedef struct TreeNode{ int data; struct TreeNode *le ...
有关树的理论部分描述:<数据结构与算法>-4-树与二叉树: 下面代码均基于python实现,包含: 二叉树的前序.中序.后序遍历的递归算法和非递归算法: 层次遍历: 由前序序列.中 ...
上篇文章我们介绍了树的概念,今天我们来介绍一种特殊的树--二叉树,二叉树的应用很广,有很多特性.今天我们一一来为大家介绍. 二叉树 顾名思义,二叉树就是只有两个节点的树,两个节点分别为左节点和右节点, ...
建立一棵含有n个结点的二叉树,采用二叉链表存储: 输出前序.中序.后序..层序遍历该二叉树的遍历结果. 定义二叉树的数据类型——二叉树结点结构体BiNode.建立二叉链表可以采用扩展二叉树的一个遍历序 ...
- Ubuntu下deb文件及tgz文件安装
dpkg 是Debian Package的简写,是为Debian 专门开发的套件管理系统,方便软件的安装.更新及移除.所有源自Debian的Linux发行版都使用dpkg,例如Ubuntu.Knopp ...
- 【原创】-- uboot,kennel,fs,rootfs 编译制作
环境:ubuntu14.04 内核版本 linux 3.13.0 OK6410 内核编译环境 linux 3.0.1 uboot版本 1.1.6 交叉编译工具链 arm-lin ...
- 夺命雷公狗—angularjs—8—ng-class的简单用法
我们在正常的业务处理中往往会遇到一些逻辑类的问题,比如各行换色,现在angularjs里面也给我们提供了一个小小的的class处理的方式,废话不多说,如下所示: <!doctype html&g ...
- Yii2中自带分页类实现分页
1.首先写控制器层 先引用pagination类 use yii\data\Pagination; 写自己的方法: function actionFenye(){ $data = Fie ...
- erlang和go之间桥接库相关
https://github.com/goerlang
- substring与substr
一.substring package Test; public class SubstringTest { public static void main(String[] args) { Stri ...
- [LeetCode] 032. Longest Valid Parentheses (Hard) (C++)
指数:[LeetCode] Leetcode 指标解释 (C++/Java/Python/Sql) Github: https://github.com/illuz/leetcode 032. Lon ...
- LIBPNG
libpng 库的源码包中有个 example.c ,里面包含PNG文件读/写的示例代码,参考示例代码和注释(虽然是英文的),可以了解大致的用法. 以下是读取PNG图片的图像数据的代码,使用前还需要按 ...
- ABP框架系列之十五:(Caching-缓存)
Introduction ASP.NET Boilerplate provides an abstraction for caching. It internally uses this cache ...
- Linux系统如何将某一程序设置为开机自启动
文章来源:百度知道. Linux开机启动程序详解 我们假设大家已经熟悉其它操作系统的引导过程,了解硬件的自检引导步骤,就只从Linux操作系统的引导加载程序(对个人电脑而言通常是LILO)开始,介绍L ...