数据结构实验⼋⼆叉树的构造和遍历
实验⼋⼆叉树的构造和遍历
1、实验⽬的：
（1）理解⼆叉树的⼆叉链表存储。
（2）理解⼆叉树这种递归数据结构以及其操作的递归实现。
2、实验环境与设备：
已安装Visual Studio 2010（或其以上版本）集成开发环境的计算机。
3、实验原理：
raign
（1）⼆叉树的⼆叉链表存储。
（2）⼆叉树的三种遍历算法。
4、实验内容：
puppy是什么意思（1）基于标明空⼦树的先序遍历序列构造⼀棵采⽤⼆叉链表存储的⼆叉树。（空⼦树⽤“#”表⽰，如某棵⼆叉树的标明空⼦树的先序遍历序列为：ABC##DE#G##F###）
（2）设计递归算法分别对该⼆叉树做先序、中序、后序遍历，要求输出这三种遍历序列。
5、实验考核：
（1）完成纸质版实验报告
（2）提交电⼦版作业
6、执⾏结果⽰例如下：
英语词典免费下载
上述⼆叉树如下图所⽰。
#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 **ba;
bitree **top;
int stacksize;
}sqstack;// 链栈结点定义top栈顶 ba栈底且栈元素是指向⼆叉树结点的⼆级指针
int initstack(sqstack *s)
{
想念的英文
s->ba =(bitree *)malloc(STACK_INIT_SIZE*sizeof(bitree));//栈底指向开辟空间
if(!s->ba)exit(1);//抛出异常
s->top = s->ba;//栈顶=栈尾表⽰栈空
s->stacksize = STACK_INIT_SIZE;//栈长度为开辟空间⼤⼩
return1;
}
//进栈
int push(sqstack *s, bitree *e)
{
if(s->top - s->ba >= s->stacksize)//如果栈满追加开辟空间
{
s->ba =(bitree *)realloc(s->ba,(s->stacksize + STACKINCREMENT)*sizeof(bitree)); if(!s->ba)exit(1);//抛出异常
s->top = s->ba + s->stacksize;//感觉这⼀句没⽤
s->stacksize += STACKINCREMENT;
}
*(s->top)= e; s->top++;//进栈栈顶后移
return1;
}
//出栈
int pop(sqstack *s, bitree **e)
{
if(s->top == s->ba)return0;//栈空返回0
--s->top;*e =*(s->top);//栈顶前移取出栈顶元素给e
return1;
}
//取栈顶
中学英语教学论文
int gettop(sqstack *s, bitree **e)//去栈顶元素注意top指向的是栈顶的后⼀个
{
if(s->top == s->ba)return0;//所以 s->top-1
*e =*(s->top -1);
return1;
}
/*------------------------⾮递归-----先序建⽴⼆叉树----------------------------------*/
bitree *createprebitree()
{
char ch; bitree *ht,*p,*q;
sqstack *s;
s =malloc(sizeof(bitree));//加上这⼀句为s 初始化开辟空间
keep holding onch =getchar();
if(ch !='#'&&ch !='\n')/* 输⼊⼆叉树先序顺序是以完全⼆叉树的先序顺序
沈阳意大利语培训不是完全⼆叉树的把没有的结点以#表⽰ */
{
ht =(bitree *)malloc(sizeof(bitree));
ht->data = ch;
ht->lchild = ht->rchild =NULL;
p = ht;
initstack(s);
push(s, ht);//根节点进栈
while((ch =getchar())!='\n')// 算
{
q =(bitree *)malloc(sizeof(bitree));// 法
q->data = ch;//
if(p ==*(s->top -1)) p->lchild = q;// 核
el p->rchild = q;//
push(s, q); p = q;// ⼼
}//
el{
if(p ==*(s->top -1)) p->lchild =NULL;// 的
el p->rchild =NULL;//
pop(s,&p);
}// 步
//
}// 骤
return ht;
}
el return NULL;
}
/*--------------------------递归---------先序建⽴⼆叉树-------------------------------*/ void CreateBiTree(bitree **T){
//按先序次序输⼊⼆叉树中的结点的值（⼀个字符），空格字符表⽰空树，//构造⼆叉链表表⽰⼆叉树
char ch;
scanf_s("%c",&ch);
if(ch =='#')*T =NULL;
el{
*T =(bitree *)malloc(sizeof(bitree));
if(!*T)exit(1);
(*T)->data = ch;//⽣成根结点
CreateBiTree(&(*T)->lchild);//构造左⼦树
CreateBiTree(&(*T)->rchild);//构造右⼦树
}九月 英文
}
/*--------------------------⾮递归-------中序建⽴⼆叉树-------------------------------*/ /*--------------------------递归---------中序建⽴⼆叉树-------------------------------*/ /*--------------------------⾮递归-------后序建⽴⼆叉树-------------------------------*/ /*--------------------------递归---------后序建⽴⼆叉树-------------------------------*/ /*-----------------------⾮递归------先序输出⼆叉树------------------------------*/
void preordertraver(bitree *h)
{
sqstack m;
initstack(&m);
while(h || m.ba != m.top)
{
if(h){push(&m, h);printf("%c", h->data); h = h->lchild;}
el{
pop(&m,&h);
h = h->rchild;
}
}
}
/*------------------------⾮递归-----中序输出⼆叉树----------------------------*/
void inordertraver(bitree *h)
{
sqstack m;
initstack(&m);
while(h || m.ba != m.top)
{
if(h){push(&m, h); h = h->lchild;}
el{
pop(&m,&h);
printf("%c", h->data);
h = h->rchild;
}
}
}
remark用法/*---------------------⾮递归----后序遍历⼆叉树----------------------------------*/
void postordertraver(bitree *h)
{
sqstack m;
bitree *r = h;//使⽤r结点表⽰访问了右⼦树代替标志域
initstack(&m);
while(h || m.ba != m.top)
{
if(h){
acquit
push(&m, h);
h = h->lchild;
}
el{
gettop(&m,&h);
if(h->rchild&&h->rchild != r)
{
h = h->rchild;
push(&m, h);
h = h->lchild;
}
el{
pop(&m,&h);
printf("%c", h->data);
r = h; h =NULL;
}
}
}
}
/
/层次遍历⼆叉树⽤队列哈哈以后做
/*-------------------------------主过程-------------------------------*/
int main()
{
bitree *ht;
//printf("先序⾮递归建⽴⼀个⼆叉树:");
printf("以标明空⼦树的先序遍历序列构造⼆叉树:\n");
if((ht =createprebitree())!=NULL)//⾮递归建⽴
//CreateBiTree(&ht);
//if(ht!=NULL) //递归建⽴
{
printf("先序遍历输出⼆叉树:");
preordertraver(ht);
putchar('\n');
printf("中序遍历输出⼆叉树:");
inordertraver(ht);
putchar('\n');
printf("后序遍历输出⼆叉树:");
postordertraver(ht);
postordertraver(ht); putchar('\n');
}
el printf("空⼆叉树\n"); system("pau"); return0;
}
