数据结构树的PPT课件

1、(根目录) f1f2f3fnd1d2dm例例2f11f12f1kd11d12 第1页/共41页例例3第2页/共41页1 树的基本概念树的基本概念2 树的存储结构树的存储结构3 二叉树二叉树4 二叉树的存储结构二叉树的存储结构5 二叉树的遍历二叉树的遍历6 线索二叉树线索二叉树第3页/共41页 6.1 树的基本概念树的基本概念 树树是由是由n 0 个结点组成的有穷集合个结点组成的有穷集合( (不妨用不妨用D表示表示) )以及结点之间关系组成的集合构成的结构。以及结点之间关系组成的集合构成的结构。 当当n=0 时，称该树为空树；时，称该树为空树； 在任何一棵非空的树中，有一个特殊的结点在任何一棵非

2、空的树中，有一个特殊的结点t D，称之为该树的根结点；其余结点称之为该树的根结点；其余结点Dt被分割成被分割成m0个个不相交的子集不相交的子集D1, D2, ,Dm, ,其中每一个子集其中每一个子集Di又为一又为一棵树，分别称之为棵树，分别称之为t 的的子树子树。递归定义一一. . 树的定义树的定义第4页/共41页JIHGFEACXBA的第1棵子树A的第3棵子树A的第2棵子树二二. . 树树( (逻辑上逻辑上) )的特点的特点1. . 有且仅有一个结点没有前驱结点有且仅有一个结点没有前驱结点, ,该结点为树的根结点。该结点为树的根结点。2. . 除了根结点外除了根结点外, ,每个结点有且仅有一

3、个直接前驱结点。每个结点有且仅有一个直接前驱结点。3. . 包括根结点在内，每个结点可以有多个后继结点。包括根结点在内，每个结点可以有多个后继结点。第5页/共41页JIHGFEACXB4. 树形表示法树形表示法 借助自然界中一棵倒置的树的形状来表示数据元素之间层借助自然界中一棵倒置的树的形状来表示数据元素之间层次关系的方法。次关系的方法。第6页/共41页1. 结点的度：结点的度：2. 树的度：树的度：3. 叶结点：叶结点：4. 分支结点分支结点: :5. 层次的定义层次的定义: :JIHGFEACXB该结点拥有的子树的数目。该结点拥有的子树的数目。树中结点度的最大值树中结点度的最大值。度为度为

4、0 的结点的结点. .度非度非0 的结点的结点. . 根结点为第一层根结点为第一层, ,若某结点在第若某结点在第i 层层, , 则其孩子结点则其孩子结点( (若存在若存在) )为第为第i+1层层. .四四. . 基本名词术语基本名词术语第第1层层第第2层层第第3层层第7页/共41页7. 树林树林( (森林森林): ): m 0 棵不相交的树组成的树的集合棵不相交的树组成的树的集合. .8. 树的有序性树的有序性: :6. 树的深度树的深度: :树中结点所处的最大层次数树中结点所处的最大层次数. 若树中结点的子树的相对位置不能若树中结点的子树的相对位置不能 随意改变随意改变, , 则称该树为则称

5、该树为有序树有序树，否，否 则称该树为则称该树为无序树无序树。JIHGFEACXB深度为深度为3的树的树第8页/共41页二叉树的基本形态：二叉树的基本形态：(空空)根根根根左左子子树树根根右右子子树树根根左左子子树树右右子子树树 6.2 二叉树二叉树第9页/共41页二二. . 两种特殊形态的二叉树两种特殊形态的二叉树 若一棵二叉树中的结点若一棵二叉树中的结点, ,或者为叶结点，或者为叶结点， 或者具有两或者具有两棵非空子树棵非空子树, ,并且叶结点都集并且叶结点都集中在二叉树的最下面一层中在二叉树的最下面一层. .这这样的二叉树为满二叉树样的二叉树为满二叉树. .1. . 满二叉树满二叉树 若

6、一棵二叉树中只有最下若一棵二叉树中只有最下面两层的结点的度可以小于面两层的结点的度可以小于2, ,并且最下面一层的结点并且最下面一层的结点( (叶结叶结点点) )都依次排列在该层从左至都依次排列在该层从左至右的位置上。这样的二叉树为右的位置上。这样的二叉树为完全二叉树完全二叉树. .2. .完全二叉树完全二叉树第10页/共41页1. . 一棵非空二叉树的第一棵非空二叉树的第i 层最多有层最多有2i1个结点个结点( (i 1) )。三三. . 二叉树的性质二叉树的性质2. . 深度为深度为h 的非空二叉树最多有的非空二叉树最多有2h -1-1个结点个结点. .3. . 若非空二叉树有若非空二叉树

7、有n0个叶结点个叶结点, ,有有n2个度为个度为2的结点的结点, , 则则 n0=n2+1 4. . 具有具有n个结点的完全二叉树的深度个结点的完全二叉树的深度h= log2n +1. .第11页/共41页 二叉树的存储结构二叉树的存储结构一一. .二叉树的顺序存储结构二叉树的顺序存储结构12345678910ABCDEFGHIJBT1:151 2 3 4 5 6 7 8 9 10 11 12 13 14 15A B C D E F G H I J 根据完全二叉树的性质根据完全二叉树的性质 , ,对于深度为对于深度为h 的完全二叉树的完全二叉树, , 将树中所有结点的将树中所有结点的数据信息按

8、照编号的顺序依次存储到一维数组数据信息按照编号的顺序依次存储到一维数组BT1:2h-1中中, ,由于编号与数组由于编号与数组的下标一一对应的下标一一对应, 该数组就是该完全二叉树的顺序存储结构该数组就是该完全二叉树的顺序存储结构. . 1. 完全二叉树的顺序存储结构完全二叉树的顺序存储结构第12页/共41页12345678910ABCDEFGHIJ111213BT1:151 2 3 4 5 6 7 8 9 10 11 12 13 14 15A B C D E F G H J IABCDEFGHIJ 2. . 一般二叉树的顺序存储结构一般二叉树的顺序存储结构第13页/共41页 对于一般二叉树对于

9、一般二叉树, 只须在二叉树中只须在二叉树中“添加添加”一些实际上一些实际上二叉树中并不存在的二叉树中并不存在的“虚结点虚结点” ( 可以认为这些结点的数据可以认为这些结点的数据信息为空信息为空), 使其在形式上成为一棵使其在形式上成为一棵“完全二叉树完全二叉树”, 然后然后按照完全二叉树的顺序存储结构的构造方法将所有结点的数据信息依次存放按照完全二叉树的顺序存储结构的构造方法将所有结点的数据信息依次存放于数组于数组BT1: 2h -1中。中。第14页/共41页二二. .二叉树的链式存储结构二叉树的链式存储结构( (二叉链表二叉链表) )链结点的构造为链结点的构造为lchilddatarchil

10、d 其中其中, data 为数据域为数据域 lchild 与与rchild 分别为指向左、右子树的指针域分别为指向左、右子树的指针域.ABCDEFGIJABCDEFGJIT第15页/共41页6.3.3 二叉树的遍历二叉树的遍历第16页/共41页二二. .前序遍历前序遍历第17页/共41页三三. .中序遍历中序遍历第18页/共41页四四. .后序遍历后序遍历第19页/共41页ABCDKFGIJEH前序遍历序列前序遍历序列: : A, B, D, K, J, G, C, F, I, E, H中序遍历序列中序遍历序列: : D, B, G, J, K, A, F, I, E, C, H后序遍历序列后

11、序遍历序列: : D, G, J, K, B, E, I, F, H, C, A按层次遍历序列按层次遍历序列: : A, B, C, D, K, F, H, J, I, G, E例例第20页/共41页6.3.2 6.3.2 线索二叉树线索二叉树1.1.何谓线索二叉树？何谓线索二叉树？ 遍历结果是求得结点的一个线性序列。指遍历结果是求得结点的一个线性序列。指向该线性序列向该线性序列“前驱前驱”和和“后继后继”的指针，称的指针，称“线索线索”；包含；包含“线索线索”的存储结构，称为的存储结构，称为“线索链表线索链表”；与其相应的二叉树，称为；与其相应的二叉树，称为“线线索二叉树索二叉树”；对二叉树

12、以某种次序遍历，使其；对二叉树以某种次序遍历，使其变为线索二叉树的过程，称为变为线索二叉树的过程，称为“线索化线索化”。第21页/共41页2.2.线索链表中结点的结构线索链表中结点的结构标志域标志域lchildLTagdataRTag rchild其中：其中：LTag =LTag =0 lchild 0 lchild 域指示结点的左孩子域指示结点的左孩子1 lchild 1 lchild 域指示结点的前驱域指示结点的前驱RTag =RTag =0 rchild 0 rchild 域指示结点的右孩子域指示结点的右孩子1 rchild 1 rchild 域指示结点的后继域指示结点的后继第22页/共

13、41页二叉树二叉线索存储表示二叉树二叉线索存储表示typedef enum Link, Thread PointerThr; typedef enum Link, Thread PointerThr; / Link=0:/ Link=0:指针，指针，Thread=1:Thread=1:线索线索typedef struct BiThrNodetypedef struct BiThrNode TElemType data; TElemType data; Struct BiThrNode Struct BiThrNode * *lchild, lchild, * *rchild;rchild; /

14、 / 左右孩子指针左右孩子指针 PointerThr LTag, RTag; PointerThr LTag, RTag; / / 左右标志左右标志 BiThrNode, BiThrNode, * *BiThrTree;BiThrTree;第23页/共41页3.3.线索二叉树图例线索二叉树图例 线索二叉树及其存储结构线索二叉树及其存储结构 （a a）中序线索二叉树）中序线索二叉树 （b b）中序线索链表）中序线索链表12345670 1 00 2 01 3 11 4 10 5 01 6 11 7 1thrt0 1第24页/共41页如何在线索树中找结点的后继？如何在线索树中找结点的后继？结合中序

15、线索树结合中序线索树 若其右标志为若其右标志为“1 1”，右链是线索，右链直接指，右链是线索，右链直接指示了结点的后继；示了结点的后继； 若其右标志为若其右标志为“0 0”，右链是指针，其后继为右，右链是指针，其后继为右子树中最左下的结点。子树中最左下的结点。1234567第25页/共41页如何在线索树中找结点的前驱？如何在线索树中找结点的前驱？结合中序线索树结合中序线索树 若其左标志为若其左标志为“1 1”，左链为线索，直接指示，左链为线索，直接指示其前驱；其前驱； 若其左标志为若其左标志为“0 0”，左子树中最右下的结点，左子树中最右下的结点为其前驱。为其前驱。1234567第26页/共4

16、1页线索链表的中序遍历算法线索链表的中序遍历算法Status IOTraver_T( BiThrTree T,Status (Status IOTraver_T( BiThrTree T,Status (* *Visit)(TElemType e) )Visit)(TElemType e) ) /T/T指向头结点，头结点的左链指向头结点，头结点的左链lchildlchild指向根结点，中序遍历指向根结点，中序遍历 /二叉线索树二叉线索树T T的非递归算法，对每个数据元素调用函数的非递归算法，对每个数据元素调用函数VisitVisit。 p = T-lchild; p = T-lchild; /

17、p/p指向根结点指向根结点 while (p != T) while (p != T) /空树或遍历结束时，空树或遍历结束时，p = = Tp = = T while (p-LTag while (p-LTag=Link) p = p-lchild; Link) p = p-lchild; if (!Visit(p-data) return ERROR; if (!Visit(p-data) return ERROR; /访问其左子树为空的结点访问其左子树为空的结点 while (p-RTagwhile (p-RTag=Thread & p-rchild!=T) Thread &

18、; p-rchild!=T) p = p-rchild; Visit(p-data); p = p-rchild; Visit(p-data); /访问后继结点访问后继结点 p = p-rchild; p = p-rchild; return OK; return OK; / IOTraver_T/ IOTraver_T0 1 00 2 01 3 11 4 10 5 01 6 11 7 1T0 1 1第27页/共41页6.4.2 6.4.2 森林和二叉树的转换森林和二叉树的转换1. 1. 树和二叉树的对应关系树和二叉树的对应关系 由于二叉树和树都可用二叉链表作为存由于二叉树和树都可用二叉链表作

19、为存储结构，则以二叉链表作为媒介可导出树与二储结构，则以二叉链表作为媒介可导出树与二叉树之间的一个对应关系。叉树之间的一个对应关系。第28页/共41页第29页/共41页树转换为二叉树方法：树转换为二叉树方法：1 1）对每个孩子进行从左到右的排序；）对每个孩子进行从左到右的排序；2 2）在兄弟之间加一条连线；）在兄弟之间加一条连线；3 3）对每个结点，除了左孩子外，去除其与其余）对每个结点，除了左孩子外，去除其与其余孩子之间的联系；孩子之间的联系； 4 4）以根结点为轴心，将整个树顺时针转）以根结点为轴心，将整个树顺时针转4545。第30页/共41页ABCDEGHFIa aABCDEGHFIb

20、bABCDEGHFIc cABCDEGHFId d第31页/共41页2. 2. 森林和二叉树的对应关系森林和二叉树的对应关系 从树的二叉链表表示的定义可知，任何一棵从树的二叉链表表示的定义可知，任何一棵和树对应的二叉树，其和树对应的二叉树，其右子树必空右子树必空。 若把森林中第二棵树的根结点看成是第一棵若把森林中第二棵树的根结点看成是第一棵树的根结点的兄弟，则同样可导出森林和二叉树树的根结点的兄弟，则同样可导出森林和二叉树的对应关系。的对应关系。第32页/共41页第33页/共41页BCDEGHFIa aBCDEGHFIb bBCDEGHFIc cBCDEGHFId d第34页/共41页已知条件

21、：森林和二叉树的对应关系设已知条件：森林和二叉树的对应关系设 森森 林林 F = ( TF = ( T1 1, T, T2 2, , , T, Tn n ); ); T T1 1 = (root = (root，t t1111, t, t1212, , , t, t1m1m); ); 二叉树二叉树 B =( LBT, Node(root), RBT );B =( LBT, Node(root), RBT );由森林转换成二叉树的转换规则为由森林转换成二叉树的转换规则为: :若若 F = F = ，则，则 B = ;B = ;否则，由否则，由 Root( TRoot( T1 1 ) ) 对应得到

22、对应得到 Node(root);Node(root); 由由 (t(t1111, t, t1212, , , t, t1m1m ) ) 对应得到对应得到 LBT;LBT; 由由 (T(T2 2, T, T3 3, , T, Tn n ) ) 对应得到对应得到 RBTRBT。由二叉树转换为森林的转换规则为由二叉树转换为森林的转换规则为: :若若 B = , B = , 则则 F = ;F = ;否则，由否则，由 Node(root) Node(root) 对应得到对应得到 Root( TRoot( T1 1 ); ); 由由LBT LBT 对应得到对应得到 ( t( t1111, t, t121

23、2, , ，t t1m1m);T);T1 1除根以外所除根以外所 构成的森林构成的森林 由由RBT RBT 对应得到对应得到 (T(T2 2, T, T3 3, , , T, Tn n) )；除；除T T1 1之外的森林之外的森林第35页/共41页6.4.3 6.4.3 树和森林的遍树和森林的遍历历1. 1. 树的遍历树的遍历：有三条搜索路径：有三条搜索路径先根先根( (序序) )遍历：遍历：若树不空，则先访问根结点，若树不空，则先访问根结点， 然后依次先根遍历各棵子树。然后依次先根遍历各棵子树。后根后根( (序序) )遍历：遍历：若树不空，则先依次后根遍历若树不空，则先依次后根遍历 各棵子树

24、，然后访问根结点。各棵子树，然后访问根结点。按层次遍历：按层次遍历： 若树不空，则自上而下自左至若树不空，则自上而下自左至 右访问树中每个结点。右访问树中每个结点。第36页/共41页例例对树进行先根遍历，获得的先根序列是：对树进行先根遍历，获得的先根序列是：对树进行后根遍历，获得的后根序列是：对树进行后根遍历，获得的后根序列是：ABCDEGHFIA B E F C D G H IA B E F C D G H IE F B C G H I D AE F B C G H I D A第37页/共41页2.2.森林的遍历森林的遍历先序遍历先序遍历( (对森林中的每一棵树进行先根遍历对森林中的每一棵树