哈夫曼树和其应用.ppt

第6章 树和二叉树;6.1 树的概念与定义;例如：;1. 树型表示法 2. 嵌套集合表示法;树的基本术语;有关树的一些术语：;双亲结点：一个结点的直接前驱称为该结点的双亲结点。上图中A是B、C、D的双亲。;结点的层次：从根结点开始定义，根结点的层次为1，根的直接后继的层次为2，依此类推。 ;树的抽象数据类型定义：;基本操作：;(7) FirstChild（Tree，x）： 树Tree存在，x是Tree中的某个结点。若x为非叶子结点，则返回它的第一个孩子结点，否则返回“空”。 (8) NextSibling（Tree，x）： 树Tree存在，x是Tree中的某个结点。若x不是其双亲的最后一个孩子结点，则返回x后面的下一个兄弟结点，否则返回“空”。 (9) InsertChild（Tree，p，Child）： 树Tree存在，p指向Tree中某个结点，非空树Child与Tree不相交。将Child插入Tree中，做p所指向结点的子树。 ;基本操作:;6.2 二叉数;6.2.1 二叉树的定义与基本操作;二叉树的基本操作：;基本操作：;6.2.2 二叉树的性质;性质2：深度为k的二叉树至多有2k-1个结点（k≥1）。 ;性质3：对任意一棵二叉树T，若终端结点数为n0，而其度数为2的结点数为n2，则n0= n2+1 。;两种特殊的二叉树：;定义2：完全二叉树：;性质4：具有n个结点的完全二叉树的深度为?㏒2n?+1。 ;性质5：对于具有n个结点的完全二叉树，如果按照从上到下和从左到右的顺序对二叉树中的所有结点从1开始顺序编号，则对于任意的序号为i的结点有： ;6.2.3 二叉树的存储结构;完全二叉树 一般二叉树 的顺序表示 的顺序表示; 对于一般的二叉树，我们必须按照完全二叉树的形式来存储，就会造成空间的浪费。单支树就是一个极端情况。;链表表示;二叉树链表表示的示例; ;结论：若一个二叉树含有n个结点，则它的二叉链表中必含有2n个指针域，其中必有n＋1个空的链域。;6.3 二叉树的遍历与线索化;用L、D、R分别表示遍历左子树、访问根结点、遍历右子树，那么对二叉树的遍历顺序就可以有：;在以上六种遍历方式中，如果我们规定按先左后右的顺序，那么就只剩有 DLR 、LDR 和LRD三种。根据对根的访问先后顺序不同，分别称DLR为先序遍历或先根遍历；LDR为中序遍历（对称遍历）；LRD为后序遍历。 ;三种遍历方法的递归定义：;若二叉树为空，则空操作，否则依次执行如下操作： （1）按中序遍历左子树； （2）访问根结点； （3）按中序遍历右子树。 ;后序遍历（LRD）操作过程：;对于如下图的二叉树，其先序、中序、后序遍历的序列为： 先序遍历： A、B、D、F、G、C、E、H 。 中序遍历： B、F、D、G、A、C、E、H 。 后序遍历： F、G、D、B、H、E、C、A 。 ;以二叉链表作为存储结构，讨论二叉树的遍历算法;2) 中序遍历;3) 后序遍历;以中序遍历为例来说明中序遍历二叉树的递归过程;6.3.2 基于栈的递归消除;中序遍历二叉树的非递归算法（直接实现栈操作）; { p=s[top]; top=top-1; Visit(p-data); /*访问根结点*/ p=p-Rchild;} /*遍历右子树*/ } }while(p!=NULL||top!=0) } ;中序遍历二叉树的非递归算法（调用栈操作的函数）;2) 后序遍历的二叉树的非递归算法; { p=s[top]; if((p-RChild==NULL) ||(p-RChild==q)) /* 无右孩子，或右孩子已遍历过 */ { visit(p-data); /* 访问根结点* / q=p; /* 保存到q，为下一次已处理结点前驱 */ top--; p=NULL; } else p=p-RChild; } } free(s); };6.3.3 遍历算法应用;先序遍历输出二叉树中的结点;2. 输出二叉树中的叶子结点;3. 统计叶子结点数目;int leaf(BiTree root) { int LeafCount; if(root==NULL) LeafCount =0; else if((root-LChild==NULL)(root-RChild==NULL)) LeafCount =1; else LeafC