首页 二叉树的各种遍历算法及其深度算法

二叉树的各种遍历算法及其深度算法

举报
开通vip

二叉树的各种遍历算法及其深度算法二叉树的各种遍历算法及其深度算法 二叉树的算法: 用扩展先序遍历序列创建二叉树; 递归遍历算法 中序非递归遍历 层次遍历 二叉树深度的算法 实现代码如下: #include #include #include typedef struct Node { char data; struct Node *LChild; struct Node *RChild; }BitNode,*BitTree; typedef struct CSNode { char data; struct CSN...

二叉树的各种遍历算法及其深度算法
二叉树的各种遍历算法及其深度算法 二叉树的算法: 用扩展先序遍历序列创建二叉树; 递归遍历算法 中序非递归遍历 层次遍历 二叉树深度的算法 实现代码如下: #include #include #include typedef struct Node { char data; struct Node *LChild; struct Node *RChild; }BitNode,*BitTree; typedef struct CSNode { char data; struct CSNode *fch, *nextSib; }CSNode, *CSTree; void CreatBiTree(BitTree *bt)//用扩展先序遍历序列创建二叉树,如果是#当前树根置为空, 否则申请一个新节点// { char ch; ch=getchar(); if(ch=='#')*bt=NULL; else { *bt=(BitTree)malloc(sizeof(BitNode)); (*bt)->data=ch; CreatBiTree(&((*bt)->LChild)); CreatBiTree(&((*bt)->RChild)); } } void Visit(char ch)//访问根节点 { printf("%c ",ch); } //以下为递归遍历算法 void PreOrder(BitTree root) /*先序遍历二叉树, root为指向二叉树(或某一子树)根结点的指 针*/ { if (root!=NULL) { Visit(root ->data); /*访问根结点*/ PreOrder(root ->LChild); /*先序遍历左子树*/ PreOrder(root ->RChild); /*先序遍历右子树*/ } } void InOrder(BitTree root) /*中序遍历二叉树, root为指向二叉树(或某一子树)根结点的指针*/ { if (root!=NULL) { InOrder(root ->LChild); /*中序遍历左子树*/ Visit(root ->data); /*访问根结点*/ InOrder(root ->RChild); /*中序遍历右子树*/ } } void PostOrder(BitTree root) /* 后序遍历二叉树,root为指向二叉树(或某一子树)根结点的指针*/ { if(root!=NULL) { PostOrder(root ->LChild); /*后序遍历左子树*/ PostOrder(root ->RChild); /*后序遍历右子树*/ Visit(root ->data); /*访问根结点*/ } } //中序非递归遍历 void InOrder1(struct Node *head) { struct Node *p; struct Node *stack[20]; int top=0; p=head; while(p||top!=0) { while (p) { stack[top++]=p; p=p->LChild ; } p=stack[--top]; printf("%c ",p->data ); p=p->RChild ; } } //层次遍历 void translevel(BitTree b) //按层次遍历 { struct node { BitTree *vec[100]; int f,r; } q; q.f=0; q.r=0; if (b!=NULL) printf("%c ",b->data); q.vec[q.r]=&b; //结点指针进入队列 q.r=q.r+1; while (q.fLChild!=NULL) //输出左孩子,并入队列 { printf("%c ",b->LChild->data); q.vec[q.r]=&(b->LChild); q.r=q.r+1; } if (b->RChild!=NULL) //输出右孩子,并入队列 { printf("%c ",b->RChild->data); q.vec[q.r]=&(b->RChild); q.r=q.r+1; } } } int PostTreeDepth(BitTree bt) //后序遍历求二叉树的高度递归算法// { int hl,hr,max; if(bt!=NULL) { hl=PostTreeDepth(bt->LChild); //求左子树的深度 hr=PostTreeDepth(bt->RChild); //求右子树的深度 max=hl>hr?hl:hr; //得到左、右子树深度较大者 return(max+1); //返回树的深度 } else return(0); //如果是空树,则返回0 } int main() { BitTree T; CSTree tree1; printf("请输入二叉树中的元素(以扩展先序遍历序列输入,其中#代 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 空子树):\n"); CreatBiTree(&T); printf("先序递归遍历序列为: "); PreOrder(T); printf("\n中序递归遍历序列为: "); InOrder(T); printf("\n后序递归遍历序列为: "); PostOrder(T); printf("\n中序非递归遍历序列为:"); InOrder1(T); printf("\n层次归遍历序列为: "); translevel(T); printf("\nThe depth of this tree is:%d\n",PostTreeDepth(T)); return 0; } 运行结果如图
本文档为【二叉树的各种遍历算法及其深度算法】,请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑, 图片更改请在作品中右键图片并更换,文字修改请直接点击文字进行修改,也可以新增和删除文档中的内容。
该文档来自用户分享,如有侵权行为请发邮件ishare@vip.sina.com联系网站客服,我们会及时删除。
[版权声明] 本站所有资料为用户分享产生,若发现您的权利被侵害,请联系客服邮件isharekefu@iask.cn,我们尽快处理。
本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用。
网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
下载需要: 免费 已有0 人下载
最新资料
资料动态
专题动态
is_321635
暂无简介~
格式:doc
大小:32KB
软件:Word
页数:7
分类:互联网
上传时间:2017-09-18
浏览量:31