《二叉树的遍历及线索化》由会员分享，可在线阅读，更多相关《二叉树的遍历及线索化（9页珍藏版）》请在金锄头文库上搜索。
1、青 岛 理 工 大 学数据结构课程实验报告课程名称数据结构班级网络102实验日期2012/4/26#徐梦婷学号201007110实验成绩实验名称二叉树的遍历与线索化实验目的与要求掌握二叉树的建立,用递归方法先序、中序、后序遍历和非递归的中序遍历与层次遍历还有二叉树的线索化以与中序遍历的算法与代码实现.实验环境硬件平台：普通的PC机软件平台：Windows 2003操作系统编程环境：VisualC+实验内容1、 建立一棵二叉树,定义它的链式存储结构,包括数据域和指针域2、 掌握用递归方法的前中后序遍历3、 掌握非递归的中序遍历利用栈和层次遍历利用队列4、 掌握二叉树的线索化,定义二叉线索存储结构
2、并对她进行中序线索化以与遍历算法描述与实验步骤1、typedef int TElemType;/定义了二叉树的存储结构typedef struct BiTNodeTElemType data;/结点域struct BiTNode *lchild,*rchild;/左右孩子指针BiTNode,*BiTree;typedef BiTree SElemType;/用递归方法建立一棵二叉树void CreatBiTreeifT=NULL;/创建了一棵空树elseT=mallocsizeof;/申请树根结点空间T-data=ch;CreatBiTreelchild;/递归生成左子树CreatBiTree
3、rchild;/递归生成右子树2、/以递归先序遍历为例void PreOrderTraverseBiTree T,StatusifVisitdata;/首先访问根结点PreOrderTraverselchild,Visit;/然后递归遍历左子树PreOrderTraverserchild,Visit;/最后递归遍历右子树 /中序遍历时先递归遍历左子树,然后访问根结点,最后递归遍历右子树；后序遍历时先递归遍历左子树,然后递归遍历右子树,最后访问根结点3、/先把栈与队列相关操作的头文件包括进来 1根指针入栈, 2向左走到左尽头入栈操作 3出栈,访问结点 4向右走一步,入栈,循环到第二步,直到栈空/
4、层次遍历时,若树不空,则首先访问根结点,然后,依照其双亲结点访问的顺序,依次访问它们的左、右孩子结点;4.首先建立二叉线索存储：包含数据域,左右孩子指针以与左右标志typedef enum Link=0,Thread=1 PointerTag;typedef struct BiThrNodeTElemType data;struct BiThrNode *lchild,*rchild;/左右孩子指针PointerTag LTag,RTag;/左右标志BiThrNode, *BiThrTree; 建立前驱线索和后继线索,并用中序遍历进行中序线索化,然后最后一个结点线索化调试过程与实验结果把测试数
5、据放在f:filedata.txt里,测试数据为：1 2 4 0 0 0 3 5 0 0 0总结访问结点是指访问该结点的数据域,弄清楚各个指针所指的类型附录#includeusing namespace std;#include#include#include#include#includeSqStack.htypedef int Status;typedef int TElemType; / 函数结果状态代码 #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define INFEASIBLE -1typedef BiT
6、ree QElemType; / 单链队列队列的链式存储结构 typedef struct QNode QElemType data; QNode *next; *QueuePtr; struct LinkQueue QueuePtr front,rear; / 队头、队尾指针 ;void InitQueue / 构造一个空队列Q if!Q.front=Q.rear=mallocsizeof exit; Q.front-next=NULL; void EnQueue / 插入元素e为Q的新的队尾元素 QueuePtr p; if!p=mallocsizeof / 存储分配失败 exit; p-
7、data=e; p-next=NULL; Q.rear-next=p; Q.rear=p; Status DeQueue / 若队列不空,删除Q的队头元素,用e返回其值,并返回OK,否则返回ERROR QueuePtr p; if return ERROR; p=Q.front-next; e=p-data; Q.front-next=p-next; if Q.rear=Q.front; free; return OK; Status QueueEmpty / 若Q为空队列,则返回TRUE,否则返回FALSE ifnext=NULL return TRUE; else return FALSE
8、; /函数指针visit指向这个函数Status printprintf;return OK;/创建一棵树,字符代表结点,空格代表空树void CreatBiTreeint ch;scanf;ifT=NULL;/这是一棵空树elseT=mallocsizeof;/申请结点空间,放树根结点ifexit;T-data=ch;CreatBiTreelchild;/递归生成左子树CreatBiTreerchild;/递归生成右子树/递归先序遍历void PreOrderTraverseBiTree T,StatusifVisitdata;/首先访问根结点PreOrderTraverselchild,V
9、isit;/然后递归遍历左子树PreOrderTraverserchild,Visit;/最后递归遍历右子树/递归中序遍历void InOrderTraverseBiTree T,Statusif/T不是空树InOrderTraverselchild,Visit;/首先递归遍历左子树Visitdata;/访问根结点InOrderTraverserchild,Visit;/最后递归遍历右子树/递归后序遍历void PostOrderTraverseBiTree T,StatusifPostOrderTraverselchild,Visit;/递归遍历左子树PostOrderTraverserch
10、ild,Visit;/递归遍历右子树Visitdata;/访问根结点/非递归的中序遍历利用栈Status InOrderTraverse2BiTree T,Status SqStack S;InitStack;BiTree p;Push;/根指针入栈while!StackEmptywhileGetTop&pPushlchild;/向左走到尽头Pop;/空指针退栈if!StackEmpty/访问结点,向Pop;if!Visitdatareturn ERROR;Pushrchild;return OK;/层次遍历void BFSTraverseBiTree T,Status LinkQueue Q;QElemType p;InitQueue;/置空的辅助队列ifEnQueue;/根结点入队while!QueueEmptyDeQueue;/对头出队并置为pVisitdata ;iflchildEnQueuelchild;ifrchildEnQueuerchild;int mainfreopen;BiTree T;printf;CreatBiTree;printf;PreOrderTraverse;printf;InOrderTraverse;
