数据结构二叉树ppt

1、第第6 6章章 树与二叉树树与二叉树 校长校长 一一 系系 二二 系系 三三 系系 六六 系系 教教 务务 处处 科科 研研 处处 总总 务务 处处 601 602教教 务务 科科 603 A B CD 张张 三三 李李 四四 王王 五五 例例1 工工 厂厂 (根目录) f1f2f3fnd1d2dm 例例2 f11f12f1kd11d12 例例3 1 树的基本概念树的基本概念 2 树的存储结构树的存储结构 3 二叉树二叉树 4 二叉树的存储结构二叉树的存储结构 5 二叉树的遍历二叉树的遍历 6 线索二叉树线索二叉树 6.1 树的基本概念树的基本概念 树树是由是由n 0 个结点组成的有穷集合个结

2、点组成的有穷集合( (不妨用不妨用D表示表示) ) 以及结点之间关系组成的集合构成的结构。以及结点之间关系组成的集合构成的结构。 当当n=0 时，称该树为空树；时，称该树为空树； 在任何一棵非空的树中，有一个特殊的结点在任何一棵非空的树中，有一个特殊的结点t D， 称之为该树的根结点；其余结点称之为该树的根结点；其余结点Dt被分割成被分割成m0个个 不相交的子集不相交的子集D1, D2, ,Dm, ,其中每一个子集其中每一个子集Di又为一棵又为一棵 树，分别称之为树，分别称之为t 的的子树子树。 递归定义递归定义 一一. . 树的定义树的定义 2021/3/117 JIHGFE A CX B

3、A的第1棵子树A的第3棵子树 A的第2棵子树 二二. . 树树( (逻辑上逻辑上) )的特点的特点 1. . 有且仅有一个结点没有前驱结点有且仅有一个结点没有前驱结点, ,该结点为树的根结点。该结点为树的根结点。 2. . 除了根结点外除了根结点外, ,每个结点有且仅有一个直接前驱结点。每个结点有且仅有一个直接前驱结点。 3. . 包括根结点在内，每个结点可以有多个后继结点。包括根结点在内，每个结点可以有多个后继结点。 JIHGFE A CX B 4. 树形表示法树形表示法 借助自然界中一棵倒置的树的形状来表示数借助自然界中一棵倒置的树的形状来表示数 据元素之间层次关系的方法。据元素之间层次关

4、系的方法。 1. 结点的度：结点的度： 2. 树的度：树的度： 3. 叶结点：叶结点： 4. 分支结点分支结点: : 5. 层次的定义层次的定义: : JIHGFE A CX B 该结点拥有的子树的数目。该结点拥有的子树的数目。 树中结点度的最大值树中结点度的最大值。 度为度为0 的结点的结点. . 度非度非0 的结点的结点. . 根结点为第一层根结点为第一层, ,若某结点在第若某结点在第i 层层, , 则其孩子结点则其孩子结点( (若存在若存在) )为第为第i+1层层. . 四四. . 基本名词术语基本名词术语 第第1层层 第第2层层 第第3层层 7. 树林树林( (森林森林): ): m

5、0 棵不相交的树组成的树的集合棵不相交的树组成的树的集合. . 8. 树的有序性树的有序性: : 6. 树的深度树的深度: :树中结点所处的最大层次数树中结点所处的最大层次数. 若树中结点的子树的相对位置不能若树中结点的子树的相对位置不能 随意改变随意改变, , 则称该树为则称该树为有序树有序树，否，否 则称该树为则称该树为无序树无序树。 JIHGFE A CX B 深度为深度为3的树的树 二叉树的基本形态：二叉树的基本形态： (空空)根根根根 左左 子子 树树 根根 右右 子子 树树 根根 左左 子子 树树 右右 子子 树树 6.2 二叉树二叉树 二二. . 两种特殊形态的二叉树两种特殊形态

6、的二叉树 若一棵二叉树中的结点若一棵二叉树中的结点, , 或者为叶结点，或者为叶结点， 或者具有两或者具有两 棵非空子树棵非空子树, ,并且叶结点都集并且叶结点都集 中在二叉树的最下面一层中在二叉树的最下面一层. .这这 样的二叉树为满二叉树样的二叉树为满二叉树. . 1. . 满二叉树满二叉树 若一棵二叉树中只有最下若一棵二叉树中只有最下 面两层的结点的度可以小于面两层的结点的度可以小于2, , 并且最下面一层的结点并且最下面一层的结点( (叶结叶结 点点) )都依次排列在该层从左至都依次排列在该层从左至 右的位置上。这样的二叉树为右的位置上。这样的二叉树为 完全二叉树完全二叉树. . 2.

7、 .完全二叉树完全二叉树 1. . 一棵非空二叉树的第一棵非空二叉树的第i 层最多有层最多有2i1个结点个结点( (i 1) )。 三三. . 二叉树的性质二叉树的性质 2. . 深度为深度为h 的非空二叉树最多有的非空二叉树最多有2h -1-1个结点个结点. . 3. . 若非空二叉树有若非空二叉树有n0个叶结点个叶结点, ,有有n2个度为个度为2的结点的结点, , 则则 n0=n2+1 4. . 具有具有n个结点的完全二叉树的深度个结点的完全二叉树的深度h= log2n +1. . 二叉树的存储结构二叉树的存储结构 一一. .二叉树的顺序存储结构二叉树的顺序存储结构 1 23 45 67

8、8910 A BC DEFG HIJ BT1:15 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 A B C D E F G H I J 根据完全二叉树的性质根据完全二叉树的性质 , ,对于深度为对于深度为h 的完全二叉树的完全二叉树, , 将树中所有结点的数据信息按照编号的顺序依次存储到一将树中所有结点的数据信息按照编号的顺序依次存储到一 维数组维数组BT1:2h-1中中, ,由于编号与数组的下标一一对应由于编号与数组的下标一一对应, 该该 数组就是该完全二叉树的顺序存储结构数组就是该完全二叉树的顺序存储结构. . 1. 完全二叉树的顺序存储结构完全二叉树的顺序存储

9、结构 1 23 4 5 67 8910 A BC D E FG H IJ 111213 BT1:15 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 A B C D E F G H J I A BC DEFG HIJ 2. . 一般二叉树的顺序存储结构一般二叉树的顺序存储结构 2021/3/1116 对于一般二叉树对于一般二叉树, 只须在二叉树中只须在二叉树中“添加添加”一些实际一些实际 上上 二叉树中并不存在的二叉树中并不存在的“虚结点虚结点” ( 可以认为这些结点的数可以认为这些结点的数 据据 信息为空信息为空), 使其在形式上成为一棵使其在形式上成为一棵“完全二叉

10、树完全二叉树”, 然然 后后 按照完全二叉树的顺序存储结构的构造方法将所有结点的按照完全二叉树的顺序存储结构的构造方法将所有结点的 数据信息依次存放于数组数据信息依次存放于数组BT1: 2h -1中。中。 二二. .二叉树的链式存储结构二叉树的链式存储结构( (二叉链表二叉链表) ) 链结点的构造为链结点的构造为 lchilddatarchild 其中其中, data 为数据域为数据域 lchild 与与rchild 分别为指向左、右子树的指针域分别为指向左、右子树的指针域. A BC DEF G I J A BC DEFG J I T 6.3.3 二叉树的遍历二叉树的遍历 二二. .前序遍历

11、前序遍历 三三. .中序遍历中序遍历 四四. .后序遍历后序遍历 2021/3/1122 A BC DKF G I J E H 前序遍历序列前序遍历序列: : 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 例例 2021/3/1123 6.3.2 6.3.2 线索二叉树线索二叉树 1.1.

12、何谓线索二叉树？何谓线索二叉树？ 遍历结果是求得结点的一个线性序列。指向遍历结果是求得结点的一个线性序列。指向 该线性序列该线性序列“前驱前驱”和和“后继后继”的指针，称的指针，称“线线 索索”；包含；包含“线索线索”的存储结构，称为的存储结构，称为“线索链线索链 表表”；与其相应的二叉树，称为；与其相应的二叉树，称为“线索二叉树线索二叉树”； 对二叉树以某种次序遍历，使其变为线索二叉树对二叉树以某种次序遍历，使其变为线索二叉树 的过程，称为的过程，称为“线索化线索化”。 2.2.线索链表中结点的结构线索链表中结点的结构 标志域标志域 lchildLTagdataRTag rchild 其中：

13、其中： LTag =LTag = 0 lchild 0 lchild 域指示结点的左孩子域指示结点的左孩子 1 lchild 1 lchild 域指示结点的前驱域指示结点的前驱 RTag =RTag = 0 rchild 0 rchild 域指示结点的右孩子域指示结点的右孩子 1 rchild 1 rchild 域指示结点的后继域指示结点的后继 2021/3/1125 二叉树二叉线索存储表示二叉树二叉线索存储表示 typedef enum Link, Thread PointerThr; typedef enum Link, Thread PointerThr; / Link=0:/ Link

14、=0:指针，指针，Thread=1:Thread=1:线索线索 typedef struct BiThrNodetypedef struct BiThrNode TElemType data; TElemType data; Struct BiThrNode Struct BiThrNode * *lchild, lchild, * *rchild;rchild; / / 左右孩子指针左右孩子指针 PointerThr LTag, RTag; PointerThr LTag, RTag; / / 左右标志左右标志 BiThrNode, BiThrNode, * *BiThrTree;BiThr

15、Tree; 2021/3/1126 3.3.线索二叉树图例线索二叉树图例 线索二叉树及其存储结构线索二叉树及其存储结构 （a a）中序线索二叉树）中序线索二叉树 （b b）中序线索链表）中序线索链表 1 23 4 5 67 0 1 0 0 2 01 3 1 1 4 10 5 0 1 6 11 7 1 thrt0 1 2021/3/1127 如何在线索树中找结点的后继？如何在线索树中找结点的后继？ 结合中序线索树结合中序线索树 若其右标志为若其右标志为“1 1”，右链是线索，右链直接指，右链是线索，右链直接指 示了结点的后继；示了结点的后继； 若其右标志为若其右标志为“0 0”，右链是指针，其后

16、继为右，右链是指针，其后继为右 子树中最左下的结点。子树中最左下的结点。 1 23 4 5 67 2021/3/1128 如何在线索树中找结点的前驱？如何在线索树中找结点的前驱？ 结合中序线索树结合中序线索树 若其左标志为若其左标志为“1 1”，左链为线索，直接指示，左链为线索，直接指示 其前驱；其前驱； 若其左标志为若其左标志为“0 0”，左子树中最右下的结点，左子树中最右下的结点 为其前驱。为其前驱。 1 23 4 5 67 2021/3/1129 线索链表的中序遍历算法线索链表的中序遍历算法 Status IOTraver_T( BiThrTree T,Status (Status IO

17、Traver_T( BiThrTree T,Status (* *Visit)(TElemType e) )Visit)(TElemType e) ) /T/T指向头结点，头结点的左链指向头结点，头结点的左链lchildlchild指向根结点，中序遍历指向根结点，中序遍历 /二叉线索树二叉线索树T T的非递归算法，对每个数据元素调用函数的非递归算法，对每个数据元素调用函数VisitVisit。 p = T-lchild; p = T-lchild; /p/p指向根结点指向根结点 while (p != T) while (p != T) /空树或遍历结束时，空树或遍历结束时，p = = Tp

18、= = 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 Visit(p-data); p = p-rchild; Visit(p-data); /访问后继结点访问后继结点 p = p-rchild; p = p-rchild; return OK; retur

19、n OK; / IOTraver_T/ IOTraver_T 0 1 0 0 2 01 3 1 1 4 10 5 0 1 6 11 7 1 T0 1 1 2021/3/1130 6.4.2 6.4.2 森林和二叉树的转换森林和二叉树的转换 1. 1. 树和二叉树的对应关系树和二叉树的对应关系 由于二叉树和树都可用二叉链表作为存储结由于二叉树和树都可用二叉链表作为存储结 构，则以二叉链表作为媒介可导出树与二叉树之构，则以二叉链表作为媒介可导出树与二叉树之 间的一个对应关系。间的一个对应关系。 2021/3/1131 2021/3/1132 树转换为二叉树方法：树转换为二叉树方法： 1 1）对每个

20、孩子进行从左到右的排序；）对每个孩子进行从左到右的排序； 2 2）在兄弟之间加一条连线；）在兄弟之间加一条连线； 3 3）对每个结点，除了左孩子外，去除其与其余）对每个结点，除了左孩子外，去除其与其余 孩子之间的联系；孩子之间的联系； 4 4）以根结点为轴心，将整个树顺时针转）以根结点为轴心，将整个树顺时针转4545。 2021/3/1133 A BCD EGHFI a a A BCD EGHFIb b A BCD EGHFIc c A B C D E G H F I d d 2021/3/1134 2. 2. 森林和二叉树的对应关系森林和二叉树的对应关系 从树的二叉链表表示的定义可知，任何一

21、棵从树的二叉链表表示的定义可知，任何一棵 和树对应的二叉树，其和树对应的二叉树，其右子树必空右子树必空。 若把森林中第二棵树的根结点看成是第一棵若把森林中第二棵树的根结点看成是第一棵 树的根结点的兄弟，则同样可导出森林和二叉树树的根结点的兄弟，则同样可导出森林和二叉树 的对应关系。的对应关系。 2021/3/1135 2021/3/1136 BCD EGHFI a a BCD EGHFIb b BCD EGHFIc c B C D E G H F I d d 2021/3/1137 已知条件：森林和二叉树的对应关系设已知条件：森林和二叉树的对应关系设 森森 林林 F = ( TF = ( T1

22、 1, T, T2 2, , , T, Tn n ); ); T T1 1 = (root = (root，t t11 11, t , t12 12, , , t, t1m 1m); ); 二叉树二叉树 B =( LBT, Node(root), RBT );B =( LBT, Node(root), RBT ); 由森林转换成二叉树的转换规则为由森林转换成二叉树的转换规则为: : 若若 F = F = ，则，则 B = ;B = ; 否则，由否则，由 Root( TRoot( T1 1 ) ) 对应得到对应得到 Node(root);Node(root); 由由 (t(t11 11, t ,

23、 t12 12, , , t, t1m 1m ) ) 对应得到对应得到 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( t11 11, t , t12 12, , ，t t1m 1m);T );T1 1除根以外所除根以外所

24、构成的森林构成的森林 由由RBT RBT 对应得到对应得到 (T(T2 2, T, T3 3, , , T, Tn n) )；除；除T T1 1之外的森林之外的森林 2021/3/1138 6.4.3 6.4.3 树和森林的遍历树和森林的遍历 1. 1. 树的遍历树的遍历：有三条搜索路径：有三条搜索路径 先根先根( (序序) )遍历：遍历：若树不空，则先访问根结点，若树不空，则先访问根结点， 然后依次先根遍历各棵子树。然后依次先根遍历各棵子树。 后根后根( (序序) )遍历：遍历：若树不空，则先依次后根遍历若树不空，则先依次后根遍历 各棵子树，然后访问根结点。各棵子树，然后访问根结点。 按层次遍历：按层次遍历： 若树不空，则自上而下自左至若树不空，则自上而下自左至 右访问树中每个结点。右访问树中每个结点。 2021/3/1139 例例 对树进行先根遍历，获得的先根序列是：对树进行先根遍历，获得的先根序列是： 对树进行后根遍历，获得的后根序列是：对树进行后根遍历，获得的后根序列是： A BCD EGHFI A B E F C D G H IA B E F C D G H I E F B C G H I D AE F B C G H I D A 2021/3/1140 2.2.森林的遍历森林的遍历 先序遍历