数据结构树的ppt

《数据结构树的ppt》由会员分享，可在线阅读，更多相关《数据结构树的ppt（42页珍藏版）》请在金锄头文库上搜索。

1、第6章 树与二叉树校长一 系二 系三 系六 系教 务 处科 研 处总 务 处601 602教 务 科603A B CD张 三李 四王 五例1工厂(根目录)f1f2f3fnd1d2dm例2f11f12f1kd11d12 例31 树的基本概念 2 树的存储结构 3 二叉树4 二叉树的存储结构5 二叉树的遍历6 线索二叉树6.1 树的基本概念树是由n0 个结点组成的有穷集合(不妨用D表示) 以及结点之间关系组成的集合构成的结构。当n=0 时，称该树为空树；在任何一棵非空的树中，有一个特殊的结点t D， 称之为该树的根结点；其余结点Dt被分割成m0个 不相交的子集D1, D2, ,Dm,其中每一个子集

2、Di又为一棵 树，分别称之为t 的子树。递归定义一. 树的定义JIHGFEACXBA的第1棵子树A的第3棵子树A的第2棵子树二. 树(逻辑上)的特点1. 有且仅有一个结点没有前驱结点,该结点为树的根结点。 2. 除了根结点外,每个结点有且仅有一个直接前驱结点。 3. 包括根结点在内，每个结点可以有多个后继结点。JIHGFEACXB4. 树形表示法 借助自然界中一棵倒置的树的形状来表示数 据元素之间层次关系的方法。1. 结点的度： 2. 树的度： 3. 叶结点： 4. 分支结点: 5. 层次的定义:JIHGFEACXB该结点拥有的子树的数目。 树中结点度的最大值。 度为0 的结点. 度非0 的结

3、点.根结点为第一层,若某结点在第i 层,则其孩子结点(若存在)为第i+1层.四. 基本名词术语第1层第2层第3层7. 树林(森林): m0 棵不相交的树组成的树的集合. 8. 树的有序性:6. 树的深度:树中结点所处的最大层次数.若树中结点的子树的相对位置不能随意改变, 则称该树为有序树，否则称该树为无序树。JIHGFEACXB深度为3的树二叉树的基本形态：(空)根根左 子 树根右 子 树根左 子 树右 子 树6.2 二叉树二. 两种特殊形态的二叉树若一棵二叉树中的结点, 或者为叶结点， 或者具有两 棵非空子树,并且叶结点都集 中在二叉树的最下面一层.这 样的二叉树为满二叉树.1. 满二叉树若

4、一棵二叉树中只有最下 面两层的结点的度可以小于2, 并且最下面一层的结点(叶结 点)都依次排列在该层从左至 右的位置上。这样的二叉树为 完全二叉树.2.完全二叉树1. 一棵非空二叉树的第i 层最多有2i1个结点(i1)。三. 二叉树的性质2. 深度为h 的非空二叉树最多有2h -1个结点.3. 若非空二叉树有n0个叶结点,有n2个度为2的结点,则 n0=n2+1 4. 具有n个结点的完全二叉树的深度h=log2n+1.二叉树的存储结构一.二叉树的顺序存储结构12345678910ABCDEFGHIJBT1:151 2 3 4 5 6 7 8 9 10 11 12 13 14 15A B C D

5、 E F G H I J 根据完全二叉树的性质 ,对于深度为h 的完全二叉树, 将树中所有结点的数据信息按照编号的顺序依次存储到一 维数组BT1:2h-1中,由于编号与数组的下标一一对应, 该 数组就是该完全二叉树的顺序存储结构.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 IABCDEFGHIJ2. 一般二叉树的顺序存储结构对于一般二叉树, 只须在二叉树中“添加”一些实际上 二叉树中并不存在的“虚结点” ( 可以认为这些结点的数据 信息为

6、空), 使其在形式上成为一棵“完全二叉树”, 然后 按照完全二叉树的顺序存储结构的构造方法将所有结点的 数据信息依次存放于数组BT1: 2h -1中。二.二叉树的链式存储结构(二叉链表) 链结点的构造为 lchilddatarchild其中, data 为数据域lchild 与rchild 分别为指向左、右子树的指针域.ABCDEFGIJABCDEFGJIT6.3.3 二叉树的遍历二.前序遍历三.中序遍历四.后序遍历ABCDKFGIJEH前序遍历序列:A, B, D, K, J, G, C, F, I, E, H中序遍历序列:D, B, G, J, K, A, F, I, E, C, H后序遍

7、历序列: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.何谓线索二叉树？遍历结果是求得结点的一个线性序列。指向该线性序列“前驱”和“后继”的指针，称“线索”；包含“线索”的存储结构，称为“线索链表”；与其相应的二叉树，称为“线索二叉树”；对二叉树以某种次序遍历，使其变为线索二叉树的过程，称为“线索化”。2.线索链表中结点的结构在二叉链表的结点结构中增加两个在二叉链表的结点结构中增加两个标志域，并，并规定：规定：lchildLTagdataRTag rchild其中：LTag

8、=0 lchild 域指示结点的左孩子1 lchild 域指示结点的前驱RTag =0 rchild 域指示结点的右孩子1 rchild 域指示结点的后继二叉树二叉线索存储表示typedef enum Link, Thread PointerThr; / Link=0:指针，Thread=1:线索typedef struct BiThrNodeTElemType data;Struct BiThrNode *lchild, *rchild;/ 左右孩子指针PointerThr LTag, RTag; / 左右标志 BiThrNode, *BiThrTree;3.线索二叉树图例线索二叉树及其存储

9、结构（a）中序线索二叉树 （b）中序线索链表12345670 1 00 2 01 3 11 4 10 5 01 6 11 7 1thrt0 1如何在线索树中找结点的后继？结合中序线索树若其右标志为“1”，右链是线索，右链直接指 示了结点的后继；若其右标志为“0”，右链是指针，其后继为右 子树中最左下的结点。 1234567如何在线索树中找结点的前驱？结合中序线索树若其左标志为“1”，左链为线索，直接指示其 前驱；若其左标志为“0”，左子树中最右下的结点为 其前驱。 1234567线索链表的中序遍历算法Status IOTraver_T( BiThrTree T,Status (*Visit)(

10、TElemType e) ) /T指向头结点，头结点的左链lchild指向根结点，中序遍历/二叉线索树T的非递归算法，对每个数据元素调用函数Visit。p = T-lchild; /p指向根结点 while (p != T) /空树或遍历结束时，p = = Twhile (p-LTag=Link) p = p-lchild; if (!Visit(p-data) return ERROR; /访问其左子树为空的结点while (p-RTag=Thread Visit(p-data); /访问后继结点p = p-rchild; return OK; / IOTraver_T0 1 00 2 01

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

12、看成是第一棵树的根结点的兄弟，则同样可导出森林和二叉树的对应关系。BCDEGHFIaBCDEGHFIbBCDEGHFIcBCDEGHFId已知条件：森林和二叉树的对应关系设森 林 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。 由二叉树转换

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

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