淄博周村网站建设哪家好,.net 网站 调试,网站字头优化,网站cms一.二叉树的遍历#xff1a;
按照一定规律对二叉树的每个结点进行访问且仅访问一次#xff1b;
这里的访问#xff1a;可以是计算二叉树中的结点数据#xff0c;打印该结点的信息#xff0c;也可以是对结点进行的任何其它操作#xff01;
为什么需要遍历二叉树#x…一.二叉树的遍历
按照一定规律对二叉树的每个结点进行访问且仅访问一次
这里的访问可以是计算二叉树中的结点数据打印该结点的信息也可以是对结点进行的任何其它操作
为什么需要遍历二叉树
从过遍历可以得到访问结点的顺序序列遍历操作就是将二叉树的结点按一定的规律线性化目的就在于将非线性化的结构变成线性化的访问序列。 二.3种遍历方式
1.先序遍历DLR根——左——右
若二叉树非空
首先访问根结点其次按先序遍历左子树最后按先序遍历右子树
下面我们给出一个例子 如图所示的二叉树根据先序遍历的特点我们先访问根结点A再访问其左子树,而其左子树又可以看成一个二叉树我们依然用先序遍历A的左子树此时B为这个左子树的根结点于是我们访问BA的左子树此时还没有访问完成因此我们继续访问此时B已经访问过那么我们接着访问B的左孩子而B没有左孩子所以我们接着访问B的右孩子D作为右孩子的根结点直接访问对于D来说接着访问D的左孩子F最后访问D的右孩子G此时A的左孩子遍历完成
那么我们接着遍历A的右孩子C作为右子树的根结点直接访问C没有左孩子接着访问C的右孩子E作为C的右孩子的根节点直接访问E没有左孩子访问E的右孩子H
综上所述上述二叉树的先序遍历的顺序就为A-B-D-F-G-C-E-H 2.中序遍历LDR左——根——右 我们仍然以上述二叉树为例来看
根据 中序遍历的特点首先按中序遍历左子树此时首先访问A的左子树我们将二叉树的左子树单独拿出来看如图B作为左子树的根节点我们要找此时这个二叉树的左孩子而此时这个二叉树没有左孩子因此我们直接访问这个二叉树的根节点B之后访问这个二叉树的右孩子同样把这个二叉树的右孩子单独拿出来此时我们依然以中序遍历首先访问这个二叉树的左孩子即F接着访问这个二叉树的根节点D,最后访问这个二叉树的右孩子G
那么此时整个二叉树的左孩子访问完成继续访问整个二叉树的根节点A
接着访问整个二叉树的右孩子
此时C作为整个二叉树的右孩子的根节点我们首先访问这个二叉树的左孩子显然这个二叉树没有左孩子因此我们先访问根结点C
此时E作为二叉树的根结点此时该二叉树没有左孩子直接访问根节点E最后访问右孩子H
综上所述按照中序遍历访问上述二叉树的顺序B-F-D-G-A-C-E-H
3.后序遍历LRD左——右——根 仍然以上述二叉树作为例子来看首先访问整个二叉树的左子树
按照后序遍历访问B作为根结点访问这个二叉树的左子树左子树为空接着访问这个二叉树的右孩子
此时D作为根结点先访问其左孩子F接着访问其右孩子G最后访问根节点D
那么经过上述过程该二叉树的右孩子访问完成接着访问根节点B此时整个二叉树的左子树遍历完成
那么我们接着访问整个二叉树的右子树
C作为此时这个二叉树的根结点先访问这个二叉树的左子树但是左子树为空接着访问右孩子
E为此时这个二叉树的根结点此时这个二叉树没有左子树那么我们访问其右孩子H接着访问根节点E
此时这个二叉树的右孩子也访问完成所以我们访问根结点C
整个二叉树的左右子树均已遍历完成于是我们最后访问根结点A
综上所述按照后续遍历访问上述二叉树的顺序为F-G-D-B-H-E-C-A
总结
看了以上三种方式遍历二叉树的例子应该就能明白三种遍历方式的本质与区别其实我们可以看出无论以何种方式我们只要把握好访问的顺序并且将每一个根结点下的子树都看成一个新树再按照某种遍历方式访问这个这个新树即可
例子中缀表达式转后缀表达式前缀表达式波兰表达式后缀表达式逆波兰表达式 前缀表达式-a*bc/de也就是以先序遍历访问上述二叉树的顺序
中缀表达式ab*c-d/e也就是以中序遍历访问上述二叉树的顺序
后缀表达式abc*de/-也就是以后序遍历访问上述二叉树的顺序
我们其实可以看出中缀表达式是我们在数学计算中的习惯顺序但是其实在计算机种后缀表达式才是计算机能理解的表达式
关于中缀表达式转后缀表达式的例题
有兴趣的读者可以自行尝试下面给出利用栈来解决逆波兰表达式的代码
#include stdio.h
#include string.h
#include stdlib.h
#define MaxSize 1010typedef struct
{char* ch;int top;}CharStack;typedef struct
{double* num;int top;
}NumStack;CharStack S;
NumStack St;void InitCharStack(CharStack S);
void InitNumStack(NumStack St);
void PushCharStack(CharStack S, char c);
void PushNumStack(NumStack St, double num);
char PopCharStack(CharStack S);
double PopNumStack(NumStack St);
char GetStackTop(CharStack S);
bool PriorJudge(char c1, char c2);//priority优先级 judge判断
char* InfixToSuffex(char* a, char* b);//infix前缀 suffex后缀
double CaculatValue(char* b, NumStack St);int main()
{InitCharStack(S);char a[MaxSize] { 0 };char b[MaxSize] { 0 };InfixToSuffex(a, b);double ans CaculatValue(b, St);printf(%.2f\n, ans);return 0;
}void InitCharStack(CharStack S)
{S.ch (char*)malloc(MaxSize * sizeof(char));if (S.ch NULL){printf(内存分配失败);return;}S.top -1;return;
}void PushCharStack(CharStack S, char c)
{if (S.top MaxSize){printf(栈已满);return;}S.top;*S.ch c;return;
}char PopCharStack(CharStack S)
{if (S.top -1){printf(栈为空);;exit(1);}S.top--;char c *S.ch--;return c;
}char GetStackTop(CharStack S)
{char c *S.ch;return c;
}bool PriorJudge(char c1, char c2)//priority优先级 judge判断
{if (c1 * || c1 /)if (c2 || c2 - || c2 ()return true;if (c1 || c1 -)if (c2 () return true;return false;
}char* InfixToSuffex(char* a, char* b)//infix中缀 suffex后缀
{fgets(a, MaxSize - 1, stdin);//从输入流中读取字符串 int t strlen(a);int k 0;// 12.25 25.02 / 2.36 8 * 2.01 for (int i 0; i t; i){if (a[i] 0 a[i] 9){b[k] a[i];if (a[i 1] .) b[k] ., i;else if (a[i 1] 0 || a[i 1] 9)b[k] #;}else if (a[i] || a[i] ) continue;else{if (S.top -1 || a[i] ()PushCharStack(S, a[i]);else if (a[i] )){while (S.top ! -1 GetStackTop(S) ! ()b[k] PopCharStack(S);if (S.top ! -1) PopCharStack(S);}else{while (S.top ! -1 !PriorJudge(a[i], GetStackTop(S)))b[k] PopCharStack(S);PushCharStack(S, a[i]);}}}b[k] \0;//这句话加不加应该无所谓因为该字符数组已初始化为0 return b;
}void InitNumStack(NumStack St)
{St.num (double*)malloc(MaxSize * sizeof(double));St.top -1;return;
}void PushNumStack(NumStack St, double n)
{if (St.top MaxSize){printf(栈已满);return;}St.top;*St.num n;return;
}double PopNumStack(NumStack St)
{if (St.top -1){printf(栈为空);exit(1);}St.top--;double num *St.num--;return num;
}double CaculatValue(char* b, NumStack St)
{InitNumStack(St);int t strlen(b);char str[MaxSize] { 0 };for (int i 0, k 0; i t; i){if (b[i] . || (b[i] 0 b[i] 9)){str[k] b[i];if (b[i 1] #){str[k] \0;double num atof(str);PushNumStack(St, num);k 0;}}else{if (b[i] #) continue;double n PopNumStack(St);double m PopNumStack(St);if (b[i] ) PushNumStack(St, m n);else if (b[i] -) PushNumStack(St, m - n);else if (b[i] *) PushNumStack(St, m * n);else PushNumStack(St, m / n);}}return PopNumStack(St);
} 三.二叉树的遍历算法
在理解了上述所说的遍历过程之后我们来看二叉树的遍历算法可以分为递归算法与非递归算法
1.递归算法
1先序遍历的递归算法
首先定义二叉树的链表结点结构
#define DataType int
//首先定义二叉树typedef struct Node
{DataType data;struct Node* LChild;struct Node* RChild;
}BiTNode,*BiTree;//先序遍历二叉树的递归算法void PreOrder(BiTree root)
{//root为指向二叉树或者其某一子树的根结点的指针if (root ! NULL){printf(%d, root-data);//访问根结点//文章开头就已经说过二叉树的遍历可以是多种形式PreOrder(root-LChild);//按照先序遍历访问左子树PreOrder(root-RChild);//按照先序遍历访问右子树}
}2中序遍历递归算法
void InOrder(BiTree root)
{if (root ! NULL){InOrder(root-LChild);//首先按中序遍历左子树printf(%d, root-data);//访问根结点InOrder(root-RChild);//中序遍历右子树}
}
3后续遍历递归算法
void PostOrder(BiTree root)
{if (root ! NULL){PostOrder(root-LChild);//首先按照后序遍历左子树PostOrder(root-RChild);//按照后序遍历右子树printf(%d, root-data);//访问根结点}
}递归把复杂问题变成相同性质的子问题因此递归算法表面上看上去很简单其实整个的逻辑十分复杂
比如当访问到的结点不为空时我们先访问其左子树再访问其右子树但是当根结点为空时就不需要参与递归运算那此时访问的为空应该返回什么值在这里程序就会自动设置堆栈来保存本层地址涉及到堆栈的知识当递归函数调用时应按照“后调用先返回”因为大问题一直在分解成小问题当分解为基问题时才会返回一个值因此最后调用的先返回的原则处理调用过程因此函数之间的信息传递和控制转移必须通过栈来实现符合栈的特点last in first out
整个递归过程其实与上述所描述的遍历算法类似读者可尝试分析 递归算法的时间复杂度分析
假设二叉树有n个结点对每个结点都要进行一次入栈和出栈的操作即入栈和出栈均执行了n此对结点的访问也是n次这些二叉树的递归遍历算法的时间复杂度就为O(n) A.递归遍历算法的应用
a.输出二叉树中的结点
//输出二叉树的结点void PreOrder(BiTree root)
{if (root ! NULL){printf(%d,root-data);PreOrder(root-LChild);PreOrder(root-RChild);}
}输出二叉树的结点并没有次序要求因此三种次序均可以使用
b.输出二叉树中的叶子结点
相比于上述应用叶子节点无后继因此有条件限制
//输出叶子结点数void PreOrder(BiTree root)
{if (root ! NULL){if (root-LChild NULL root-RChild NULL){printf(%d, root-data);}PreOrder(root-LChild);PreOrder(root-RChild);}
}
c.统计叶子结点数目
1一般的后序遍历
void leaf(BiTree root)
{if (root ! NULL){leaf(root-LChild);leaf(root-RChild);if (root-LChild NULL root-RChild NULL){leafCount;//保存叶子结点数目的全局变量调用之前的初始化为0别忘了在main函数中先调用初始化函数}}
}
在这里根据文章开头所说的究竟什么才是对根结点进行访问在这里leafCount就可以是因此在这里我们使用的是后续遍历
2分治算法
如果二叉树为空树返回0如果二叉树只有一个根结点返回1否则返回左子树和右子树的叶子节点数之和也是递归算法
int leaf1(BiTree root)
{int leafCount;if (root NULL){leafCount 0;}else if (root-LChild NULL root-RChild NULL){leafCount 1;}else{leafCount leaf1(root-LChild) leaf1(root-RChild);}return leafCount;
}在这里也是后序遍历根据表达式CAB在C语言中是先计算A再计算B最后计算AB赋值给C因此依然是先遍历左子树再遍历右子树最后访问根
关于求二叉树的高度读者可尝试
int PostTreeDepth(BiTree bt)
{int hl, hr,max;if (bt ! NULL){hlPostTreeDepth(bt-LChild);hrPostTreeDepth(bt-RChild);max hl hr ? hl : hr;return(max 1);//还要加上第一个根结点}else{return 0;}
}
d:按横向树形显示二叉树
其实就是按照“逆中序”的方式来遍历整个二叉树所谓的逆中序就是先访问右子树再访问根最后访问右子树与正常的中序遍历相反
在这里只给出思路具体代码实现读者可以自行尝试有问题欢迎在评论区交流
2.非递归算法
基于栈的递归消除
关于递归的消除我们可以将这些递归问题转化为重复的循环问题即用循环代替递归但是在工作量大复杂的情况下就不适宜采用循环因此我们可以采用工作栈的方式来消除递归。
1中序遍历二叉树的非递归算法
下面我们以中序遍历二叉树的非递归算法为例来看 整个过程都依据在上述框图下进行 以此二叉树为例
首先AA不为空——进栈pA的LChild到BB不为空——进栈p指向B的左子树到CC不为空C进栈p指向C的左子树C的左子树为空判断栈是否为空栈此时非空C出栈p指向C的右子树DC的右子树不为空D入栈p指向D的左子树p为空那么判断栈是否为空栈非空D退栈p指向D的右子树D的右子树为空栈非空退栈到Bp指向B的右子树为E不是空那么E进栈E的左子树为空栈非空那么E出栈p指向E的右子树E的右子树为空栈非空A出栈A的右子树为F不为空F进栈p指向F的左子树F的左子树为G不为空G进栈p指向G的左子树G的左子树为空栈非空G出栈p指向G的右子树G的右子树为空栈非空F出栈p指向F的右子树F的右子树为空栈为空那么遍历结束出栈的同时访问根结点在这里我省略了注意一下可能有点长可以耐心看一下
此时我们需要自己设置栈来保存结点的信息为什么能够实现中序基于栈的一些特点我们可以直到先进栈的后出栈因此左子树先进栈后一直保存在栈中而到退栈的地步时说明左子树一定为空所以此时来访问右子树并且在结点判断为非空时其一直保存在栈中并没有对其进行访问所以一定是先访问左子树的直到判断左子树为空时我们才将左子树对应的根结点出栈先访问根结点再去访问右子树。
在这里其实进栈的一直都是根结点
上述便是中序遍历的非递归算法极大地利用了栈的特点
先序遍历的非递归算法与中序类似与中序遍历的不同之处在于中序保存根结点而先序遍历我们可以保存右孩子的地址这样比较简单我们不再赘述
2后序遍历二叉树的非递归算法
我们首先说明一下中序遍历的非递归与后序遍历的非递归算法的异同
1相同点根结点进栈
2而后序遍历在pNULL时不能直接出栈访问根结点因为此时我们不能判断右孩子是否已经访问
那我们该在什么时候访问
1根的右子树为空2根有右孩子但是根的右子树已经访问过了
对于第二中情况我们如何判断根的右子树是否已经访问那我们就可以多设置一个指针记忆之前已经访问的结点
(以此二叉树为例
我们初始时设置p,q两个指针p用于移动q用于记忆已访问过的结点q初始值设置为NULL
首先根结点A不为空入栈p指向A的左子树
此时p为B,B不为空那么B入栈p指向B的左子树那么p为空栈非空并且此时B的右子树不为空并且qNULL,并不等于B的右子树说明B的右子树还没有访问过那么我们不访问根结点p指向B的右子树
p此时指向DD的左子树不为空D入栈p指向D的左子树此时p指向EE不为空E入栈p指向E的左子树p此时为空栈非空读取栈顶元素E并且q指向E的右子树E的右子树为空那么满足可以访问根结点的条件因此我们访问EE出栈此时设置q为E上面已经判断E的右子树为空p为空栈非空那么读取栈顶元素D此时D的右子树不为空并且q也不等于D的右子树那么说明D的右子树没有访问过此时pD的右子树Fp的右子树不为空F入栈p指向F的左子树F的左子树为空栈非空读取栈顶元素Fp指向F的右子树且F的右子树为空那么我们访问结点FF出栈并且令qF并且由于p为空栈非空读取栈顶元素D此时qD的右子树F满足访问条件访问D并且令qDD出栈下面分析出栈之后读取栈顶元素读取栈顶元素B此时qB的右子树满足访问的条件我们访问B并将qBB出栈分析访问完就出栈读取栈顶元素A此时A的右子树不为空并且q不等于A的右子树不满足访问根的条件因此我们访问A的右子树。
此时pC不为空C入栈p指向C的左子树C的左子树为空pNULL栈非空且C的右子树不为空q也不等于C的右子树G那么不满足访问的条件令pC的右子树GG不为空G入栈pG的左子树G的左子树为空栈非空G的右子树为空满足访问的条件因此访问G令qGG出栈再读取栈顶元素C此时qC的右子树G满足访问的条件访问C并且令qCC出栈读取栈顶元素A此时qA的右子树那么满足访问的条件访问A令qAA出栈此时栈为空且qA说明已经访问到最后一个结点处。遍历结束
经过以上过程的分析我们其实可以发现每次在有元素出栈后我们就开始读取栈顶元素而在我们访问完成结点后就进行出栈操作
综上所述就是后续遍历二叉树的非递归算法与中序遍历不同的是
加了一个起到记忆的作用的指针q用于记忆已经访问过的结点
加了一个读取栈顶元素的操作因为不能立即访问根结点出栈所以要先确定访问之后再出栈所以我们先读取不出栈即可。
除了上述区别之外中序遍历与后序遍历大同小异后续遍历更为复杂读者可以跟着上述内容自己走一遍这个二叉树的遍历的过程就能够理解上述思想 以上就是我对于二叉树的遍历的递归与非递归算法的一些个人总结与理解欢迎读者有更好的方法再评论区交流
