《二叉树的遍历.ppt》由会员分享，可在线阅读，更多相关《二叉树的遍历.ppt（19页珍藏版）》请在三一文库上搜索。
1、数据结构第六章 树和二叉树,第三节 遍历二叉树 制作人：高均均 20031014029,1.复习,上节课我们说了树,二叉树的定义,二叉树的五个重要的性质等.树型结构是一类重要的非线形结构.其中属树和二叉树的应用最为广泛. 1.树的定义 树(Tree)是N个结点的有限集(N0). 当N=0时是一个空树. 当N0时,树有两个重要的性质: (1)有且仅有一个特定的结点称为根的结点. (2)当N1,其余结点可以分为了若干个有限集(T1,T2,T3Tm),其中每个集合本身又是一棵树,并且称为根的子树.,树的基本术语,树的结点：包含一个数据元素及若干指向其子树的分支。 结点的度：结点拥有的子树数称为结点的
2、度。 叶 子：度为0的结点，又称终端结点。 分支结点：度不为0的结点，又称非终端结点。 树的度：树内各结点度的最大值。 结点孩子：结点的子树的根称为该结点的孩子。 孩子双亲：由结点孩子定义知，该结点称为孩子的双亲。 兄弟结点：同一个双亲的孩子间互称兄弟。 结点祖先：从根到该结点所经分支上的所有结点。 子 孙：以某结点为根的子树中任意结点称为子孙。,2.二叉树的定义,二叉树是一类特殊的树. (1)二叉树中的每个结点至多只有两棵子树,即二叉树中不存在度大于二的接点. (2)二叉树的由三个基本单元构成:根结点,左子树,右子树. (3)二叉树的左右子树有次序之分,顺序不能颠倒. 二叉树的基本形态:,二
3、叉树的遍历,1.问题的提出： 在二叉树的一些应用中，为了在树中查找具有某种特征的结点，或者对树中的全部结点逐一进行处理。这样就提出了一个遍历二叉树的问题，即如何按某条搜索路径寻访树中的每个结点，使得每个结点均被访问一次，而且仅被访问一次。“访问”的含义很广，可以是对结点进行处理，如输出结点的信息等等。 因此对二叉树而言：可以有三条搜索路径： （1）先上后下的按层次搜索 （2）先左子树，后右子树的遍历 （3）先左子树，后右子树的遍历,回顾二叉树的递归定义可知：二叉树有三个基本形态：根结点，左子树，右子树。因此，若能依次遍历这三部分，便是遍历了整个二叉树，假如以L，D，R分别表示遍历左子树，访问根
4、结点，遍历右子树则有DLR，DRL，LDR，RDL，LRD，RLD。 若限定先左后右，则只有三种情况：RLD，LDR，LRD。 也是我们的先序遍历二叉树，中序遍历二叉树，后序遍历二叉树,“中序”和“后序”中的”中”和”后”都是指访问根结点的先后次序，顾名思义，中序遍历就是中间遍历的是根结点，后序遍历就是最后遍历根结点但左子树总是默认在右子树之前遍历,2.二叉树的遍历,1先序遍历二叉树 操作定义: 若二叉树为空，则遍历结束，否则按顺序遍历 （1）访问根结点， （2）遍历左子树， （3）遍历右子树。,1,2,3,4,5,7,6,先序遍历二叉树： 1.从根结点开始遍历 2.访问1的左孩子 3.访问2
5、的左孩子 4.访问1的右孩子 5.访问4的左孩子 6.访问4的右孩子 7.访问6的右孩子,分析: 1.二叉树的先序遍历永远最先访问根结点. 2.二叉树的先序遍历永远从根结点开始 3.对于每一个需要遍历的结点,遍历的顺序是: (1)遍历该结点; (2)遍历该结点的左孩子(若存在的话) (3)遍历该结点的右孩子(若存在的话),中序遍历二叉树 操作定义: 若二叉树为空，则遍历结束，否则按顺序 遍历左子树， 遍历右子树， 访问 根结点。,分析: 1.二叉树的中序遍历永远从根结点开始分析. 2.二叉树的中序遍历永远从树的最左边开始. 3.对于每一个需要遍历的结点,遍历的顺序是: (1)遍历该结点的左孩子
6、(若存在的话); (2)遍历该结点; (3)遍历该结点的右孩子(若存在的话).,3,2,1,5,4,7,6,中序遍历二叉树： 1.最左边开始遍历 2.访问1的父结点 3.访问2的父结点 4.访问3的右孩子的左孩子 5.访问4的父结点 6.访问5的右孩子 7.访问6的右孩子,后序遍历二叉树 操作定义: 若二叉树为空，则遍历结束，否则按顺序 遍历左子树， 访问 根结点， 遍历右子树。,分析: 1.二叉树的后序遍历永远最后访问根结点. 2.二叉树的后序遍历永远从树的最左边开始. 3.对于每一个需要遍历的结点,遍历的顺序是: (1)遍历该结点的左孩子(若存在的话); (2)遍历该结点的右孩子(若存在的
7、话); (3)遍历该结点.,7,2,1,6,3,4,5,后序遍历二叉树： 1.最左边开始遍历 2.访问1的父结点 3.访问2的父结点的左孩子的左孩子 4.访问3的父结点的右孩子的右孩子 5.访问3的父结点的右孩子 6.访问3的父结点 7.最后访问根结点,例题:,-,+,/,a,*,e,f,b,c,-,d,所示的二叉树表示下列表达式 a+b*(c-d)-e/f 若先序遍历此二叉树得 -+a*b-cd/ef 若中遍历此二叉树得a+b*c-d-e/f 若后序遍历此二叉树得abcd-*+ef/-,例题-A- -/- - -B-C- -/- /- -D- E- F- -/- -G- - -H-先看中序遍
8、历，根节点是A，它的左子树的根节点是B，左子树的左子树是D，右子树是E。根据中序遍历的算法，先“左”后“中”最后“右”，所以A的左子树中序遍历的结果是DBE，既然整个树的左子树访问完了，当然就要访问整个树的根节点了，就是A；现在已经是DBEA了。现在开始看右子树，右子树C的左子树是F，C的右子树为空；再接着往左下找，F的左子树是G，F没有右子树；在往左下找，G没有左子树，那么G的左子树就不用访问了，直接写根节点G就可以了，再写G的右子树H，再逆着找回去，到F了，F的左子树已经访问完，所以接着写访问根节点F，没有右子树，再往上，就是C了。即：DBEAGHFC 再看后序遍历，依照后序遍历的法则，后序遍历左子树D ，后序遍历右子树E ，接着访问根结点B ，然后对于整个树来说先遍历右子树”CFGH”，对右子树来说又应该先从最低层遍历起，最低层无左分支，遍历右分支H，然后上溯到G，又无右分支，再上溯到F，然后是C，最后才遍历总的根结点A 即DEBHGFCA,作业,假定后序遍历二叉树的结果是A,C,B (1)画出所有可能用得这一结果的不同形态的二叉树(2)分别写出这些二叉树的中序遍历序列?,