数据结构树的.pptx

《数据结构树的.pptx》由会员分享，可在线阅读，更多相关《数据结构树的.pptx（41页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

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该结点拥有的子树的数目。该结点拥有的子树的数目。树中结点度的最大值树中结点度的最大值。度为度为0 的结点的结点.度非度非0 的结点的结点.根结点为第一层根结点为第一层,若某结点在第若某

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

5、)根根根根左左子子树树根根右右子子树树根根左左子子树树右右子子树树 6.2 二叉树二叉树第9页/共41页二二.两种特殊形态的二叉树两种特殊形态的二叉树 若一棵二叉树中的结点若一棵二叉树中的结点,或者为叶结点，或者为叶结点，或者具有两或者具有两棵非空子树棵非空子树,并且叶结点都集并且叶结点都集中在二叉树的最下面一层中在二叉树的最下面一层.这这样的二叉树为满二叉树样的二叉树为满二叉树.1.满二叉树满二叉树 若一棵二叉树中只有最下若一棵二叉树中只有最下面两层的结点的度可以小于面两层的结点的度可以小于2,并且最下面一层的结点并且最下面一层的结点(叶结叶结点点)都依次排列在该层从左至都依次排列在该层从左

6、至右的位置上。这样的二叉树为右的位置上。这样的二叉树为完全二叉树完全二叉树.2.完全二叉树完全二叉树第10页/共41页1.一棵非空二叉树的第一棵非空二叉树的第i 层最多有层最多有2i1个结点个结点(i 1)。三三.二叉树的性质二叉树的性质2.深度为深度为h 的非空二叉树最多有的非空二叉树最多有2h-1-1个结点个结点.3.若非空二叉树有若非空二叉树有n0个叶结点个叶结点,有有n2个度为个度为2的结点的结点,则则 n0=n2+1 4.具有具有n个结点的完全二叉树的深度个结点的完全二叉树的深度h=log2n+1.第11页/共41页 二叉树的存储结构二叉树的存储结构一一.二叉树的顺序存储结构二叉树的

7、顺序存储结构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 的完全二叉树的完全二叉树,将树中所有结点的将树中所有结点的数据信息按照编号的顺序依次存储到一维数组数据信息按照编号的顺序依次存储到一维数组BT1:2h-1中中,由于编号与数组由于编号与数组的下标一一对应的下标一一对应,该数组就是该完全二叉树的顺序存储结构该数组就是该完全二叉树的顺序存储结构.1.完全二叉树的顺序存储结构完全二叉树的顺序存储结构第12页/共4

8、1页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页二二.二叉树的链式存储结构二叉树的链式存储结构(二叉链表二叉链表)链结点的构造为链结点的构造为lchilddatarchild 其中其中,data 为数据域为数据域 lchild 与与rchild 分别为指向左、右子树的指针域分别为指向左、右子树的指针域.ABCDEFGIJABCDEFGJIT第15页/共41页6.3.3 二叉树的遍历二叉树的遍历第16页/共41页二二.前序遍历前序遍历第17页/共41页三三.中序遍历中序遍历第18页/共41页四四.后序遍历

10、后序遍历第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后序遍历序列后序遍历序列: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.何谓线索二叉树？何谓线索二叉树？遍历结果是求得结点的一个线性序列。指遍历结果是求得结点的一个线性序列。指向该线性序列向该线性序列“前驱前驱”和和“后继后继”的指针，称的指针，称“线索线索”；包含；包含“

11、线索线索”的存储结构，称为的存储结构，称为“线索链表线索链表”；与其相应的二叉树，称为；与其相应的二叉树，称为“线索线索二叉树二叉树”；对二叉树以某种次序遍历，使其变；对二叉树以某种次序遍历，使其变为线索二叉树的过程，称为为线索二叉树的过程，称为“线索化线索化”。第21页/共41页2.2.线索链表中结点的结构线索链表中结点的结构在二叉链表的结点结构中增加两个在二叉链表的结点结构中增加两个在二叉链表的结点结构中增加两个在二叉链表的结点结构中增加两个标志域标志域，并规定：并规定：并规定：并规定：lchildLTagdataRTag rchild其中：其中：LTag=LTag=0 lchild 0

12、lchild 域指示结点的左孩子域指示结点的左孩子1 lchild 1 lchild 域指示结点的前驱域指示结点的前驱RTag=RTag=0 rchild 0 rchild 域指示结点的右孩子域指示结点的右孩子1 rchild 1 rchild 域指示结点的后继域指示结点的后继第22页/共41页二叉树二叉线索存储表示二叉树二叉线索存储表示typedef enum Link,Thread PointerThr;typedef enum Link,Thread PointerThr;/Link=0:/Link=0:指针，指针，Thread=1:Thread=1:线索线索typedef struct

13、 BiThrNodetypedef struct BiThrNode TElemType data;TElemType data;Struct BiThrNode*lchild,*rchild;Struct BiThrNode*lchild,*rchild;/左右孩子指针左右孩子指针 PointerThr LTag,RTag;PointerThr LTag,RTag;/左右标志左右标志 BiThrNode,*BiThrTree;BiThrNode,*BiThrTree;第23页/共41页3.3.线索二叉树图例线索二叉树图例 线索二叉树及其存储结构线索二叉树及其存储结构 （a a）中序线索二叉树

14、）中序线索二叉树 （b b）中序线索链表）中序线索链表12345670 1 00 2 01 3 11 4 10 5 01 6 11 7 1thrt0 1第24页/共41页如何在线索树中找结点的后继？如何在线索树中找结点的后继？结合中序线索树结合中序线索树 若其右标志为若其右标志为“1 1”，右链是线索，右链直接，右链是线索，右链直接指示了结点的后继；指示了结点的后继；若其右标志为若其右标志为“0 0”，右链是指针，其后继为，右链是指针，其后继为右子树中最左下的结点。右子树中最左下的结点。1234567第25页/共41页如何在线索树中找结点的前驱？如何在线索树中找结点的前驱？结合中序线索树结合中

15、序线索树 若其左标志为若其左标志为“1 1”，左链为线索，直接指示，左链为线索，直接指示其前驱；其前驱；若其左标志为若其左标志为“0 0”，左子树中最右下的结点，左子树中最右下的结点为其前驱。为其前驱。1234567第26页/共41页线索链表的中序遍历算法线索链表的中序遍历算法Status IOTraver_T(BiThrTree T,Status(*Visit)(TElemType e)Status IOTraver_T(BiThrTree T,Status(*Visit)(TElemType e)/T/T指向头结点，头结点的左链指向头结点，头结点的左链lchildlchild指向根结点，中

16、序遍历指向根结点，中序遍历 /二叉线索树二叉线索树T T的非递归算法，对每个数据元素调用函数的非递归算法，对每个数据元素调用函数VisitVisit。p=T-lchild;p=T-lchild;/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;/访问其左子树为空的结点访问其左子树为空的结

17、点 while(p-RTagwhile(p-RTag=Thread&p-rchild!=T)Thread&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.树和二叉树的对应关系树和二叉树的对应关系 由于

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

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

20、 cBCDEGHFId d第34页/共41页已知条件：森林和二叉树的对应关系设已知条件：森林和二叉树的对应关系设 森森 林林 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)对应得到对应得到 Node(root);Node(root);由由 (

21、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,t1212,，t t1m1m);T);T1 1除根以外所除根以外所 构成的森林构成的森林 由由RBT RBT 对应得到对应得到 (T(T2 2,T,T3 3,T,T

22、n n)；除；除T T1 1之外的森林之外的森林第35页/共41页6.4.3 6.4.3 树和森林的遍历树和森林的遍历1.1.树的遍历树的遍历：有三条搜索路径：有三条搜索路径先根先根(序序)遍历：遍历：若树不空，则先访问根结点，若树不空，则先访问根结点，然后依次先根遍历各棵子树。然后依次先根遍历各棵子树。后根后根(序序)遍历：遍历：若树不空，则先依次后根遍历若树不空，则先依次后根遍历 各棵子树，然后访问根结点。各棵子树，然后访问根结点。按层次遍历：按层次遍历：若树不空，则自上而下自左至若树不空，则自上而下自左至 右访问树中每个结点。右访问树中每个结点。第36页/共41页例例对树进行先根遍历，获

23、得的先根序列是：对树进行先根遍历，获得的先根序列是：对树进行后根遍历，获得的后根序列是：对树进行后根遍历，获得的后根序列是：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.森林的遍历森林的遍历先序遍历先序遍历(对森林中的每一棵树进行先根遍历对森林中的每一棵树进行先根遍历)1 1）若森林不空，访问森林中第一棵树的根结点若森林不空，访问森林中第一棵树的根结点；2 2）先序遍历森林中第一棵树的子树森林先序遍历森林中第一棵树的子树森林；3 3）先序遍历森林中先序遍历森林中

24、(除第一棵树外除第一棵树外)其余树构成的森林其余树构成的森林。后序遍历后序遍历(对森林中的每一棵树进行后根遍历对森林中的每一棵树进行后根遍历)1 1）若森林不空，后序遍历森林中第一棵树的子树森林若森林不空，后序遍历森林中第一棵树的子树森林；2 2）访问森林中第一棵树的根结点访问森林中第一棵树的根结点；3 3）后序遍历森林中后序遍历森林中(除第一棵树外除第一棵树外)其余树构成的森林其余树构成的森林。第38页/共41页例：例：对森林进行先序遍历，获得的先序序列是：对森林进行先序遍历，获得的先序序列是：对森林进行后序遍历，获得的后序序列是：对森林进行后序遍历，获得的后序序列是：BCDEGHFIB E

25、 F C D G H IB E F C D G H IE F B C G H I DE F B C G H I D第39页/共41页总结：总结：1.1.二叉树的线索化二叉树的线索化2.2.树的表示及其遍历操作；树的表示及其遍历操作；3.3.建立森林与二叉树的对应关系。建立森林与二叉树的对应关系。由于在树和森林中，一个结点的孩子的个由于在树和森林中，一个结点的孩子的个数不定，它们在计算机中的表示以及在各种操数不定，它们在计算机中的表示以及在各种操作计算机中的算法实现均不易实现，因此将树作计算机中的算法实现均不易实现，因此将树和森林表示为二叉树，并将对树和森林的操作和森林表示为二叉树，并将对树和森林的操作转化为对二叉树的操作是通常采用的方法。转化为对二叉树的操作是通常采用的方法。第40页/共41页感谢您的观看。第41页/共41页