全文预览已结束
下载本文档
版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
实验四 树和二叉树的应用 #include “stdio.h“ #include “stdlib.h“ #define STACK_INIT_SIZE 10 /栈的初始长度 #define STACKINCREMENT 5 /栈的追加长度 typedef struct bitree char data; struct bitree *lchild,*rchild; bitree; /二叉树结点定义 typedef struct bitree *base; bitree *top; int stacksize; sqstack; / 链栈结点定义 top 栈顶 base 栈底 且栈元素是指向二叉树结点 的二级指针 /建立一个空栈 int initstack(sqstack *s) s-base=(bitree *)malloc(STACK_INIT_SIZE*sizeof(bitree); /栈底指向开辟空间 if(!s-base) exit(1); /抛出异常 s-top=s-base; /栈顶=栈尾 表示栈空 s-stacksize=STACK_INIT_SIZE; /栈长度为开辟空间大小 return 1; /进栈 int push(sqstack *s,bitree *e) if(s-top-s-base=s-stacksize) /如果栈满 追加开辟空间 s-base=(bitree *)realloc (s-base,(s-stacksize+STACKINCREMENT)* sizeof(bitree); if(!s-base) exit(1); /抛出异常 s-top=s-base+s-stacksize; /感觉这一句没用 s-stacksize+=STACKINCREMENT; *(s-top)=e;s-top+; /进栈 栈顶后移 return 1; /出栈 int pop(sqstack *s,bitree *e) if(s-top=s-base) return 0; /栈空 返回 0 -s-top;*e=*(s-top); /栈顶前移 取出栈顶元素给 e return 1; /取栈顶 int gettop(sqstack *s,bitree *e) /去栈顶元素 注意 top 指向的是栈顶的后一 个 if(s-top=s-base) return 0; /所以 s-top-1 *e=*(s-top-1); return 1; /*-非递归-先序建立二叉树-*/ bitree *createprebitree() char ch;bitree *ht,*p,*q; sqstack *s; s=malloc(sizeof(bitree); /加上这一句为 s 初始化开辟空间 ch=getchar(); if(ch!=# ht-data=ch; ht-lchild=ht-rchild=NULL; p=ht; initstack(s); push(s,ht); /根节点进栈 while(ch=getchar()!=n) / 算 if(ch!=#) q=(bitree *)malloc(sizeof(bitree); / 法 q-data=ch; / if(p=*(s-top-1) p-lchild=q; / 核 else p-rchild=q; / push(s,q);p=q; / 心 / else if(p=*(s-top-1) p-lchild=NULL; / 的 else p-rchild=NULL; / pop(s, / 步 / / 骤 return ht; else return NULL; /*-递归- 先序建立二叉树-*/ void CreateBiTree(bitree *T) /按先序次序输入二叉树中的结点的值(一个字符) ,空格字符表示空树, /构造二叉链表表示二叉树 char ch; scanf(“%c“, if(ch=#) *T=NULL; else *T=(bitree * )malloc(sizeof(bitree); if(!*T) exit(1); (*T)-data=ch; /生成根结点 CreateBiTree( /构造左子树 CreateBiTree( /构造右子树 /*-非递归-中序建立二叉树-*/ /*-递归- 中序建立二叉树-*/ /*-非递归-后序建立二叉树-*/ /*-递归- 后序建立二叉树-*/ /*-非递归-先序输出二叉树-*/ void preordertraverse(bitree *h) sqstack m; initstack( while(h|m.base!=m.top) if(h) push(printf(“%c“,h-data);h=h-lchild; elsepop( h=h-rchild; /*-非递归-中序输出二叉树-*/ void inordertraverse(bitree *h) sqstack m; initstack( while(h|m.base!=m.top) if(h) push(h=h-lchild; else pop( printf(“%c“,h-data); h=h-rchild; /*-非递归-后序遍历二叉树-*/ void postordertraverse(bitree *h) sqstack m; initstack( while(h|m.base!=m.top) if(h) push( h=h-lchild; else bitree *r; /使用 r 结点表示访问了右子树 代替标志域 gettop( if(h-rchild push( h=h-lchild; elsepop( printf(“%c“,h-data); r=h;h=NULL; /层次遍历二叉树 用队列 哈哈以后做 /*-主过程-*/ int main() bitree *ht; printf(“先序非递归建立一个二叉树:“); if(ht=createprebitree()!=NULL) /非递归建立 /CreateBiTree( /if(ht!=NULL) /递归建立 printf(“先序遍历输出二叉树:“); preordertraverse(ht); putchar(
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 2024年3月全国二手车市场深度分析
- 2024年三亚市《高等数学(一)》(专升本)考前冲刺试卷含解析
- 无烟为成长护航
- 2022年湖南省郴州市人教PEP版六年级下册小升初全真模拟测试英语试卷(十四)
- 中学教育托管服务投标方案(技术方案技术标)
- 2015年内蒙古公路造价师基础理论与法规:运输合同考试题
- 同业存款协议模板
- 旧房屋改造合同6篇
- 艰难曲折的探索历程教案5-北师大版
- 教你攻克学习上的三大难题作文1000字高分作文
- 大国安全智慧树知到期末考试答案2024年
- 2024下半年上海市嘉定区社区工作者招聘33人历年高频考题难、易错点模拟试题(共500题)附带答案详解
- 2024年全国行业职业技能竞赛(电力交易员)备考试题库大全(浓缩800题)
- 科普项目管理办法
- 幼儿园镇村一体化管理工作总结
- 继承优良传统弘扬中国精神 (模板)
- 新森林父母教养方案
- 健康体重-课件
- 好利来品牌介绍
- 进出口用原料质量标准 β-烟酰胺单核苷酸
- 宇宙生命之谜 市赛一等奖完整版
评论
0/150
提交评论