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

实验报告五月 142015姓名：陈斌 学号：E11314079 专业：13计算机科学与技术数据结构 第三次实验学号 E11314079 专业 计算机科学与技术 姓名 陈 斌 实验日期 2015.05.14 教师签字 成绩 实 验 报 告【实验名称】 树和二叉树（一） 【实验目的】 1. 掌握二叉树的二叉链表存储表示；2. 掌握二叉树的遍历算法；3. 运用遍历算法求解有关问题。【实验内容】1. 必做内容任务1：以算法6.4创建二叉树的存储结构，树的具体形态自定。任务2：对任务1中的二叉树分别实现先序、中序、后序遍历（递归实现）和中序遍历的非递归实现以及层序遍历；任务3：统计1中树的结点总数、叶子结点总数以及树的高度；源代码：head.h: #include#include#include /malloc( )#include / INT ,MAX#include /EOF,NULL#include /atoi( )#include /eof( )#include /floor( ),ceil( ),abs( )#include /exit( )#include /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;SElemType *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); /* 存储分配失败 */ 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.topS.base) e=*(S.top-1); 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.stacksize+=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(OVERFLOW); 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(OVERFLOW); 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.front; free(p); return OK;main.cpp:typedef char TElemType;#includehead.htypedef struct BiTNodeTElemTypedata;struct BiTNode *lchild,*rchild;BiTNode,*BiTree;typedef BiTree QElemType; /* 设队列元素为二叉树的指针类型 */typedef BiTree SElemType; /* 设栈元素为二叉树的指针类型 */#includehead2.hStatus InitBiTree(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; /* 生成根结点 */ 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(PreOrderTraverse(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-lchild,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不空 */ 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的非递归算法(利用栈)，对每个数据元素调用函数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)(TElemType) /* 采用二叉链表存储结构，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,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(!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-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 (BiTreeDepth(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);coutendl;cout中序遍历序列:endl;InOrderTraverse(T,visitT);coutendl;cout后序遍历序列:endl;PostOrderTraverse(T,visitT);coutendl;cout中序遍历的非递归实现1(利用栈):endl;InOrderTraverse1(T,visitT);cout中序遍历的非递归实现2(利用栈):endl;InOrderTraverse2(T,visitT);cout层序遍历(利用队列):endl;LevelOrderTraverse(T,visitT);cout树的结点总数为:BiTreeNodeNum(T)endl;cout树的叶子结点总数为:BiTreeLeafNodeNum(T)endl;cout树的深度为:BiTreeDepth(T)endl;运行结果：A树的形状：BCDGEFH先序输入：ABG CDE H F ( “ ” 代表空格)2. 选做内容任务4：修改算法6.4（结点及二叉树类型分别用BiThrNode，BiThrTree，创建根结点的语句也要进行修改），然后对所创建的二叉树进行中序线索化；任务5：对任务4得到的中序线索化树进行中序遍历。源代码：head.h: #include#include#include /malloc( )#include / INT ,MAX#include /EOF,NULL#include /atoi( )#include /eof( )#include /floor( ),ceil( ),abs( )#include /exit( )#include /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:typedef char TElemType; typedef enumLink,ThreadPointerTag; /* Link(0):指针,Thread(1):线索 */typedef struct BiThrNode TElemType data; struct BiThrNode *lchild,*rchild; /* 左右孩子指针 */ PointerTag LTag,RTag; /* 左右标志 */BiThrNode,*BiThrTree;main.cpp:#includehead.h#includehead2.hStatus CreateBiThrTree(BiThrTree &T) /* 按先序输入二叉线索树中结点的值,构造二叉线索树T */ /* 空格表示空结点 */ TElemType h; scanf(%c,&h); if(h= ) T=NULL; else T=(BiThrTree)malloc(sizeof(BiThrNode); if(!T) exit(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 */ if(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); /* 递归右子树线索化 */ 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-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指向根结点 *