数据结构chapter06.ppt

第六章 树与二叉树 6.1 树的类型定义 基本操作： 查找类： 插入类： 删除类： 树定义示例: 有向树、有序树和无序树 基 本 术 语 树型结构和线性结构 6.2 二叉树的类型定义 二叉树的五种基本形态： 二叉树的主要基本操作： 二叉树的重要特性 两类特殊的二叉树： 性质 4 ： 具有 n 个结点的完全二叉树的深度为 ? log2n? +1 6.3 二叉树的存储结构 一、 二叉树的顺序存储表示 二、二叉树的链式存储表示 1. 二叉链表 2．三叉链表 3．双亲链表 6.4 二叉树的遍历 一、问题的提出 二叉树的三条遍历路径： 二、先左后右的遍历算法 先（根）序的遍历算法： 中（根）序的遍历算法： 后（根）序的遍历算法： 三、算法的递归描述 四、中序遍历算法的非递归描述 一、“任务书”分析方法 二、“路径”分析方法 四、遍历算法的应用举例 1、建立二叉树的存储结构 不同的定义方法相应有不同的存储结构的建立算法 通过给定字符串建立二叉树 由先序和中序序列建立二叉树 2、复制二叉树 3、二叉树中的查找 （1）在二叉树中查找指定元素 （2）统计二叉树中叶子结点的个数 统计叶子结点方法1 统计叶子结点方法2 （3）统计二叉树中所有结点的个数 4、求二叉树的深度(后序遍历) 6.5线索二叉树 何谓线索二叉树？ 线索链表的遍历算法 如何建立线索链表？ 一、何谓线索二叉树？ 二、线索链表的遍历算法: 中序线索二叉树中的头结点 为了方便操作，可以在中序线索二叉树中加入一个头结点，使其lchild指向二叉树的根结点，而rchild指向最右下的结点。这时最左下结点的lchild成为线索指针，指向头结点前驱，而最右下结点的rchild也成为线索指针，指向头结点后继。 由于头结点的左子树指针指向根结点，右子树指针指针指向最右下结点，同时最左下结点的左子树指针指向头结点，最右下结点的右子树指针指向头结点，这样加入头结点的线索二叉树就形成了一个双向链表，因此可以从任意结点开始，遍历线索二叉树 为空树时的带头结点线索二叉树 三、如何建立线索链表？ 6.6 树和森林的表示方法 一、双亲表示法: 二、孩子链表表示法: 三、树的二叉链表 (孩子-兄弟）存储表示法 森林和二叉树的对应关系 由森林转换成二叉树的转换规则为: 由二叉树转换为森林的转换规则为: 6.7树和森林的遍历 一、树的遍历 二、森林的遍历 三、树遍历算法的应用 求树的深度 输出树中所有从根到叶子的路径 建树的存储结构 1、求树的深度算法（1） 设树的存储结构为孩子兄弟链表 1、求树的深度的算法（2） 设树的存储结构为孩子链表 2、输出树中所有从根到叶子的路径的算法: 3、建树的存储结构的算法: 6.8 哈 夫 曼 树 与 哈 夫 曼 编 码 最优树的定义 如何构造最优树 前缀编码 一、最优树的定义 二、如何构造最优树 三、前缀编码 第六章 结束 int Depth( CTree T, int root ){ max = 0; p = T.nodes[root].firstchild; while ( p ) { h = Depth( T, p-child ); if ( h max ) max = h; p = p-nextchild; }/*end while*/ return max+1; } A B C D E F G H I J K 例如：对左图所示的树，其输出结果应为： A B E A B F A C A D G H I A D G H J A D G H K void AllPath( BiTree T, Stack *S ) { if (T) { push( S, T-data ); if (!T-Lchild !T-Rchild ) PrintStack(S); else { AllPath( T-Lchild, S ); AllPath( T-Rchild, S ); } pop(S); } /* end if(T)*/ } /*end AllPath*/ /* 输出二叉树上从根到所有叶子结点的路径*/ void OutPath( Bitree T, Stack *S ) { while ( T !=NULL) { push(S, T-dat