算法之二叉树各种遍历
本文共 9194 字，大约阅读时间需要 30 分钟。
分享一下我老师大神的人工智能教程！零基础，通俗易懂！
也欢迎大家转载本篇文章。分享知识，造福人民，实现我们中华民族伟大复兴！
树形结构是一类重要的非线性数据结构，其中以树和二叉树最为常用。
二叉树是每个结点最多有两个子树的有序树。通常子树的根被称作“左子树”（left subtree）和“右子树”（right subtree）。二叉树常被用作二叉查找树和二叉堆或是二叉排序树。二叉树的每个结点至多只有二棵子树(不存在度大于2的结点)，二叉树的子树有左右之分，次序不能颠倒。二叉树的第i层至多有2的 i -1次方个结点；深度为k的二叉树至多有2^(k) -1个结点；对任何一棵二叉树T，如果其终端结点数(即叶子结点数)为n0，度为2的结点数为n2，则n0 = n2 + 1。
二叉树的链式存储结构是一类重要的数据结构，其形式定义如下：
//二叉树结点typedef struct BiTNode{ //数据 char data; //左右孩子指针 struct BiTNode *lchild,*rchild;}BiTNode,*BiTree; 二叉树的创建： 通过读入一个字符串，建立二叉树的算法如下：
//按先序序列创建二叉树int CreateBiTree(BiTree &T){ char data; //按先序次序输入二叉树中结点的值（一个字符），‘#’表示空树 scanf("%c",&data); if(data == '#'){ T = NULL; } else{ T = (BiTree)malloc(sizeof(BiTNode)); //生成根结点 T->data = data; //构造左子树 CreateBiTree(T->lchild); //构造右子树 CreateBiTree(T->rchild); } return 0;} 二叉树的遍历： 遍历是对树的一种最基本的运算，所谓遍历二叉树，就是按一定的规则和顺序走遍二叉树的所有结点，使每一个结点都被访问一次，而且只被访问一次。由于二叉树是非线性结构，因此，树的遍历实质上是将二叉树的各个结点转换成为一个线性序列来表示。
递归算法：
//输出void Visit(BiTree T){ if(T->data != '#'){ printf("%c ",T->data); }}//先序遍历void PreOrder(BiTree T){ if(T != NULL){ //访问根节点 Visit(T); //访问左子结点 PreOrder(T->lchild); //访问右子结点 PreOrder(T->rchild); }}//中序遍历void InOrder(BiTree T){ if(T != NULL){ //访问左子结点 InOrder(T->lchild); //访问根节点 Visit(T); //访问右子结点 InOrder(T->rchild); }}//后序遍历void PostOrder(BiTree T){ if(T != NULL){ //访问左子结点 PostOrder(T->lchild); //访问右子结点 PostOrder(T->rchild); //访问根节点 Visit(T); }} 非递归算法：
<1>先序遍历：
【思路】：访问T->data后，将T入栈，遍历左子树；遍历完左子树返回时，栈顶元素应为T，出栈，再先序遍历T的右子树。
/* 先序遍历(非递归) 思路：访问T->data后，将T入栈，遍历左子树；遍历完左子树返回时，栈顶元素应为T，出栈，再先序遍历T的右子树。*/void PreOrder2(BiTree T){ stack stack; //p是遍历指针 BiTree p = T; //栈不空或者p不空时循环 while(p || !stack.empty()){ if(p != NULL){ //存入栈中 stack.push(p); //访问根节点 printf("%c ",p->data); //遍历左子树 p = p->lchild; } else{ //退栈 p = stack.top(); stack.pop(); //访问右子树 p = p->rchild; } }//while} <2>中序遍历 【思路】：T是要遍历树的根指针，中序遍历要求在遍历完左子树后，访问根，再遍历右子树。
先将T入栈，遍历左子树；遍历完左子树返回时，栈顶元素应为T，出栈，访问T->data，再中序遍历T的右子树。void InOrder2(BiTree T){ stack stack; //p是遍历指针 BiTree p = T; //栈不空或者p不空时循环 while(p || !stack.empty()){ if(p != NULL){ //存入栈中 stack.push(p); //遍历左子树 p = p->lchild; } else{ //退栈，访问根节点 p = stack.top(); printf("%c ",p->data); stack.pop(); //访问右子树 p = p->rchild; } }//while} <3>后序遍历 【思路】：T是要遍历树的根指针，后序遍历要求在遍历完左右子树后，再访问根。需要判断根结点的左右子树是否均遍历过。
//后序遍历(非递归)typedef struct BiTNodePost{ BiTree biTree; char tag;}BiTNodePost,*BiTreePost;void PostOrder2(BiTree T){ stack stack; //p是遍历指针 BiTree p = T; BiTreePost BT; //栈不空或者p不空时循环 while(p != NULL || !stack.empty()){ //遍历左子树 while(p != NULL){ BT = (BiTreePost)malloc(sizeof(BiTNodePost)); BT->biTree = p; //访问过左子树 BT->tag = 'L'; stack.push(BT); p = p->lchild; } //左右子树访问完毕访问根节点 while(!stack.empty() && (stack.top())->tag == 'R'){ BT = stack.top(); //退栈 stack.pop(); BT->biTree; printf("%c ",BT->biTree->data); } //遍历右子树 if(!stack.empty()){ BT = stack.top(); //访问过右子树 BT->tag = 'R'; p = BT->biTree; p = p->rchild; } }//while} <4>层次遍历
【思路】：按从顶向下，从左至右的顺序来逐层访问每个节点，层次遍历的过程中需要用队列。
//层次遍历void LevelOrder(BiTree T){ BiTree p = T; //队列 queue queue; //根节点入队 queue.push(p); //队列不空循环 while(!queue.empty()){ //对头元素出队 p = queue.front(); //访问p指向的结点 printf("%c ",p->data); //退出队列 queue.pop(); //左子树不空，将左子树入队 if(p->lchild != NULL){ queue.push(p->lchild); } //右子树不空，将右子树入队 if(p->rchild != NULL){ queue.push(p->rchild); } }} 测试用例：
输入：
ABC##DE#G##F###
输出：
代码：
#include#include #include using namespace std;//二叉树结点typedef struct BiTNode{ //数据 char data; //左右孩子指针 struct BiTNode *lchild,*rchild;}BiTNode,*BiTree;//按先序序列创建二叉树int CreateBiTree(BiTree &T){ char data; //按先序次序输入二叉树中结点的值（一个字符），‘#’表示空树 scanf("%c",&data); if(data == '#'){ T = NULL; } else{ T = (BiTree)malloc(sizeof(BiTNode)); //生成根结点 T->data = data; //构造左子树 CreateBiTree(T->lchild); //构造右子树 CreateBiTree(T->rchild); } return 0;}//输出void Visit(BiTree T){ if(T->data != '#'){ printf("%c ",T->data); }}//先序遍历void PreOrder(BiTree T){ if(T != NULL){ //访问根节点 Visit(T); //访问左子结点 PreOrder(T->lchild); //访问右子结点 PreOrder(T->rchild); }}//中序遍历 void InOrder(BiTree T){ if(T != NULL){ //访问左子结点 InOrder(T->lchild); //访问根节点 Visit(T); //访问右子结点 InOrder(T->rchild); } } //后序遍历void PostOrder(BiTree T){ if(T != NULL){ //访问左子结点 PostOrder(T->lchild); //访问右子结点 PostOrder(T->rchild); //访问根节点 Visit(T); }}/* 先序遍历(非递归) 思路：访问T->data后，将T入栈，遍历左子树；遍历完左子树返回时，栈顶元素应为T，出栈，再先序遍历T的右子树。*/void PreOrder2(BiTree T){ stack stack; //p是遍历指针 BiTree p = T; //栈不空或者p不空时循环 while(p || !stack.empty()){ if(p != NULL){ //存入栈中 stack.push(p); //访问根节点 printf("%c ",p->data); //遍历左子树 p = p->lchild; } else{ //退栈 p = stack.top(); stack.pop(); //访问右子树 p = p->rchild; } }//while}/* 中序遍历(非递归) 思路：T是要遍历树的根指针，中序遍历要求在遍历完左子树后，访问根，再遍历右子树。 先将T入栈，遍历左子树；遍历完左子树返回时，栈顶元素应为T，出栈，访问T->data，再中序遍历T的右子树。*/void InOrder2(BiTree T){ stack stack; //p是遍历指针 BiTree p = T; //栈不空或者p不空时循环 while(p || !stack.empty()){ if(p != NULL){ //存入栈中 stack.push(p); //遍历左子树 p = p->lchild; } else{ //退栈，访问根节点 p = stack.top(); printf("%c ",p->data); stack.pop(); //访问右子树 p = p->rchild; } }//while}//后序遍历(非递归)typedef struct BiTNodePost{ BiTree biTree; char tag;}BiTNodePost,*BiTreePost;void PostOrder2(BiTree T){ stack stack; //p是遍历指针 BiTree p = T; BiTreePost BT; //栈不空或者p不空时循环 while(p != NULL || !stack.empty()){ //遍历左子树 while(p != NULL){ BT = (BiTreePost)malloc(sizeof(BiTNodePost)); BT->biTree = p; //访问过左子树 BT->tag = 'L'; stack.push(BT); p = p->lchild; } //左右子树访问完毕访问根节点 while(!stack.empty() && (stack.top())->tag == 'R'){ BT = stack.top(); //退栈 stack.pop(); printf("%c ",BT->biTree->data); } //遍历右子树 if(!stack.empty()){ BT = stack.top(); //访问过右子树 BT->tag = 'R'; p = BT->biTree; p = p->rchild; } }//while}//层次遍历void LevelOrder(BiTree T){ BiTree p = T; //队列 queue queue; //根节点入队 queue.push(p); //队列不空循环 while(!queue.empty()){ //对头元素出队 p = queue.front(); //访问p指向的结点 printf("%c ",p->data); //退出队列 queue.pop(); //左子树不空，将左子树入队 if(p->lchild != NULL){ queue.push(p->lchild); } //右子树不空，将右子树入队 if(p->rchild != NULL){ queue.push(p->rchild); } }}int main(){ BiTree T; CreateBiTree(T); printf("先序遍历：\n"); PreOrder(T); printf("\n"); printf("先序遍历(非递归)：\n"); PreOrder2(T); printf("\n"); printf("中序遍历：\n"); InOrder(T); printf("\n"); printf("中序遍历(非递归)：\n"); InOrder2(T); printf("\n"); printf("后序遍历：\n"); PostOrder(T); printf("\n"); printf("后序遍历(非递归)：\n"); PostOrder2(T); printf("\n"); printf("层次遍历：\n"); LevelOrder(T); printf("\n"); return 0;}
新版：
给我老师的人工智能教程打call！
新的改变
我们对Markdown编辑器进行了一些功能拓展与语法支持，除了标准的Markdown编辑器功能，我们增加了如下几点新功能，帮助你用它写博客：
- 全新的界面设计 ，将会带来全新的写作体验；
- 在创作中心设置你喜爱的代码高亮样式，Markdown 将代码片显示选择的高亮样式 进行展示；
- 增加了 图片拖拽 功能，你可以将本地的图片直接拖拽到编辑区域直接展示；
- 全新的 KaTeX数学公式 语法；
- 增加了支持甘特图的mermaid语法 功能；
- 增加了 多屏幕编辑 Markdown文章功能；
- 增加了 焦点写作模式、预览模式、简洁写作模式、左右区域同步滚轮设置 等功能，功能按钮位于编辑区域与预览区域中间；
- 增加了 检查列表 功能。
功能快捷键
撤销：Ctrl/Command + Z
重做：Ctrl/Command + Y 加粗：Ctrl/Command + B 斜体：Ctrl/Command + I 标题：Ctrl/Command + Shift + H 无序列表：Ctrl/Command + Shift + U 有序列表：Ctrl/Command + Shift + O 检查列表：Ctrl/Command + Shift + C 插入代码：Ctrl/Command + Shift + K 插入链接：Ctrl/Command + Shift + L 插入图片：Ctrl/Command + Shift + G合理的创建标题，有助于目录的生成
直接输入1次#，并按下space后，将生成1级标题。
输入2次#，并按下space后，将生成2级标题。 以此类推，我们支持6级标题。有助于使用TOC语法后生成一个完美的目录。 如何改变文本的样式
强调文本 强调文本
加粗文本 加粗文本
标记文本
删除文本
引用文本
H2O is是液体。
210 运算结果是 1024.
插入链接与图片
链接: .
图片: 
带尺寸的图片:
当然，我们为了让用户更加便捷，我们增加了图片拖拽功能。
如何插入一段漂亮的代码片
去页面，选择一款你喜欢的代码片高亮样式，下面展示同样高亮的 代码片.
// An highlighted block var foo = 'bar';
生成一个适合你的列表
- 项目
- 项目
- 项目
- 项目
- 项目1
- 项目2
- 项目3
- 计划任务
- 完成任务
创建一个表格
一个简单的表格是这么创建的：
| 项目 | Value |
|---|---|
| 电脑 | $1600 |
| 手机 | $12 |
| 导管 | $1 |
设定内容居中、居左、居右
使用:---------:居中
:----------居左 使用----------:居右 | 第一列 | 第二列 | 第三列 |
|---|---|---|
| 第一列文本居中 | 第二列文本居右 | 第三列文本居左 |
SmartyPants
SmartyPants将ASCII标点字符转换为“智能”印刷标点HTML实体。例如：
| TYPE | ASCII | HTML |
|---|---|---|
| Single backticks | 'Isn't this fun?' | ‘Isn’t this fun?’ |
| Quotes | "Isn't this fun?" | “Isn’t this fun?” |
| Dashes | -- is en-dash, --- is em-dash | – is en-dash, — is em-dash |
创建一个自定义列表
- Markdown
- Text-to- HTML conversion tool Authors
- John
- Luke
如何创建一个注脚
一个具有注脚的文本。
注释也是必不可少的
Markdown将文本转换为 HTML。
KaTeX数学公式
您可以使用渲染LaTeX数学表达式 :
Gamma公式展示 Γ ( n ) = ( n − 1 ) ! ∀ n ∈ N \Gamma(n) = (n-1)!\quad\forall n\in\mathbb N Γ(n)=(n−1)!∀n∈N 是通过欧拉积分
Γ ( z ) = ∫ 0 ∞ t z − 1 e − t d t   . \Gamma(z) = \int_0^\infty t^{z-1}e^{-t}dt\,. Γ(z)=∫0∞tz−1e−tdt.
你可以找到更多关于的信息 LaTeX 数学表达式.
新的甘特图功能，丰富你的文章
gantt dateFormat YYYY-MM-DD title Adding GANTT diagram functionality to mermaid section 现有任务 已完成 :done, des1, 2014-01-06,2014-01-08 进行中 :active, des2, 2014-01-09, 3d 计划一 : des3, after des2, 5d 计划二 : des4, after des3, 5d
- 关于 甘特图 语法，参考 ,
UML 图表
可以使用UML图表进行渲染。 . 例如下面产生的一个序列图：:
这将产生一个流程图。:
- 关于 Mermaid 语法，参考 ,
FLowchart流程图
我们依旧会支持flowchart的流程图：
- 关于 Flowchart流程图 语法，参考 .
导出与导入
导出
如果你想尝试使用此编辑器, 你可以在此篇文章任意编辑。当你完成了一篇文章的写作, 在上方工具栏找到 文章导出 ，生成一个.md文件或者.html文件进行本地保存。
导入
如果你想加载一篇你写过的.md文件或者.html文件，在上方工具栏可以选择导入功能进行对应扩展名的文件导入，
继续你的创作。注脚的解释
你可能感兴趣的文章
Matlab subplot 图像间距调整
查看>>
Hibernate使用count(*)取得表中记录总数
查看>>
distinct使SQL查询除去重复的字段
查看>>
从mysql中 导出/导入表及数据
查看>>
HQL语句大全（转）
查看>>
几个常用的Javascript字符串处理函数 spilt(),join(),substring()和indexof()
查看>>
javascript传参字符串 与引号的嵌套调用
查看>>
进程的状态
查看>>
Runnable和Thread 两种实现方式的区别和联系：
查看>>
并发和并行的区别
查看>>
JAVA多线程和并发基础面试问答
查看>>
线程池的介绍及简单实现
查看>>
利用session,cookie进行安全性控制
查看>>
Session和Cookie的区别及Session的生命周期
查看>>
线程池 Thread Pools
查看>>
Cannot forward after response has been committed 错误解决
查看>>
Linux系统调用--getpid/getppid函数详解
查看>>
二分法排序
查看>>
内部排序
查看>>
二叉树前序、中序、后序遍历相互求法
查看>>