遍历和线索二叉树.ppt

《遍历和线索二叉树.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、6.1树的定义和基本术语6.2二叉树6.3遍历二叉树和线索二叉树6.4树和森林6.6哈夫曼树及其应用第六章树和二叉树6.3遍历二叉树和线索二叉树顺着某一条搜索路径巡访二叉树中的结点，使得每个结点均被访问一次，而且仅被访问一次。“访问”的含义可以很广，如：输出结点的信息等。“遍历”是任何类型均有的操作，对线性结构而言，只有一条搜索路径(因为每个结点均只有一个后继)，故不需要另加讨论。而二叉树是非线性结构，每个结点有两个后继，则存在如何遍历即按什么样的搜索路径进行遍历的问题。对“二叉树”而言，可以有三条搜索路径：1．先上后下的按层次遍历；2．先左（子树）后右（子树）的遍历；3

2、．先右（子树）后左（子树）的遍历。先左后右的遍历算法先（根）序的遍历算法中（根）序的遍历算法后（根）序的遍历算法根左子树右子树根根根根根若二叉树为空树，则空操作；否则，（1）访问根结点；（2）先序遍历左子树；（3）先序遍历右子树。先（根）序的遍历算法：若二叉树为空树，则空操作；否则，（1）中序遍历左子树；（2）访问根结点；（3）中序遍历右子树。中（根）序的遍历算法：若二叉树为空树，则空操作；否则，（1）后序遍历左子树；（2）后序遍历右子树；（3）访问根结点。后（根）序的遍历算法：ABCDEFGHK例如：先序序列：中序序列：后序序列：ABCDEFGHKBDCAEHGKFDC

3、BHKGFEA算法的递归描述StatusPreOrderTraverse(BiTreeT,Status(*Visit)(TElemTypee)){//采用二叉链表存储结构，visit是对数据元素操作的应用函数。//先序遍历二叉树T的递归算法，对每个数据元素调用函数Visit。//最简单的Visit函数是：//StatusPrintElement(TElemTypee){//输出元素e的值//printf(e);//实用时，加上格式串//returnOK;//}//调用实例：PreOrderTraverse(T,PrintElement);if(T){if(Visit(T－

4、>data))if(PreOrderTraverse(T－>lchild,Visit))if(PreOrderTraverse(T－>rchild,Visit))returnOK;returnERROR;}elsereturnOK;}//PreOrderTraverse若定义二叉树的存储结构为二叉链表，则有先序遍历二叉树的递归算法6.1如下：对应先表达式a+b*(c-d)-efabcde-×+/f-类似地，中序遍历此二叉树，可得到此二叉树的中序序列为a+b*c-d-e/f(表达式的中缀表示)若先序遍历二叉树，按访问结点的先后次序将结点排列起来，可得到二叉树的先序序列为-+

5、a*b-cd/ef(表达式的前缀表示—波兰式)类似地，后中序遍历此二叉树，可得到此二叉树的后序序列为abcd-*+ef/-(表达式的后缀表示—逆波兰式)（2）非递归算法以中序遍历为例说明二叉树遍历的非递归算法。仿照递归算法执行过程中递归工作栈的状态变化状况可直接写成相应的非递归算法：①工作记录中包含两项，其一是递归调用的语句编号，其二是指向根结点的指针，则当栈顶记录中的指针非空时，应遍历左子树，即指向左子树树根的指针进栈；②若栈顶记录中的指针值为空，则应退至上一层，若是从左子树返回,则应访问当前层即栈顶记录中指针所指的根结点；③若是从右子树返回，则表明当前层的遍历结束，应

6、继续退栈。由上述分析可得两个中序遍历二叉树的非递归算法如下所示：算法6.2如下：StatusInOrderTraverse(BiTreeT,Status(*Visit)(TElemTypee)){//采用二叉链表存储结构，visit是对数据元素操作的应用函数。//中序遍历二叉树T的非递归算法，对每个数据元素调用函数Visit。InitStack(S);Push(S,T);//根指针进栈while(!StackEmpty(S)){while(GetTop(S,p)&&p)Push(S,p－>lchild);//向左走到尽头Pop(S,p);if(!StackEmpty(S)

7、){//访问结点，向右一步Pop(S,p);if(!Visit(p－>data))returnERROR;Push(S,p－>rchild);}//if}//whilereturnOK;}//InOrderTraverse算法6.3如下：StatusInOrderTraverse(BiTreeT,Status(*Visit)(TElemTypee)){//采用二叉链表存储结构，visit是对数据元素操作的应用函数。//中序遍历二叉树T的非递归算法，对每个数据元素调用函数Visit。InitStack(S);P=T;while(