《数据结构》
第六次实验报告。
1、实验内容。
1) 采用二叉树链表作为存储结构，完成二叉树的建立，先序、中序和后序以及按层次遍历的操作，求所有叶子及结点总数的操作。
2) 输出树的深度，最大元，最小元。
2、需求分析。
遍历二叉树首先有三种方法，即先序遍历，中序遍历和后序遍历。
递归方法比较简单，首先获得结点指针如果指针不为空，且有左子，从左子递归到下一层，如果没有左子，从右子递归到下一层，如果指针为空，则结束一层递归调用。直到递归全部结束。
下面重点来讲述非递归方法：
首先介绍先序遍历：
先序遍历的顺序是根左右，也就是说先访问根结点然后访问其左子再然后访问其右子。具体算法实现如下：如果结点的指针不为空，结点指针入栈，输出相应结点的数据，同时指针指向其左子，如果结点的指针为空，表示左子树访问结束，栈顶结点指针出栈，指针指向其右子，对其右子树进行访问， 如此循环，直至结点指针和栈均为空时，遍历结束。
再次介绍中序遍历：
中序遍历的顺序是左根右，中序遍历和先序遍历思想差不多，只是打印顺序稍有变化。具体实现算法如下：如果结点指针不为空，结点入栈，指针指向其左子，如果指针为空，表示左子树访问完成，则栈顶结点指针出栈，并输出相应结点的数据，同时指针指向其右子，对其右子树进行访问。
如此循环直至结点指针和栈均为空，遍历结束。
最后介绍后序遍历：
后序遍历的顺序是左右根，后序遍历是比较难的一种，首先需要建立两个栈，一个用来存放结点的指针，另一个存放标志位，也是首先访问根结点，如果结点的指针不为空，根结点入栈，与之对应的标志位也随之入标志位栈，并赋值0，表示该结点的右子还没有访问，指针指向该结点的左子，如果结点指针为空，表示左子访问完成，父结点出栈，与之对应的标志位也随之出栈，如果相应的标志位值为0，表示右子树还没有访问，指针指向其右子，父结点再次入栈，与之对应的标志位也入栈，但要给标志位赋值为1，表示右子访问过。如果相应的标志位值为1，表示右子树已经访问完成，此时要输出相应结点的数据，同时将结点指针赋值为空，如此循环直至结点指针和栈均为空，遍历结束。
三、详细设计。
源**：#include<>
#define max 100 //表示栈的最大容量。
#define full 99//表示栈满。
#define empty -1//表示栈空。
typedef struct tnode //定义结点。
char data;//存储结点数据。
struct tnode *left;//定义结点左子指针。
struct tnode *right;//定义右子指针。
tnode,*pnode;//声明tnode类型的变量和指针。
typedef struct stack//定义栈。
pnode pnode[max];/存放数据。
int p;//栈顶指针。
stack,*pstack;//定义stack类型的变量和指针。
void push (pstack pstack,pnode pnode)//入栈。
pstack->p ++
pstack->pnode[pstack->p] =pnode;//赋值。
pnode pop(pstack pstack)//出栈。
return pstack->pnode[pstack->p--]
pnode top (pstack pstack)//看栈顶元素。
return pstack->pnode[pstack->p];
int isempty (pstack pstack)//栈判空。
if(pstack->p==empty)
return 1;
else return 0;;
int isfull (pstack pstack )/栈满。
if (pstack ->p==full)
return 1;
else return 0;
void initstack (pstack pstack)//初始化栈。
pstack->p=empty;
void inittnode(pnode root,pnode left,pnode right,char data)//初始化结点。
root->left=left;
root->right = right;
root->data = data;
void preorderr(pnode proot)//递归先序遍历算法。
if(proot)
void inorderr(pnode proot)//递归中序遍历算法。
if(proot)
void postorderr(pnode proot)//递归后序遍历算法。
if(proot)
void preorderi(pnode proot,pstack pstack)//非递归先序遍历算法。
initstack(pstack);/初始化栈。
while(proot||!isempty(pstack))/如果栈空并且结点指针空，则结束循环。else
void inorderi(pnode proot,pstack pstack)//非递归中序遍历算法。
initstack(pstack);/初始化栈。
while(proot||!isempty(pstack))/循环结束条件。else
void postorderi(pnode proot,pstack pstack)//非递归后续遍历算法。
int flags[max];/定义标志位栈。
int p =-1;//初始化标志位栈。
int flag;//存放标志位。
initstack(pstack);/初始化栈。
while(proot||!isempty(pstack))/循环结束条件。else
void main ()
tnode a,b,c,d,e,f,g;//声明结点变量。
stack stack;//声明栈。
inittnode(&a,&b,&c,'a');初始化结点。
inittnode(&b,null,&d,'b');
inittnode(&c,&e,&f,'c');
inittnode(&d,null,null,'d');
inittnode(&e,null,null,'e');
inittnode(&f,&g,null,'f');
inittnode(&g,null,null,'g');
printf("你定义的树的结构是：");
/*一下是调用相应的函数输出遍历结果*/
printf("a(b(d)c(e f(g)))n");
printf下面是遍历结果n");
printf递归先序遍历n");
preorderr(&a);
printf("");
printf非递归先序遍历n");
preorderi(&a,&stack);
printf("");
printf递归中序遍历n");
inorderr(&a);
printf("");
数据结构习题第六章树和二叉树答案
第六章树和二叉树。注 参 只能作为参考，也是有错的，自己要学会辨别。一 单项选择题。3 a4 c 5 b6 d 7 e8.d 9 c10 b 11.c12 a 13 d14 b 15 c16 b 17 d18 b 19.d20 c 二 判断题 在各题后填写 或 1.完全二叉树一定存在度为1的结点。2...
数据结构考研复习题第六章 数和二叉树 带答案
第六章树和二叉树。一 选择题。1 已知一算术表达式的中缀形式为 a b c d e，后缀形式为abc de 其前缀形式为 a a b c de b.a b cd e c abc ded.a bc de 北京航空航天大学 1999 一 3 2分 2 算术表达式a b c d e 转为后缀表达式后为 中...
数据结构队列实验报告
队列实验报告。小组成员 xx日期 xx 1 需求分析 1.链队列。1 在本演示程序中，首先要链队列添加一个头结点，并判断队列是否为空，它只允许在表的一端进行插入，而在另一端删除元素，允许插入的一段叫队尾，允许删除的一端则为对头，接着访问队列中所有元素，并输出，输出是每个元素之间用空格来完成。最后销毁...