实验05-二叉树 1 / 5
《数据结构与算法》实验报告
班级学号 BX120109 姓 名 刘嘉琦 实验周次 W10 实验日期 2013年11月13日 实验05：二叉树
一、实验目的
1．掌握二叉树及线索二叉树的特点，以及二叉链表的存储方式。 2．掌握二叉树的创建和显示，以及二叉树中序线索化的方法。
3．了解二叉树遍历的概念，掌握二叉树先序、中序和后序遍历的递归及非递归遍历方法。
4．掌握二叉树的层次遍历（使用队列），线索二叉树的非栈非递归遍历方法。 5．掌握求二叉树的叶结点数、总结点数和深度等基本算法。
二、实验内容
A题：采用二叉链表存储结构，用递归方式(当子树为空时输入#)建立如图5-1所示二叉树对应的二叉链表，请分别用递归和非递归两种方式实现该二叉树的前序、中序及后序序列的输出；并通过LevelOrder()函数输出其层次遍历序列。
程序中需要完成的功能为3、4、5、6（其中功能3、4为选做）；其它功能的实现代码已经全部给出。
程序运行的主界面如图5-2(a)所示。
图5-1 二叉树
B题：二叉树如图5-1所示，采用线索二叉链表作为存储结构，首先用递归方式(当子树为空时输入#)建立对应的二叉链表，再对该二叉链表进行中序线索化，最后对该线索二叉树进行非栈非递归中序遍历；并通过LevelOrder()函数输出其层次遍历序列。
实验05-二叉树 2 / 5
程序中需要完成的功能为3、5、6；其它功能的实现代码已经全部给出。 程序运行的主界面如图5-2(b)所示。
三、实验要求
学号为单号的同学做A题；学号为双号的同学做B题。 A题“非递归后序遍历”功能的提示：
①二叉树的非递归遍历功能需要利用栈来实现，可以定义两个栈（如果利用C++模板，则只需构造一个栈），一个是节点指针栈PS，另一个为输出数据栈DS。
②节点指针型栈用于保存左右子树的根节点地址。最后，当节点指针栈PS为空时，直接将输出数据栈DS中的所有数据依次弹出，即得到该二叉树的后序序列。
③本功能的实现和非递归求解Hanoi问题类似，这里的左右子树的根节点地址入栈时应该是左子树的根先进栈，然后是右子树的根进栈，如果没有左右子树，则直接将根节点的数据输出到输出数据栈DS。
“非递归后序遍历”二叉树的步骤： 第一步：先将根T入节点指针型栈PS； while(PS不为空) {
① 出栈一棵子树；
② 子树根的值入输出数据栈DS； ③ 子树的左孩子如果存在， 则进PS； ④ 子树的右孩子如果存在，则进PS； }
最后一步： 将输出数据栈DS中的所有元素出栈并输出； B题中序线索化功能的提示：
中序线索化可用递归方式来实现，关键要理解子树的直接前驱和子树的直接后继的概念。注意：不是结点的直接前驱和直接后继。
四、运行结果（主要功能界面截图）
实验05-二叉树 3 / 5
图5-1 非递归后序遍历
图5-2 层次遍历(使用队列)
五、参考程序（补全函数的源代码）
{
void NoRecursionPostOrder(BiTree T)
实验05-二叉树 4 / 5
// 补全此处代码 char e; PtrLinkedStack PS; DataLinkedStack DS; BiTree p; p=T; initDLS(DS); //初始化数据型栈DS initPLS(PS); //初始化指针型栈PS PushPLS(PS,p); while(!IsEmptyPLS(PS)) { PopPLS(PS,p); PushDLS(DS, p->data); //子树根的值入数据栈DS if(p->lchild!=NULL) //左子树有则进PS PushPLS(PS,p->lchild); if(p->rchild!=NULL) //右子树有则进PS PushPLS(PS,p->rchild); } while(!IsEmptyDLS(DS)) //输出DS中数据 { PopDLS(DS,e); printf(\ } }
// Function6--层次遍历(要使用队列，请先构造一个队列) void LevelOrder(BiTree T) { // 补全此处代码 SqQueue q; BiTree p; InitQueue(q); //初始化一个空队列 p=T; InQueue(q,p); //根结点入队 while(!QueueIsEmpty(q)) { OutQueue(q,p); printf(\ if(p->lchild!=NULL) //有左子树则左子树进队 InQueue(q,p->lchild); if(p->rchild!=NULL) //有右子树则右子树进队 InQueue(q,p->rchild); } }
实验05-二叉树 5 / 5