数据结构二叉树ppt.ppt

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

2、度为0 的结点.,度非0 的结点.,根结点为第一层,若某结点在第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个

3、结点的完全二叉树的深度h=log2n+1.,二叉树的存储结构,一.二叉树的顺序存储结构,1. 完全二叉树的顺序存储结构,2. 一般二叉树的顺序存储结构,A,16,二.二叉树的链式存储结构(二叉链表),二.前序遍历,三.中序遍历,四.后序遍历,A,22,前序遍历序列: 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,A,23,6.3.2 线索

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

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

6、其后继为右子树中最左下的结点。,A,28,如何在线索树中找结点的前驱？,结合中序线索树 若其左标志为“1”，左链为线索，直接指示其前驱； 若其左标志为“0”，左子树中最右下的结点为其前驱。,A,29,线索链表的中序遍历算法 Status IOTraver_T( BiThrTree T,Status (*Visit)(TElemType e) ) /T指向头结点，头结点的左链lchild指向根结点，中序遍历 /二叉线索树T的非递归算法，对每个数据元素调用函数Visit。 p = T-lchild; /p指向根结点 while (p != T) /空树或遍历结束时，p = = T while (p

7、-LTag=Link) p = p-lchild; if (!Visit(p-data) return ERROR; /访问其左子树为空的结点 while (p-RTag=Thread / IOTraver_T,A,30,6.4.2 森林和二叉树的转换,1. 树和二叉树的对应关系 由于二叉树和树都可用二叉链表作为存储结构，则以二叉链表作为媒介可导出树与二叉树之间的一个对应关系。,A,31,A,32,树转换为二叉树方法：,1）对每个孩子进行从左到右的排序； 2）在兄弟之间加一条连线； 3）对每个结点，除了左孩子外，去除其与其余孩子之间的联系； 4）以根结点为轴心，将整个树顺时针转45。,A,33

8、,A,34,2. 森林和二叉树的对应关系 从树的二叉链表表示的定义可知，任何一棵和树对应的二叉树，其右子树必空。 若把森林中第二棵树的根结点看成是第一棵树的根结点的兄弟，则同样可导出森林和二叉树的对应关系。,A,35,A,36,A,37,已知条件：森林和二叉树的对应关系设 森 林 F = ( T1, T2, , Tn ); T1 = (root，t11, t12, , t1m); 二叉树 B =( LBT, Node(root), RBT ); 由森林转换成二叉树的转换规则为: 若 F = ，则 B = ; 否则，由 Root( T1 ) 对应得到 Node(root); 由 (t11, t1

9、2, , t1m ) 对应得到 LBT; 由 (T2, T3, Tn ) 对应得到 RBT。 由二叉树转换为森林的转换规则为: 若 B = , 则 F = ; 否则，由 Node(root) 对应得到 Root( T1 ); 由LBT 对应得到 ( t11, t12, ，t1m);T1除根以外所 构成的森林 由RBT 对应得到 (T2, T3, , Tn)；除T1之外的森林,A,38,6.4.3 树和森林的遍历,1. 树的遍历：有三条搜索路径 先根(序)遍历：若树不空，则先访问根结点， 然后依次先根遍历各棵子树。 后根(序)遍历：若树不空，则先依次后根遍历 各棵子树，然后访问根结点。 按层次遍

10、历： 若树不空，则自上而下自左至 右访问树中每个结点。,A,39,例 对树进行先根遍历，获得的先根序列是： 对树进行后根遍历，获得的后根序列是：,A B E F C D G H I,E F B C G H I D A,A,40,2.森林的遍历,先序遍历(对森林中的每一棵树进行先根遍历) 1）若森林不空，访问森林中第一棵树的根结点； 2）先序遍历森林中第一棵树的子树森林； 3）先序遍历森林中(除第一棵树外)其余树构成的森林。 后序遍历(对森林中的每一棵树进行后根遍历) 1）若森林不空，后序遍历森林中第一棵树的子树森林； 2）访问森林中第一棵树的根结点； 3）后序遍历森林中(除第一棵树外)其余树构成的森林。,A,41,例： 对森林进行先序遍历，获得的先序序列是： 对森林进行后序遍历，获得的后序序列是：,B E F C D G H I,E F B