本文共 3010 字，大约阅读时间需要 10 分钟。
前言
这是我听老师讲课做的笔记。
作者：RodmaChen 关注我的csdn博客，更多数据结构与算法知识还在更新 看这篇文章之前可以先看：
遍历二叉树
一. 遍历二叉树
1.介绍
- 什么叫做遍历？ 官方回答：是指沿着某条搜索路线，依次对树中每个结点均做一 次且做一次访问。
通俗回答：每个结点都过一遍
-
遍历的目的： 非线性结构线性化。
二叉树是非线性结构，经过一次完整遍历，可将各结点的非线性排列变为某种意义的线性序列。
2.遍历的方式
（1）先（根）序遍历（NLR/DLR ）
基本思想：若二叉树为空，则退出，否则
(1) 访问根结点；
(2) 按先序周游整个左子树；
(3) 按先序周游整个右子树。
先序遍历的递归算法:(两部分：出口为空结束，否者继续递减)
基本思想：若二叉树为空，则退出，否则
中序遍历整个左子树；
访问根结点；
中序遍历整个右子树。
中序遍历的递归算法:
(3) 后（根）序遍历（LRD/LRN ）
基本思想：若二叉树为空，则退出，否则
后序遍历整个左子树；
后序遍历整个右子树；
访问根结点。
后序遍历的递归算法:
3.二叉树遍历的考试方式
-
给出一棵树，写出先、中、后序
-
由NLR 、LNR 、LRN 扩展到NRL 、RNL 、RLN
-
（1）给出先序+ 中序 写出 后序
（先序找根，中序分左右） （2）给出后序+ 中序 写出 先序 （后序找根，中序分左右） -
考递归遍历算法
事列：
注意：后序：最后一个是根节点
4. 遍历的应用（重点学习）
（1）建立二叉链表（已经有树，现在是创建链表存）：掌握要考
基于先序遍历的构造算法，在其中加入虚结点以示空指针
的位置：ABDøøøCEøøFøø 构造算法
Status CreateBiTree(BiTree &T) { //按先序次序输入二叉树中结点的值(一个字符)，空格字符表示空树，//构造二又链表表示的二叉树Tscanf(&ch);if(ch ==’’) T = NULL;else{ if(!(T = (BiTNode *)malloc(sizeof(BiTNode)))) exit(OVERFLOW);//分配空间T->data = ch; //生成根结点CreateBiTree(T -> lchild); //构造左子树CreateBiTree(T -> rchild) //构造右子树}return OK;}// CreateBiTree （2) 求二叉树的结点个数（重要）
调用过程：事列
int count(BiTree T)//计数{ int lcount,rcount;//左右if (T==NULL) return 0;else{ lcount = count(T -> lchild);//左子树调用函数返回左子树的个数rcount = count(T -> rchild);return lcount + rcount +1;//加一是根节点}} （3) 求二叉树叶子结点的个数
修改计数条件，满足加上，不满足不加
int countleaf(BiTree T){ int lcount,rcount;if (T==NULL) return 0;else{ lcount = countleaf(T -> lchild);rcount = countleaf(T -> rchild);if(T->lchild==NULL && T->rchild==NULL)return lcount + rcount +1;elsereturn lcount + rcount;}} （4) 求二叉树度为1 的结点的个数
int countdeg1(BiTree T){ int lcount,rcount;if (T==NULL) return 0;else{ lcount = countdeg1(T -> lchild);rcount = countdeg1(T -> rchild);if((T->lchild != NULL && T->rchild == NULL)||(T->lchild ==NULL && T->rchild != NULL))return lcount + rcount +1;elsereturn lcount + rcount;}} （5) 计算二叉树的深度
int BiTDepth(BiTree T){ int ldep,rdep;if (T==NULL) return 0;else{ ldep=BiTDepth(T->lchild)+1;//左子树深度rdep=BiTDepth(T->rchild)+1;//右子树深度return ldep>rdep?ldep:rdep;}} （6) 复制二叉树
Status CopyBiTree(BiTree &T, BiTree &T1){ BiTree p;if(T){ p=new BiTNode;if(!p) return ERROR;p->data=T->data;T1=p;CopyBiTree(T->lchild,T1->lchild);CopyBiTree(T->rchild,T1->rchild);}else T1=T;return OK;} 二.遍历的非递归：（考研要考）
仿照递归算法执行过程中递归工作栈（利用栈的先进后出一层层递归出来）的状态变化状况可
直接写出相应的非递归算法。以中序遍历为例：每遇到一个结点就把它推入栈，然后
遍历其左子树，若左子树为空，则从栈顶退出这个结点并 访问；按照其右链接指示的地址再去周游该结点的右子树。中序遍历( 左根右) ：
d b g e h a c f
Status InOrderTraverse(BiTree T){ //采用二叉链表存储结构,Visit是对数据元素操作的应用函数。//中序遍历二叉树T的非递归算法,对每个数据元素调用函数Visit。InitStack(S) ; p=T;while (p || !StackEmpty(S)) { if (p) { Push(S,p); p = p->lchild; } // 根指针进栈,遍历左子树else{ //根指针退栈，访问根结点,遍历右子树Pop(S, p); Visit(p->data);（VIsit输出值）p= p-> rchild;}// else}// Whilereturn 0K;} // InOrderTraverse 三.边学边练
1、若一棵二叉树后序遍历和中序遍历的序列分别为：后序
序列为DHEBFIGCA，中序序列为DBEHAFCIG，试画出这棵二 叉树。
2、（1）已知一棵二叉树的前序序列和中序序列分别为 ABDGHCEFI和GDHBAECIF，求其对应的二叉树。
（2）已知一棵二叉树的中序序列和后序序列分别为 BDCEAFHG和DECBHGFA，求其对应的二叉树。
（3）若前序序列和后序序列均为AB和BA能否惟一确定 一棵二叉树。答案：不能
作者：RodmaChen
本人博客： 本人b站求关注： 转载说明：跟我说明，务必注明来源，附带本人博客连接。
请给我点个赞鼓励我吧
转载地址：https://chenyunzhi.blog.csdn.net/article/details/106297007 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！
发表评论
最新留言
关于作者
