[工学]数据结构-树.ppt

第六章 树和二叉树 树的示意图： 作 业 已知二叉树有50个叶子结点，则该二叉树的总结点数至少应有多少个？ 任意一个有n个结点的二叉树，已知它有m个叶子结点，试证明非叶子结点中有（m-1）个结点的度为2，其余度为1。 含n个结点的完全三叉树的高度为多少？ 完全二叉树第7层有10个叶子，问该二叉树共有多少个结点？ 一、 二叉树的顺序存储表示 （适合存储完全二叉树） 即用一组地址连续的存储单元集资从上至下，从左至右存储完全二叉树上的结点元素 。也就是说，将完全二叉树上编号为i的结点存放在数组下标为（i-1)的分量中。 若要存储一棵一般的二叉树，结点的存放应与完全二叉树上的结点对照，存储在数组的相应分量中。用“0”表示不存在该结点。可能会浪费很多存储空间，单支树就是一个极端情况。 数组表示 3建立二叉树的存储结构 不同的定义方法相应有不同的存储结构的建立算法 证明：在含有n个结点的二叉树中，含有n+1个空指针。 Proof: 设二叉树中度为0、1、2的结点数分别为n0,n1,n2，即n= n0+n1+n2 由于二叉树中的空指针数=2 n0+n1+0 =n0+ n0+n1 由性质3知： n0=n2+1 所以空指针数= n2+1+ n0+n1=n+1 证毕。 6.5线索二叉树 何谓线索二叉树？ 线索链表的遍历算法 如何建立线索链表？ 6.8 哈 夫 曼 树 与 哈 夫 曼 编 码 几个预备概念 最优树的定义 如何构造最优树 前缀编码 几个概念 路径：树中一个结点到另一个结点所经过的分支。 路径长度：路径上的分支数目。 树的路径长度：从根到每一个结点的路径长度之和。（完全二叉树是路径长度最短的二叉树） 有八种字符：a b c d e f g h ，其在通信联络中出现的概率分别为：0.05 0.29 0.07 0.08 0.14 0.23 0.03 0.11 ,试设计哈夫曼遍码。 设权 w = ( 5 , 29 , 7 ,8 , 14 , 23 ,3 , 11) n = 8 构造过程： 作业 以数据集{2，5，7，9，13}为权值构造一棵huffman树，并计算其带权路径长度。 习题集P41 6.26 （仅使用0 1 编码方案） 按层次遍历二叉树（二叉链表） 分析： 使用一个队列，先将二叉树根结点入队列，然后出队，并输出该结点。若它有左孩子则左孩子入队；若有右孩子则右孩子入队，然后分别出队，直到队列为空。 #define MAXSIZE 100 struct queue { bitree v[MAXSIZE] ; int front ,rear ; //队头、队尾指针 }q; void levelorder( bitree t) { q.front = q.rear = 0; //初始化空队列 if (t!=NULL ) printf(“ %d” ,t-data) ; //遍历根结点 q.v[q.rear]= t ; q.rear = q. rear +1 ; //结点指针入队 while ( q.front q.rear ) //队列不空 { s=q.v[q.front ] ; q.front = q.front ; //队头出队 if( s-lchild!=NULL ) //遍历左孩子 { printf(“ %d” ,s-lchile-data) ; q.v[q.rear ]=s-lchild; q.rear = q.rear +1; } if( s-rchild!=NULL ) //遍历右孩子 { printf(“ %d” ,s-rchil