二叉树的各种基本作实验报告.docx

《二叉树的各种基本作实验报告.docx》由会员分享，可在线阅读，更多相关《二叉树的各种基本作实验报告.docx（9页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、实验项目二叉树的操作最好的沉淀项目类型综合型完成 时间2009-11-2实 验 目 的及要 求掌握二叉树的存储实现;掌握二叉树的遍历思想; 掌握二叉树的 常见算法的程序实现。【实验过程】（实验步骤、绘图、记录、数据、分析、结果）实验内容：a.输入完全二叉树的先序序列， 用 #代表虚结点 （空指针），如 ABD#CE#F# 建 立二叉树，实现先序、中序和后序以及按层次遍历序列。b. 求所有叶子及结点总数。实验步骤：#include #include #define MAX10#define STACK_INIT_SIZE 40/ 存储空间初始分配量#define STACKINCREMENT 1

2、0 / 存储空间分配增量typedef struct BiTNodechar data;struct BiTNode *lchild; struct BiTNode *rchild;BiTNode,*BiTree;/ 将 BiTree 定义为指向二叉链表结点结构的指针类型BiTNode *bt;typedefstruct BiTree *base; int top;intstacksize;SqStack;typedef structBiTree *base;int front; int rear;SqQueue;void InitStack(SqStack &S)/ 构造一个空栈 SS.ba

3、se=(BiTree*) malloc(STACK_INIT_SIZE*sizeof(BiTree); if (!S.base) exit (0);/存储分配失败S.top=0;/ 空表长度为 0 S.stacksize=STACK_INIT_SIZE;/初始存储容量/InitStackint StackEmpty(SqStack &S)/ 判断栈 S 是否是空栈，是返回1，否则返回 0 if(S.top=0)return 1;elsereturn 0;/StcakEmptyvoid Push(SqStack &S, BiTree e)/ 插入元素 e 为新的栈顶元素 , if (S.top=

4、S.stacksize)/ 栈满追加空间S.base=(BiTree*) realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(BiTree);if(!S.base)exit(0);/存储分配失败S.stacksize+=STACKINCREMENT;S.baseS.top+=e;/Pushvoid Pop(SqStack &S,BiTree &e)/若栈不空则删除S 的栈顶元素，并用e返回其值if (S.top=0)printf( 栈空 );/栈为空exit(0);e=S.base-S.top;/Popint GetTop(SqStack S,

5、 BiTree &e)/若栈不空则用 e 返回 S 的栈顶元素if (S.top=0)elseprintf( 栈空 ); return 0;/栈为空/GetTope=S.baseS.top-1; return 1;void InitQueue(SqQueue &Q)/ 构建新队列 QQ.base=(BiTree*)malloc(MAX * sizeof(BiTree); Q.front=Q.rear=0;int QueueEmpty(SqQueue Q)/ 判断队列是否是一个空队列if(Q.front=Q.rear) return 1;return 0;void EnQueue(SqQueue

6、 &Q,BiTree e)/ 将元素 e 插入到队列 Q 中if(Q.rear+1)%MAX=Q.front) exit(0);Q.baseQ.rear=e;Q.rear=(Q.rear+1)%MAX;void DeQueue(SqQueue &Q,BiTree &e)/ 将非空队列 Q 的队头元素出队列if(Q.front=Q.rear) exit(0);e=Q.baseQ.front; Q.front=(Q.front+1)%MAX;/int n0,n;/n0 统计叶子结点数， n 统计总的结点数void PreCreatBiTree(BiTree &bt)/ 按照先序建立二叉树的二叉链表

7、#表示虚结点char ch; ch=getchar(); if(ch=#)bt=NULL;elsebt=(BiTree)malloc(sizeof(BiTNode); bt-data=ch;PreCreatBiTree(bt-lchild);PreCreatBiTree(bt-rchild);void InOrderTraverse1(BiTree bt)/ 利用递归算法中序遍历一个二叉树if(bt)InOrderTraverse1(bt-lchild); printf(%2c,bt-data); InOrderTraverse1(bt-rchild);void PreOrderTravers

8、e1(BiTree bt)/ 递归算法对二叉树进行先序便利if(bt)printf(%2c,bt-data); PreOrderTraverse1(bt-lchild); PreOrderTraverse1(bt-rchild);void PostOrderTraverse1(BiTree bt)/ 利用递归后序遍历二叉树if(bt)PostOrderTraverse1(bt-lchild); PostOrderTraverse1(bt-rchild); printf(%2c,bt-data);void LeverlOrderTraverse(BiTree bt)/ 层次遍历二叉树 SqQue

9、ue Q; BiTree p; if(bt)InitQueue(Q); EnQueue(Q,bt); while(!QueueEmpty(Q)DeQueue(Q,p); printf(%2c,p-data); if(p-lchild)EnQueue(Q,p-lchild);if(p-rchild)EnQueue(Q,p-rchild);/while/if/LeverlOrderTraversevoid PreOrderTraverse2(BiTree bt)/非递归对 bt 进行先序遍历SqStack S; BiTree p;if(bt)InitStack(S);Push(S, bt);/根指

10、针进栈 while(!StackEmpty(S)while(GetTop(S,p) & p)printf(%2c,p-data); Push(S, p-lchild);/向左一直走到尽头Pop(S,p);/空指针退栈 if(!StackEmpty(S)Pop(S,p);Push(S, p-rchild);/while/if/ PreOrderTraversevoid InOrderTraverse2(BiTree bt)/ 非递归对 bt 进行中序遍历if(bt)SqStack S; BiTree p; InitStack(S);Push(S, bt); /根指针进栈while(!StackE

11、mpty(S)while(GetTop(S,p)&p)/ 栈顶元素非空Push(S, p-lchild);/向左一直走到尽头 Pop(S, p);/空指针退栈if(!StackEmpty(S)Pop(S,p); printf(%2c,p-data); Push(S, p-rchild);/if/if/while/ InOrderTraversevoid PostOrderTraverse2(BiTree bt)/非递归对 bt 进行后序遍历SqStack S; BiTree p,q; InitStack(S);Push(S,bt);/根指针进栈while(!StackEmpty(S)while

12、(GetTop(S,p)&p) / 栈顶元素非空 Push(S,p-lchild);/向左一直走到尽头 Pop(S,p);/空指针退栈/对左子树操作完毕，再判断右子树 if(!StackEmpty(S)/ 栈非空GetTop(S,p);Push(S,p-rchild);/右孩子入栈if(GetTop(S,p)&p=NULL)素出栈并访问他Pop(S,p); /空结点出栈 Pop(S,p); /左右孩子处理完了printf(%2c,p-data);/ 访问根结点while(!StackEmpty(S)&GetTop(S,q)&q-rchild=p)/并且刚刚访问的结点为栈顶元素的右孩子时，让栈顶

13、元Pop(S,p); printf(%2c,p-data);if(! StackEmpty (S)/if/ifGetTop(S,p); Push(S,p-rchild);/PostOrderTraversevoid PutOutLeaf(BiTree bt)/ 返回值为 bt 的叶子数if(bt)if(bt-lchild=NULL&bt-rchild=NULL)printf(%2c,bt-data);elseif(bt-lchild)PutOutLeaf(bt-lchild);if(bt-rchild)PutOutLeaf(bt-rchild);void CountNodes(BiTree b

14、t,int &n)/ 输出总的节点数if(bt)n+;CountNodes( bt-lchild,n); CountNodes( bt-rchild,n);void main()int n=0;printf( 先序建立二叉树 ,#代表虚结点 n); printf( 请输入你所建立二叉树的字符串n); PreCreatBiTree(bt);printf(n);printf( 先序遍历二叉树递归算法n); PreOrderTraverse1(bt);printf(n 先序遍历二叉树非递归算法n);PreOrderTraverse2(bt);printf(n 中序遍历二叉树递归算法n); InOrd

15、erTraverse1(bt);printf(n 中序遍历二叉树非递归算法n);InOrderTraverse2(bt);printf(n 后序遍历二叉树递归算法n); PostOrderTraverse1(bt);printf(n 后序遍历二叉树非递归算法n);PostOrderTraverse2(bt); printf(n 层次遍历二叉树 n); LeverlOrderTraverse(bt); printf(n 叶子结点是 n); PutOutLeaf(bt); CountNodes(bt,n);printf(n 结点总数是 :%d,n);printf(n); 实验运行结果教师批阅评语：成绩评定良中及优秀好等格不及格教师签名 :年月日