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

1、实 验 项 目二叉树的操作项 目 类 型综合型完 成 时 间2009-11-2实 验 目 的及 要 求掌握二叉树的存储实现; 掌握二叉树的遍历思想; 掌握二叉树的常见算法的程序实现。【实验过程】（实验步骤、绘图、记录、数据、分析、结果）实验内容：a.输入完全二叉树的先序序列，用#代表虚结点（空指针），如ABD#CE#F# 建立二叉树，实现先序、中序和后序以及按层次遍历序列。b. 求所有叶子及结点总数。实验步骤：#include #include #define MAX 10#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;typedef struct BiTree *base; int top; int stacksize;SqStack; typedef structBiTree *base;int front;int rear;SqQueue; void InitStack(SqStack &S)/ 构造一个空栈S S.bas

3、e=(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; else return 0;/StcakEmptyvoid Push(SqStack &S, BiTree e)/ 插入元素e为新的栈顶元素, if (S.top=S.

4、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(SqStac

5、k S, BiTree &e) /若栈不空则用e返回S的栈顶元素 if (S.top=0) printf(栈空); return 0;/栈为空 else e=S.baseS.top-1; return 1; /GetTopvoid 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)/按照先序建立二叉树的二叉链表#表示虚结点char ch;ch

7、=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 PreOrderTraverse1(BiTree bt)/递归算法对二

8、叉树进行先序便利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)/层次遍历二叉树 SqQueue Q;BiTree p;if(bt) InitQ

9、ueue(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);/根指针进栈 while(!StackEmpty(S) while(

10、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(!StackEmpty(S) while(GetTop(

11、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 /while /if/ InOrderTraversevoid PostOrderTraverse2(BiTree bt) /非递归对bt进行后序遍历 SqStack S; BiTree p,q; InitStack(S); Push(S,bt);/根指针进栈 while(!StackEmpty(S) while(GetTop(S,p

12、)&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)/并且刚刚访问的结点为栈顶元素的右孩子时，让栈顶元素出栈并访问他 Pop(

13、S,p); printf(%2c,p-data); if(! StackEmpty (S) GetTop(S,p); Push(S,p-rchild); /if /if /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 bt

14、,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);InOrderTraverse1(bt);printf(n中序遍历二叉树非递归算法n);InOrderTraverse2(bt);printf(n后序遍历二叉树递归算法n);Post