树和二叉树 数据结构.ppt

数据结构数据结构线性结构——一个对一个，如线性表、栈、队列树形结构——一个对多个，如树集合——数据元素间除“同属于一个集合”外，无其它关系图形结构——多个对多个，如图逻辑结构第6章 树和二叉树6.1 树的定义和基本术语 6.2 二叉树 6.3 遍历二叉树与线索二叉树 6.4 树和森林 6.5 霍夫曼树及其应用1. 掌握二叉树的基本概念、性质和存储结构 2. 熟练掌握二叉树的前、中、后序遍历方法 3. 了解线索化二叉树的思想 4. 熟练掌握：霍夫曼树的实现方法、构造霍夫曼编 码的方法 5. 了解：森林与二叉树的转换，树的遍历方法教学目标6.1 树的定义和基本术语树是n个结点的有限集T1T2T3ADT Tree{ 数据对象D: 数据关系R:基本操作 P ： }ADT Tree若D为空集，则称为空树；//允许n=0 若D中仅含一个数据元素，则R为空集； 其他情况下的R存在二元关系：① root 唯一 //关于根的说明② Dj∩Dk= Φ //关于子树不相交的说明③ …… //关于数据元素的说明D是具有相同特性的数据元素的集合//至少有15个树的抽象数据类型定义凹入表示嵌套集合广义表树的其它表示方式根 叶子森林有序树 无序树——即根结点(没有前驱) ——即终端结点(没有后继) ——指m棵不相交的树的集合(例如删除A后的子树个数)——结点各子树从左至右有序，不能互换（左为第一） ——结点各子树可互换位置。

基本术语——即上层的那个结点(直接前驱) ——即下层结点的子树的根(直接后继) ——同一双亲下的同层结点（孩子之间互称兄弟） ——即双亲位于同一层的结点（但并非同一双亲） ——即从根到该结点所经分支的所有结点 ——即该结点下层子树中的任一结点双亲 孩子 兄弟 堂兄弟 祖先 子孙基本术语——即树的数据元素 ——结点挂接的子树数结点 结点的度 结点的层次 终端结点 分支结点 树的度 树的深度 (或高度)——从根到该结点的层数（根结点算第一层） ——即度为0的结点，即叶子 ——即度不为0的结点（也称为内部结点） ——所有结点度中的最大值 ——指所有结点中最大的层数 层次1234基本术语MINEBDAGJKCFLH1) 哪是根节点2）哪是叶子节点3）哪个节点是G的双亲4）哪些是G的祖先5）哪些节点是G的孩子6）哪些节点是E的子孙7）哪些节点是E的兄弟8）节点B和N的层次号是分别是多少9）树的深度是多少10）以节点C为根的子树的深度是多少11）树的度数是多少MINEBDAGJKCFLH6.2 二叉树普通树（多叉树）若不转化为二叉树，则运算很难实现为何要重点研究每结点最多只有两个 “叉” 的树？ü 二叉树的结构最简单，规律性最强； ü 可以证明，所有树都能转为唯一对应的二叉树，不 失一般性。

二叉树二叉树基本特点：特点：• •结点的度小于等于结点的度小于等于2 2• •有序树（子树有序，不能颠倒）有序树（子树有序，不能颠倒）二叉树的五种不同形态二叉树的五种不同形态具有具有3 3个结点的二叉树可能有几种不同形态？普通树呢？个结点的二叉树可能有几种不同形态？普通树呢？ 练习5种/2种• 一棵度为2的树与一棵二叉树有何区别？• 解：二叉树是颗有序树，但度为2的树则 未必有序 ADT BinaryTree{ 数据对象D: 数据关系R:基本操作 P： }ADT BinaryTree若D=Φ，则R= Φ ； 若D≠Φ，则R= {H}；存在二元关系：① root 唯一 //关于根的说明② Dj∩Dk= Φ //关于子树不相交的说明③ …… //关于数据元素的说明④ …… //关于左子树和右子树的说明D是具有相同特性的数据元素的集合//至少有20个二叉树的抽象数据类型定义性质1: 在二叉树的第i层上至多有2 2i-1i-1个结点二叉树的性质提问：第i层上至少有 个结点？性质2: 深度为k的二叉树至多有2 2k k-1-1个结点提问：深度为k时至少有 个结点？1k性质3: 对于任何一棵二叉树，若2度的结点数有n2 个，则叶子数n0必定为n2＋1 （即n0=n2+1）满二叉树：一棵深度为一棵深度为 k k 且有且有2 2k -1 -1个结点的个结点的 二叉树。

二叉树特点：每层 都“充满”了结点）特殊形态的二叉树完全二叉树：深度为k 的， 有n个结点的二叉树，当且 仅当其每一个结点都与深度 为k 的满二叉树中编号从1 至n的结点一一对应只有最后一层叶子不满 ，且全部集中在左边满二叉树是叶子一个也不少的树，而完全二叉树虽然 前n-1层是满的，但最底层却允许在右边缺少连续若 干个结点满二叉树是完全二叉树的一个特例满二叉树和完全二叉树的区别一棵完全二叉树有5000个结点，可以计算出其 叶结点的个数是（ ） 练习2500性质4: 具有n个结点的完全二叉树的深度必为log2n＋1k层nk-1层性质5: 对完全二叉树，若从上至下、从左至右编号，则 编号为i 的结点，其左孩子编号必为2i，其右孩子编号 必为2i＋1；其双亲的编号必为i/2二叉树的顺序存储实现：按实现：按满二叉树满二叉树的结点层次编号，依次存放二叉的结点层次编号，依次存放二叉 树中的数据元素树中的数据元素a b c d e 0 0 0 0 f g 0 1 2 3 4 5 6 7 8 9 10abcdefg特点：特点： 结点间关系蕴含在其存储位置中结点间关系蕴含在其存储位置中 浪费空间，适于存浪费空间，适于存满二叉树和完全二叉树满二叉树和完全二叉树单支树二叉树的顺序存储DATAPARENTLCHILDRCHILD二叉树的链式存储ABCDEFGABC DE FG^^^^^^^^二叉链表typedef struct BiNode{TElemType data;struct BiNode *lchild,*rchild; //左右孩子指针}BiNode,*BiTree; 分析：必有2n个链域。

除根结 点外，每个结点有且仅有一个 双亲，所以只会有n－1个结点 的链域存放指针，指向非空子 女结点空指针数目＝2n－(n-1)=n+1在在n n个结点的二叉链表中，个结点的二叉链表中，有 个空指针域空指针域练习ABC DE FG^^^^^^^^n+1三叉链表ABCDEFGAB C DE FG^^^^^^^^^lchild data parent rchildtypedeftypedef structstruct TriTNodeTriTNode { { TelemTypeTelemType data; data;structstruct TriTNodeTriTNode * *lchildlchild,*parent,*,*parent,*rchildrchild; ;} }TriTNodeTriTNode,*,*TriTreeTriTree; ;6.3 遍历二叉树和线索二叉树遍历定义——指按某条搜索路线遍访每个结点且 不重复（又称周游）遍历用途——它是树结构插入、删除、修改、查 找和排序运算的前提，是二叉树一 切运算的基础和核心。

DLRDLRLDRLRDDRLRDLRLD遍历规则先左后右先序遍历：中序遍历：后序遍历：A B CD EA B D E CA B D E CD B E A CD B E A CD E B C AD E B C A口诀：DLR—先序遍历，即先根再左再右LDR—中序遍历，即先左再根再右LRD—后序遍历，即先左再右再根+*A*/EDCB先序遍历 + * * / A B C D E 前缀表示中序遍历 A / B * C * D + E 中缀表示后序遍历 A B / C * D * E + 后缀表示层序遍历 + * E * D / C A B用二叉树表示算术表达式D L RA D L RD L R>B>>D>>CD L RADBC先序遍历序列：先序遍历序列：A B D CA B D C若二叉树为空，则空操作 否则 访问根结点 (D) 前序遍历左子树 (L) 前序遍历右子树 (R)遍历的算法实现－先序遍历则三种遍历算法可写出:遍历的算法实现－－用递归形式格外简单！用递归形式格外简单！long Factorial ( long n ) {if ( n == 0 ) return 1;//基本项else return n * Factorial (n-1); //归纳项}回忆:Status PreOrderTraverse(BiTree T){if(T==NULL) return OK; //空二叉树else{ coutdata; //访问根结点PreOrderTraverse(T->lchild); //递归遍历左子树PreOrderTraverse(T->rchild); //递归遍历右子树} }先序遍历算法Status PreOrderTraverse(BiTree T){if(T==NULL) return OK; else{ coutdata; PreOrderTraverse(T->lchild); PreOrderTraverse(T->rchild); } }主程序Pre( T )返回返回pre(T R);返回返回pre(T R);ACBDTBprintf(B); pre(T L);BTAprintf(A); pre(T L);ATDprintf(D); pre(T L);DTCprintf(C); pre(T L);C返回T>左是空返回pre(T R);T>左是空返回T>右是空返回T>左是空返回T>右是空返回pre(T R);先序序列：ABDC遍历的算法实现－中序遍历若二叉树为空，则空操作若二叉树为空，则空操作 否则否则: : 中序遍历左子树中序遍历左子树 (L)(L) 访问根结点访问根结点 (D)(D) 中序遍历右子树中序遍历右子树 (R)(R)ADBCL D RBL D RL D R>A>>D>>CL D R中序遍历序列：中序遍历序列：B D A CB D A CStatus InOrderTraverse(BiTree T){if(T==NULL) return OK; //空二叉树else{ InOrderTraverse(T->lchild); //递归遍历左子树coutdata; //访问根结点InOrderTraverse(T->rchild); //递归遍历右子树} }中序遍历算法遍历的算法实现－后序遍历若二叉树为空，则空操作 否则 后序遍历左子树 (L) 后序遍历右子树 (R) 访问根结点 (D)ADBCL R DL R DL R DA>>D>>CL R DB后序遍历序列：后序遍历序列： D B C AD B C AStatus PostOrderTraverse(BiTree T){if(T==NULL) return OK; //空二叉树else{ PostOrderTraverse(T->lchild); //递归遍历左子树PostOrderTraverse(T->rchild); //递归遍历右子树co。