当前位置： 首页 > news >正文

wordpress关站苏州疫情最新消息

news 2025/11/4 11:39:42
wordpress关站,苏州疫情最新消息,江西省建设厅网站资质升级查询,可以做旅游攻略的网站引言: 遍历二叉树：指按某条搜索路径巡访二叉树中每个结点，使得每个结点均被访问一次，而且仅被访问一次。 除了层次遍历外，二叉树有三个重要的遍历方法：先序遍历、中序遍历、后序遍历。 1、递归算法实现先序、中序、后…

引言:

遍历二叉树：指按某条搜索路径巡访二叉树中每个结点，使得每个结点均被访问一次，而且仅被访问一次。
除了层次遍历外，二叉树有三个重要的遍历方法：先序遍历、中序遍历、后序遍历。
1、递归算法实现先序、中序、后序遍历：

（1）先序遍历：

void PreOrderTraverse(BiTree T)
{if(T){cout<<T->data;PreOrderTraverse(T->lchild);PreOrderTraverse(T->rchild);}
}

（2）中序遍历：

void InOrderTraverse(BiTree T)
{   if(T){InOrderTraverse(T->lchild);cout<<T->data;InOrderTraverse(T->rchild);}
}

（3）后序遍历

void PostOrderTraverse(BiTree T)
{   if(T){  PostOrderTraverse(T->lchild); PostOrderTraverse(T->rchild); cout<<T->data;   }
}

2.非递归算法实现先序、中序、后序遍历：

采用非递归算法则需要利用栈来实现对二叉树的遍历：
（1）先序遍历非递归算法

void  PreOrder_non_recursion(BiTree T)//先序遍历的非递归算法 
{LinkStack S;InitStack (S);   BiTree p,q;p=T;while(p||!StackEmpty(S)){if(p){Push(S,*p); cout<<p->data; //访问根节点 p=p->lchild;   //遍历左子树 }else{Pop(S,*q);p=q->rchild;   //遍历右子树 }}
}

（2）中序遍历非递归算法

void  InOrder_non_recursion(BiTree T)//中序遍历的非递归算法 
{LinkStack S;InitStack (S);   BiTree p;    BiTree q; p=T;while(p||!StackEmpty(S)){if(p){Push(S,*p); p=p->lchild;   //遍历左子树 }else{Pop(S,*q);cout<<q->data; //访问根节点 p=q->rchild;   //遍历右子树 }}
}

（3）后序遍历非递归算法
（采用非递归算法实现对二叉树的后序遍历，会稍微复杂一些，本算法借用了两个栈结构）

void  PostOrder_non_recursion(BiTree T)//后序遍历的非递归算法 
{LinkStack l_S,r_S;InitStack (l_S);InitStack (r_S);BiTree p,q;    p=T;Push(l_S,*p);while(!StackEmpty(l_S)){Pop(l_S, *q);Push(r_S,*q);if(q->lchild){Push(l_S, *q->lchild);}if(q->rchild){Push(l_S,*q->rchild);}}while(!StackEmpty(r_S)){Pop(r_S,*q);cout<<q->data;}
}

3.完整代码

1、采用按照先序遍历的顺序建立二叉链表，用‘#’表示空树。如图所示：
在这里插入图片描述
2、先序遍历的递归与非递归算法的对比：

#include<iostream>
#define OK 1
#define ERROR 0
#define OVERFLOW -2
using namespace std;
typedef char TElemType;
typedef int Status;typedef struct BiTNode{  //二叉树的存储结构TElemType   data;	// 数据域struct  BiTNode *lchild; //左孩子指针struct  BiTNode *rchild; //右孩子指针
}BiTNode, *BiTree;typedef struct StackNode {  //栈的存储结构BiTNode data;       //栈数据元素类型为树结点型 struct StackNode *next;
} StackNode, *LinkStack;Status InitStack(LinkStack &S) { //栈初始化S = NULL;return OK;
}Status Push(LinkStack &S, BiTNode e) { //入栈LinkStack p;p = new StackNode; //生成新结点if (!p) {return OVERFLOW;}p->data = e; //将新结点数据域置为ep->next = S; //将新结点插入栈顶S = p; //修改栈顶指针为preturn OK;
}Status Pop(LinkStack &S, BiTNode &e) {  //出栈LinkStack p;if (S == NULL)return ERROR; //栈空e = S->data; //将栈顶元素赋给ep = S; //用p临时保存栈顶元素空间，以备释放S = S->next; //修改栈顶指针delete p; //释放原栈顶元素的空间return OK;
}bool StackEmpty(LinkStack S) {  //判断是否空栈if (!S)return true;return false;
}void CreateBiTree_PreOrder(BiTree &T){ //以先序次序创建二叉树 char ch; cin>>ch;if(ch=='#')T=NULL; else{T=new BiTNode;  //生成根结点T->data=ch; //根结点的数据域置为chCreateBiTree_PreOrder(T->lchild);//构造左子树CreateBiTree_PreOrder(T->rchild); //构造右子树}}void PreOrder(BiTree T){   //先序遍历的递归递归算法if(T){cout<<T->data;PreOrder(T->lchild);PreOrder(T->rchild);}
}void  PreOrder_non_recursion(BiTree T)//先序遍历的非递归算法 
{LinkStack S;InitStack (S);   BiTree p,q;p=T;while(p||!StackEmpty(S)){if(p){Push(S,*p); cout<<p->data; //访问根节点 p=p->lchild;   //遍历左子树 }else{Pop(S,*q);p=q->rchild;   //遍历右子树 }}
}int main() {BiTree T;cout<<"以先序次序创建二叉链表，以#表示空子树："<<endl;CreateBiTree_PreOrder(T);cout<<"先序序列（递归算法）："; PreOrder(T); cout<<"\n先序序列（非递归算法）："; PreOrder_non_recursion(T);return 0;
}

实验结果：
在这里插入图片描述
3、中序遍历的递归与非递归算法的对比：

#include<iostream>
#define OK 1
#define ERROR 0
#define OVERFLOW -2
using namespace std;
typedef char TElemType;
typedef int Status;typedef struct BiTNode{  //二叉树的存储结构TElemType   data;	// 数据域struct  BiTNode *lchild; //左孩子指针struct  BiTNode *rchild; //右孩子指针
}BiTNode, *BiTree;typedef struct StackNode {  //栈的存储结构BiTNode data;       //栈数据元素类型为树结点型 struct StackNode *next;
} StackNode, *LinkStack;Status InitStack(LinkStack &S) { //栈初始化S = NULL;return OK;
}Status Push(LinkStack &S, BiTNode e) { //入栈LinkStack p;p = new StackNode; //生成新结点if (!p) {return OVERFLOW;}p->data = e; //将新结点数据域置为ep->next = S; //将新结点插入栈顶S = p; //修改栈顶指针为preturn OK;
}Status Pop(LinkStack &S, BiTNode &e) {  //出栈LinkStack p;if (S == NULL)return ERROR; //栈空e = S->data; //将栈顶元素赋给ep = S; //用p临时保存栈顶元素空间，以备释放S = S->next; //修改栈顶指针delete p; //释放原栈顶元素的空间return OK;
}bool StackEmpty(LinkStack S) {  //判断是否空栈if (!S)return true;return false;
}void CreateBiTree_PreOrder(BiTree &T){ //以先序次序创建二叉树 char ch; cin>>ch;if(ch=='#')T=NULL; else{T=new BiTNode;  //生成根结点T->data=ch; //根结点的数据域置为chCreateBiTree_PreOrder(T->lchild);//构造左子树CreateBiTree_PreOrder(T->rchild); //构造右子树}}void InOrder(BiTree T){   //中序遍历的递归递归算法if(T){InOrder(T->lchild);cout<<T->data;InOrder(T->rchild);}
}void  InOrder_non_recursion(BiTree T)//中序遍历的非递归算法 
{LinkStack S;InitStack (S);   BiTree p;    BiTree q; p=T;while(p||!StackEmpty(S)){if(p){Push(S,*p); p=p->lchild;   //遍历左子树 }else{Pop(S,*q);cout<<q->data; //访问根节点 p=q->rchild;   //遍历右子树 }}
}int main() {BiTree T;cout<<"以先序次序创建二叉链表，以#表示空子树："<<endl;CreateBiTree_PreOrder(T);cout<<"中序序列（递归算法）："; InOrder(T); cout<<"\n中序序列（非递归算法）："; InOrder_non_recursion(T);return 0;
}

实验结果：
在这里插入图片描述

4、后序遍历的递归与非递归算法的对比：

#include<iostream>
#define OK 1
#define ERROR 0
#define OVERFLOW -2
using namespace std;
typedef char TElemType; 
typedef int Status;typedef struct BiTNode{  //二叉树的存储结构TElemType   data;	// 数据域struct  BiTNode *lchild; //左孩子指针struct  BiTNode *rchild; //右孩子指针
}BiTNode, *BiTree;typedef struct StackNode {  //栈的存储结构BiTNode data;       //栈数据元素类型为树结点型 struct StackNode *next;
} StackNode, *LinkStack;Status InitStack(LinkStack &S) { //栈初始化S = NULL;return OK;
}Status Push(LinkStack &S, BiTNode e) { //入栈LinkStack p;p = new StackNode; //生成新结点if (!p) {return OVERFLOW;}p->data = e; //将新结点数据域置为ep->next = S; //将新结点插入栈顶S = p; //修改栈顶指针为preturn OK;
}Status Pop(LinkStack &S, BiTNode &e) {  //出栈LinkStack p;if (S == NULL)return ERROR; //栈空e = S->data; //将栈顶元素赋给ep = S; //用p临时保存栈顶元素空间，以备释放S = S->next; //修改栈顶指针delete p; //释放原栈顶元素的空间return OK;
}bool StackEmpty(LinkStack S) {  //判断是否空栈if (!S)return true;return false;
}void CreateBiTree_PreOrder(BiTree &T){ //以先序次序创建二叉树 char ch; cin>>ch;if(ch=='#')T=NULL; else{T=new BiTNode;  //生成根结点T->data=ch; //根结点的数据域置为chCreateBiTree_PreOrder(T->lchild);//构造左子树CreateBiTree_PreOrder(T->rchild); //构造右子树}}void PostOrder(BiTree T){   //后序遍历的递归递归算法if(T){PostOrder(T->lchild);PostOrder(T->rchild);cout<<T->data;}
}void  PostOrder_non_recursion(BiTree T)//后序遍历的非递归算法 
{LinkStack l_S,r_S;InitStack (l_S);InitStack (r_S);BiTree p,q;    p=T;Push(l_S,*p);while(!StackEmpty(l_S)){Pop(l_S, *q);Push(r_S,*q);if(q->lchild){Push(l_S, *q->lchild);}if(q->rchild){Push(l_S,*q->rchild);}}while(!StackEmpty(r_S)){Pop(r_S,*q);cout<<q->data;}
}int main() {BiTree T;cout<<"以先序次序创建二叉链表，以#表示空子树："<<endl;CreateBiTree_PreOrder(T);cout<<"中序序列（递归算法）："; PostOrder(T); cout<<"\n中序序列（非递归算法）："; PostOrder_non_recursion(T);return 0;
}

实验结果：
在这里插入图片描述
欢迎大家一起来交流~

http://www.wangmingla.cn/news/81263.html

相关文章：

  • 阜宁做网站找哪家好免费网站制作平台
  • 网站在线咨询怎么做百度登陆页面
  • 公司网站不备案和备案有什么区别关键词搜索广告
  • wordpress调教重庆百度推广优化
  • 荆州网站建设360优化关键词
  • wordpress wp rocket淘宝seo搜索引擎优化
  • 智联招聘企业登录入口成都seo公司
  • 江西最近发生的新闻关键词首页优化
  • 武汉市建设委员会网站海南百度推广电话
  • 网站开发实用技术第2版网络推广员招聘
  • 商务网站建设的可行性分析包括谷歌seo外链平台
  • 网站的交互性seo顾问服务公司站长
  • 注册网站什么要求推广普通话宣传语100字
  • 怎样免费创建网站杭州seo营销公司
  • 公众号里的网站怎么做金华百度推广公司
  • wordpress能做什么网站青岛网站推广公司排名
  • 长沙的企业网站建设免费seo教程资源
  • 成都网站建设福州竞价外包
  • qq空间搬家wordpressseo是啥
  • 电商包括哪些平台北京seo费用是多少
  • 做博客网站要什么技术青岛seo网络推广
  • 大型商城网站开发郑州百度关键词seo
  • 北京网站建设公司怎么排版百度引流推广哪家好
  • 深圳政务服务网上大厅成都seo顾问
  • 网站运营数据周报表怎么做搜索引擎哪个最好用
  • 网站设计是不是会要用代码做公司网站推广费用
  • 哪个网站可以做条形码抖音账号权重查询入口
  • 如何在好医生网站做二类学分营销推广方案
  • 购物网站的设计与实现seo任务
  • 电子商务与网络营销题库seo的中文含义