数据结构二叉树ppt课件.ppt

《数据结构二叉树ppt课件.ppt》由会员分享，可在线阅读，更多相关《数据结构二叉树ppt课件.ppt（42页珍藏版）》请在三一办公上搜索。

1、校长,一系,二系,三系,六系,教务处,科研处,总务处,601,602,教务科,603,A,B,C,D,例1,工厂,例3,1 树的基本概念,2 树的存储结构,3 二叉树,4 二叉树的存储结构,5 二叉树的遍历,6 线索二叉树,6.1 树的基本概念,1. 有且仅有一个结点没有前驱结点,该结点为树的根结点。,2. 除了根结点外,每个结点有且仅有一个直接前驱结点。,3. 包括根结点在内，每个结点可以有多个后继结点。,4. 树形表示法,1. 结点的度：2. 树的度：,3. 叶结点：4. 分支结点:,5. 层次的定义:,该结点拥有的子树的数目。,树中结点度的最大值。,度为0 的结点.,度非0 的结点.,根

2、结点为第一层,若某结点在第i 层, 则其孩子结点(若存在)为第i+1层.,7. 树林(森林): m0 棵不相交的树组成的树的集合.,8. 树的有序性:,6. 树的深度:,树中结点所处的最大层次数.,若树中结点的子树的相对位置不能 随意改变, 则称该树为有序树，否 则称该树为无序树。,二叉树的基本形态：,(空),6.2 二叉树,二. 两种特殊形态的二叉树,1. 一棵非空二叉树的第i 层最多有2i1个结点(i1)。,2. 深度为h 的非空二叉树最多有2h -1个结点.,3. 若非空二叉树有n0个叶结点,有n2个度为2的结点, 则 n0=n2+1,4. 具有n个结点的完全二叉树的深度h=log2n+

3、1.,二叉树的存储结构,一.二叉树的顺序存储结构,1. 完全二叉树的顺序存储结构,2. 一般二叉树的顺序存储结构,二.二叉树的链式存储结构(二叉链表),二.前序遍历,三.中序遍历,四.后序遍历,前序遍历序列: A, B, D, K, J, G, C, F, I, E, H,中序遍历序列: D, B, G, J, K, A, F, I, E, C, H,后序遍历序列: D, G, J, K, B, E, I, F, H, C, A,按层次遍历序列: A, B, C, D, K, F, H, J, I, G, E,6.3.2 线索二叉树,1.何谓线索二叉树？ 遍历结果是求得结点的一个线性序列。指向

4、该线性序列“前驱”和“后继”的指针，称“线索”；包含“线索”的存储结构，称为“线索链表”；与其相应的二叉树，称为“线索二叉树”；对二叉树以某种次序遍历，使其变为线索二叉树的过程，称为“线索化”。,2.线索链表中结点的结构,在二叉链表的结点结构中增加两个标志域，并规定：,其中：LTag =,0 lchild 域指示结点的左孩子1 lchild 域指示结点的前驱,RTag =,0 rchild 域指示结点的右孩子1 rchild 域指示结点的后继,二叉树二叉线索存储表示,typedef enum Link, Thread PointerThr; / Link=0:指针，Thread=1:线索typ

5、edef struct BiThrNode TElemType data; Struct BiThrNode *lchild, *rchild; / 左右孩子指针 PointerThr LTag, RTag; / 左右标志 BiThrNode, *BiThrTree;,3.线索二叉树图例,线索二叉树及其存储结构 （a）中序线索二叉树 （b）中序线索链表,如何在线索树中找结点的后继？,结合中序线索树 若其右标志为“1”，右链是线索，右链直接指示了结点的后继； 若其右标志为“0”，右链是指针，其后继为右子树中最左下的结点。,如何在线索树中找结点的前驱？,结合中序线索树 若其左标志为“1”，左链为线

6、索，直接指示其前驱； 若其左标志为“0”，左子树中最右下的结点为其前驱。,线索链表的中序遍历算法Status IOTraver_T( BiThrTree T,Status (*Visit)(TElemType e) ) /T指向头结点，头结点的左链lchild指向根结点，中序遍历 /二叉线索树T的非递归算法，对每个数据元素调用函数Visit。 p = T-lchild; /p指向根结点 while (p != T) /空树或遍历结束时，p = = T while (p-LTag=Link) p = p-lchild; if (!Visit(p-data) return ERROR; /访问其左

7、子树为空的结点 while (p-RTag=Thread / IOTraver_T,6.4.2 森林和二叉树的转换,1. 树和二叉树的对应关系 由于二叉树和树都可用二叉链表作为存储结构，则以二叉链表作为媒介可导出树与二叉树之间的一个对应关系。,树转换为二叉树方法：,1）对每个孩子进行从左到右的排序；2）在兄弟之间加一条连线；3）对每个结点，除了左孩子外，去除其与其余孩子之间的联系； 4）以根结点为轴心，将整个树顺时针转45。,2. 森林和二叉树的对应关系 从树的二叉链表表示的定义可知，任何一棵和树对应的二叉树，其右子树必空。 若把森林中第二棵树的根结点看成是第一棵树的根结点的兄弟，则同样可导出

8、森林和二叉树的对应关系。,已知条件：森林和二叉树的对应关系设 森 林 F = ( T1, T2, , Tn ); T1 = (root，t11, t12, , t1m); 二叉树 B =( LBT, Node(root), RBT );由森林转换成二叉树的转换规则为:若 F = ，则 B = ;否则，由 Root( T1 ) 对应得到 Node(root); 由 (t11, t12, , t1m ) 对应得到 LBT; 由 (T2, T3, Tn ) 对应得到 RBT。由二叉树转换为森林的转换规则为:若 B = , 则 F = ;否则，由 Node(root) 对应得到 Root( T1 );

9、 由LBT 对应得到 ( t11, t12, ，t1m);T1除根以外所 构成的森林 由RBT 对应得到 (T2, T3, , Tn)；除T1之外的森林,6.4.3 树和森林的遍历,1. 树的遍历：有三条搜索路径先根(序)遍历：若树不空，则先访问根结点， 然后依次先根遍历各棵子树。后根(序)遍历：若树不空，则先依次后根遍历 各棵子树，然后访问根结点。按层次遍历： 若树不空，则自上而下自左至 右访问树中每个结点。,例对树进行先根遍历，获得的先根序列是：对树进行后根遍历，获得的后根序列是：,A B E F C D G H I,E F B C G H I D A,2.森林的遍历,先序遍历(对森林中的

10、每一棵树进行先根遍历) 1）若森林不空，访问森林中第一棵树的根结点； 2）先序遍历森林中第一棵树的子树森林； 3）先序遍历森林中(除第一棵树外)其余树构成的森林。后序遍历(对森林中的每一棵树进行后根遍历) 1）若森林不空，后序遍历森林中第一棵树的子树森林； 2）访问森林中第一棵树的根结点； 3）后序遍历森林中(除第一棵树外)其余树构成的森林。,例：对森林进行先序遍历，获得的先序序列是：对森林进行后序遍历，获得的后序序列是：,B E F C D G H I,E F B C G H I D,总结：1. 二叉树的线索化2. 树的表示及其遍历操作；3. 建立森林与二叉树的对应关系。 由于在树和森林中，一个结点的孩子的个数不定，它们在计算机中的表示以及在各种操作计算机中的算法实现均不易实现，因此将树和森林表示为二叉树，并将对树和森林的操作转化为对二叉树的操作是通常采用的方法。,