二叉树的遍历.ppt

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

1、二叉树的遍历重点：学习并掌握二叉树的三种遍历方案。难点：在对子树进行操作时，也要注意遍历的顺序与采用的遍历方法的统一。主讲人：唐海燕引出二叉树的遍历根节点左子树右子树在二叉树的一些应用中，常常要求在树中查找具有某种特征的结点，或者对树中全部结点逐一进行某种处理。这就引入了遍历二叉树的问题。“访问”的含义可以很广，如：输出结点的信息等。“遍历”是任何类型均有的操作，对线性结构而言，只有一条搜索路径(因为每个结点均只有一个后继)，故不需要另加讨论。而二叉树是非线性结构，每个结点都可能有两棵子树，因而需要寻找一种规律，从而使二叉树上的结点能排列在一个线性队列上，从而

2、便于遍历。二叉树的遍历定义：按某条搜索路径巡访树中每个结点，使得每个结点均被访问一次，而且仅被访问一次。二叉树是由3个基本单元组成：根结点、左子树、右子树。因此若能依次遍历这三个部分，便是遍历了整个二叉树。ABC遍历方案（先左后右）：ABC、BAC、BCA遍历方案（先右后左）：ACB、CAB、CBA假如以L、D、R分别表示遍历左子树、遍历根结点和遍历右子树，遍历整个二叉树则有DLR、LDR、LRD、DRL、RDL、RLD六种遍历方案。若规定先左后右，则只有前三种情况，根据访问根结点位置的不同，分别规定为：中根（序）遍历（LDR）先根（序）遍历（DLR）后

3、根（序）遍历（LRD）先（根）序(DLR)的遍历算法：若二叉树为空树，则空操作；否则注意：在（2）（3）步时我们要注意遍历的顺序，以便使整个二叉树的遍历具有统一性。（难点）中序，后序与先序的区别：访问子树的顺序是一样的，只是访问根结点的位置不同。（1）访问根结点；（2)先序遍历左子树；（3)先序遍历右子树；LDR（中序）LRD（后序）例题：abcde-×+/先序遍历：-×+abc/de先序遍历二叉树基本操作的递归算法在二叉链表上的实现。StatusPreOrderTraverse（BiTreeT，Status（*Visit）（TElemTypee){//采用二

4、叉链表存储结构，Visit是对数据元素操作的应用函数。//先序遍历二叉树T的递归算法，对每个数据元素调用函数Visit./*最简单的Visit函数是：StatusPrintElement(TElemTypee){printf(e);returnOK;}*///调用实例：PreOrderTraverse（T，PrintElement）；If（T){If(Visit(T->data))if(PreOrderTraverse（T->lchild，Visit）)if(PreOrderTraverse（T->rchild，Visit）)returnOK;returnEr

5、ror;}elsereturnOK;}//PreOrderTraverse