树和二叉树(一)数据结构实验

1、实验报告五月 142015姓名：陈斌 学号：E11314079 专业：13计算机科学与技术数据结构 第三次实验学号 E11314079 专业 计算机科学与技术 姓名 陈 斌 实验日期 2015.05.14 教师签字 成绩 实 验 报 告【实验名称】 树和二叉树（一） 【实验目的】 1. 掌握二叉树的二叉链表存储表示；2. 掌握二叉树的遍历算法；3. 运用遍历算法求解有关问题。【实验内容】1. 必做内容任务1：以算法6.4创建二叉树的存储结构，树的具体形态自定。任务2：对任务1中的二叉树分别实现先序、中序、后序遍历（递归实现）和中序遍历的非递归实现以及层序遍历；任务3：统计1中树的结点总数、叶子

2、结点总数以及树的高度；源代码：head.h: #include<string.h>#include<ctype.h>#include<malloc.h> /malloc( )#include<limits.h> / INT ,MAX#include<stdio.h> /EOF,NULL#include<stdlib.h> /atoi( )#include<io.h> /eof( )#include<math.h> /floor( ),ceil( ),abs( )#include<process

3、.h> /exit( )#include<iostream.h> /cout,cin/函数结果状态代码#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define INFEASIBLE -1/OVERFLOW 在 math.h 中已定义为3typedef int Status;typedef int Boolean; / 布尔类型head2.h:#define STACK_INIT_SIZE 100#define STACKINCREMENT 10typedef structSElemType *base;SE

4、lemType *top;int stacksize;SqStack;typedef struct QNode QElemType data; struct QNode *next;QNode,*QueuePtr;typedef struct QueuePtr front,rear; /* 队头、队尾指针 */LinkQueue;Status InitStack(SqStack &S) /* 构造一个空栈S */ S.base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType); if(!S.base) exit(OVERFLOW

5、); /* 存储分配失败 */ S.top=S.base; S.stacksize=STACK_INIT_SIZE; return OK;Status StackEmpty(SqStack &S) /* 若栈S为空栈，则返回TRUE，否则返回FALSE */ if(S.top=S.base) return TRUE; else return FALSE;Status GetTop(SqStack &S,QElemType &e) /* 若栈不空，则用e返回S的栈顶元素，并返回OK；否则返回ERROR */ if(S.top>S.base) e=*(S.top-1)

6、; return OK; else return ERROR;Status Push(SqStack &S,QElemType &e) /* 插入元素e为新的栈顶元素 */ if(S.top-S.base>=S.stacksize) /* 栈满，追加存储空间 */ S.base=(SElemType *)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(SElemType); if(!S.base) exit(OVERFLOW); /* 存储分配失败 */ S.top=S.base+S.stacksize; S.stac

7、ksize+=STACKINCREMENT; *S.top+=e; return OK;Status Pop(SqStack &S,QElemType &e) /* 若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR */ if(S.top=S.base) return ERROR; e=*-S.top; return OK;Status InitQueue(LinkQueue &Q) /* 构造一个空队列Q */ Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode); if(!Q.front) exit(O

8、VERFLOW); Q.front->next=NULL; return OK;Status QueueEmpty(LinkQueue &Q) /* 若Q为空队列,则返回TRUE,否则返回FALSE */ if(Q.front=Q.rear) return TRUE; else return FALSE;Status EnQueue(LinkQueue &Q,QElemType e) /* 插入元素e为Q的新的队尾元素 */ QueuePtr p=(QueuePtr)malloc(sizeof(QNode); if(!p) /* 存储分配失败 */ exit(OVERFL

9、OW); p->data=e; p->next=NULL; Q.rear->next=p; Q.rear=p; return OK;Status DeQueue(LinkQueue &Q,QElemType &e) /* 若队列不空,删除Q的队头元素,用e返回其值,并返回OK,否则返回ERROR */ QueuePtr p; if(Q.front=Q.rear) return ERROR; p=Q.front->next; e=p->data; Q.front->next=p->next; if(Q.rear=p) Q.rear=Q.f

10、ront; free(p); return OK;main.cpp:typedef char TElemType;#include"head.h"typedef struct BiTNodeTElemTypedata;struct BiTNode *lchild,*rchild;BiTNode,*BiTree;typedef BiTree QElemType; /* 设队列元素为二叉树的指针类型 */typedef BiTree SElemType; /* 设栈元素为二叉树的指针类型 */#include"head2.h"Status InitBiTre

11、e(BiTree &T) /* 操作结果: 构造空二叉树T */ T=NULL; return OK;Status CreateBiTree(BiTree &T) / 算法6.4:按先序次序输入二叉树中结点的值(字符型)，构造二叉链表表示的二叉树T。 TElemType ch; scanf("%c",&ch); if(ch=' ') /* 空 */ T=NULL; else T=(BiTree)malloc(sizeof(BiTNode); if(!T) exit(OVERFLOW); T->data=ch; /* 生成根结点

12、*/ CreateBiTree(T->lchild); /* 构造左子树 */ CreateBiTree(T->rchild); /* 构造右子树 */ return OK;Status PreOrderTraverse(BiTree T,Status(*Visit)(TElemType) /* 初始条件: 二叉树T存在,Visit是对结点操作的应用函数。算法6.1 */ /* 操作结果: 先序递归遍历T,对每个结点调用函数Visit一次且仅一次 */ if(T) /* T不空 */ if(Visit(T->data) /* 先访问根结点 */if(PreOrderTrave

13、rse(T->lchild,Visit) /* 再先序遍历左子树 */if(PreOrderTraverse(T->rchild,Visit) /* 最后先序遍历右子树 */return OK;return ERROR; else return OK;Status InOrderTraverse(BiTree T,Status(*Visit)(TElemType) /* 初始条件: 二叉树T存在,Visit是对结点操作的应用函数 */ /* 操作结果: 中序递归遍历T,对每个结点调用函数Visit一次且仅一次 */ if(T) if(InOrderTraverse(T->lc

14、hild,Visit) /* 先中序遍历左子树 */if(Visit(T->data) /* 再访问根结点 */if(InOrderTraverse(T->rchild,Visit) /* 最后中序遍历右子树 */return OK;return ERROR; else return OK;Status PostOrderTraverse(BiTree T,Status(*Visit)(TElemType) /* 初始条件: 二叉树T存在,Visit是对结点操作的应用函数 */ /* 操作结果: 后序递归遍历T,对每个结点调用函数Visit一次且仅一次 */ if(T) /* T不

15、空 */ if(PostOrderTraverse(T->lchild,Visit) /* 先后序遍历左子树 */if(PostOrderTraverse(T->rchild,Visit) /* 再后序遍历右子树 */if(Visit(T->data) /* 最后访问根结点 */return OK;return ERROR; else return OK;Status InOrderTraverse1(BiTree T,Status(*Visit)(TElemType) /* 采用二叉链表存储结构，Visit是对数据元素操作的应用函数。 */ /* 中序遍历二叉树T的非递归算

16、法(利用栈)，对每个数据元素调用函数Visit */ SqStack S; InitStack(S); while(T|!StackEmpty(S) if(T) /* 根指针进栈,遍历左子树 */ Push(S,T); T=T->lchild; else /* 根指针退栈,访问根结点,遍历右子树 */ Pop(S,T); if(!Visit(T->data) return ERROR; T=T->rchild; printf("n"); return OK;Status InOrderTraverse2(BiTree T,Status(*Visit)(TE

17、lemType) /* 采用二叉链表存储结构，Visit是对数据元素操作的应用函数。算法6.2 */ /* 中序遍历二叉树T的非递归算法(利用栈)，对每个数据元素调用函数Visit */ SqStack S; BiTree p; InitStack(S); Push(S,T); /* 根指针进栈 */ while(!StackEmpty(S) while(GetTop(S,p)&&p) Push(S,p->lchild); /* 向左走到尽头 */ Pop(S,p); /* 空指针退栈 */ if(!StackEmpty(S) /* 访问结点,向右一步 */ Pop(S,

18、p); if(!Visit(p->data) return ERROR; Push(S,p->rchild); printf("n"); return OK;void LevelOrderTraverse(BiTree T,Status(*Visit)(TElemType) /* 初始条件：二叉树T存在,Visit是对结点操作的应用函数 */ /* 操作结果：层序递归遍历T(利用队列),对每个结点调用函数Visit一次且仅一次 */ LinkQueue q; QElemType a; if(T) InitQueue(q); EnQueue(q,T); while

19、(!QueueEmpty(q) DeQueue(q,a); Visit(a->data); if(a->lchild!=NULL) EnQueue(q,a->lchild); if(a->rchild!=NULL) EnQueue(q,a->rchild); printf("n"); Status visitT(TElemType e) printf("%c ",e); return OK;Status BiTreeNodeNum(BiTree T)/结点总个数if(T)return BiTreeNodeNum(T->

20、lchild)+BiTreeNodeNum(T->rchild)+1;elsereturn 0;Status BiTreeLeafNodeNum(BiTree T)/叶子结点个数if(T)if(!T->lchild&&!T->rchild)return 1;elsereturn BiTreeLeafNodeNum(T->lchild)+BiTreeLeafNodeNum(T->rchild);else return 0;Status BiTreeDepth(BiTree T)/树的深度if(!T)return 0;elsereturn (BiTre

21、eDepth(T->lchild)>BiTreeDepth(T->rchild)?BiTreeDepth(T->lchild):BiTreeDepth(T->rchild)+1;void main()BiTree T;InitBiTree(T);cout<<"请先序输入二叉树(如:ab三个空格表示a为根结点,b为左子树的二叉树):"<<endl;CreateBiTree(T);cout<<"先序遍历序列:"<<endl;PreOrderTraverse(T,visitT);co

22、ut<<endl;cout<<"中序遍历序列:"<<endl;InOrderTraverse(T,visitT);cout<<endl;cout<<"后序遍历序列:"<<endl;PostOrderTraverse(T,visitT);cout<<endl;cout<<"中序遍历的非递归实现1(利用栈):"<<endl;InOrderTraverse1(T,visitT);cout<<"中序遍历的非递归实现

23、2(利用栈):"<<endl;InOrderTraverse2(T,visitT);cout<<"层序遍历(利用队列):"<<endl;LevelOrderTraverse(T,visitT);cout<<"树的结点总数为:"<<BiTreeNodeNum(T)<<endl;cout<<"树的叶子结点总数为:"<<BiTreeLeafNodeNum(T)<<endl;cout<<"树的深度为:&q

24、uot;<<BiTreeDepth(T)<<endl;运行结果：A树的形状：BCDGEFH先序输入：ABG CDE H F ( “ ” 代表空格)2. 选做内容任务4：修改算法6.4（结点及二叉树类型分别用BiThrNode，BiThrTree，创建根结点的语句也要进行修改），然后对所创建的二叉树进行中序线索化；任务5：对任务4得到的中序线索化树进行中序遍历。源代码：head.h: #include<string.h>#include<ctype.h>#include<malloc.h> /malloc( )#include<l

25、imits.h> / INT ,MAX#include<stdio.h> /EOF,NULL#include<stdlib.h> /atoi( )#include<io.h> /eof( )#include<math.h> /floor( ),ceil( ),abs( )#include<process.h> /exit( )#include<iostream.h> /cout,cin/函数结果状态代码#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#d

26、efine INFEASIBLE -1/OVERFLOW 在 math.h 中已定义为3typedef int Status;typedef int Boolean; / 布尔类型head2.h:typedef char TElemType; typedef enumLink,ThreadPointerTag; /* Link(0):指针,Thread(1):线索 */typedef struct BiThrNode TElemType data; struct BiThrNode *lchild,*rchild; /* 左右孩子指针 */ PointerTag LTag,RTag; /* 左

27、右标志 */BiThrNode,*BiThrTree;main.cpp:#include"head.h"#include"head2.h"Status CreateBiThrTree(BiThrTree &T) /* 按先序输入二叉线索树中结点的值,构造二叉线索树T */ /* 空格表示空结点 */ TElemType h; scanf("%c",&h); if(h=' ') T=NULL; else T=(BiThrTree)malloc(sizeof(BiThrNode); if(!T) exit(

28、OVERFLOW); T->data=h; /* 生成根结点(先序) */ CreateBiThrTree(T->lchild); /* 递归构造左子树 */ if(T->lchild) /* 有左孩子 */ T->LTag=Link; CreateBiThrTree(T->rchild); /* 递归构造右子树 */ if(T->rchild) /* 有右孩子 */ T->RTag=Link; return OK;BiThrTree pre;void InThreading(BiThrTree p) /* 中序遍历进行中序线索化。算法6.7 */ i

29、f(p) InThreading(p->lchild); /* 递归左子树线索化 */ if(!p->lchild) /* 没有左孩子 */ p->LTag=Thread; /* 前驱线索 */ p->lchild=pre; /* 左孩子指针指向前驱 */ if(!pre->rchild) /* 前驱没有右孩子 */ pre->RTag=Thread; /* 后继线索 */ pre->rchild=p; /* 前驱右孩子指针指向后继(当前结点p) */ pre=p; /* 保持pre指向p的前驱 */ InThreading(p->rchild)

30、; /* 递归右子树线索化 */ Status InOrderThreading(BiThrTree &Thrt,BiThrTree T) /* 中序遍历二叉树T,并将其中序线索化,Thrt指向头结点。算法6.6 */ Thrt=(BiThrTree)malloc(sizeof(BiThrNode); if(!Thrt) exit(OVERFLOW); Thrt->LTag=Link; /* 建头结点 */ Thrt->RTag=Thread; Thrt->rchild=Thrt; /* 右指针回指 */ if(!T) /* 若二叉树空，则左指针回指 */ Thrt-

31、>lchild=Thrt; else Thrt->lchild=T; pre=Thrt; InThreading(T); /* 中序遍历进行中序线索化 */ pre->rchild=Thrt; pre->RTag=Thread; /* 最后一个结点线索化 */ Thrt->rchild=pre; return OK;Status InOrderTraverse_Thr(BiThrTree T,Status(*Visit)(TElemType) /* 中序遍历二叉线索树T(头结点)的非递归算法。算法6.5 */ BiThrTree p; p=T->lchild; /* p指