计算机数据结构第六章 树和二叉树.ppt

第六章 树和二叉树 例3：设计一个将百分成绩转换为等级制的算法，具体要求如下： A：90～100；B：80～89；C：70～79 D：60～69；E：0～59 6.1.2 树的抽象数据类型定义 ADT Tree｛ 数据对象D：D是具有相同特性的数据元素的集合。 数据关系R：若D为空集，则称为空树; 若D仅含一个数据元素，则R为空集，否则R＝{H}，H是如下二元关系： 在D中存在唯一的称为根的数据元素root，它在关系H下无前驱； 若D－｛root｝≠φ，则存在D－｛root｝的一个划分D1, D2, ..., Dm （m＞0），对任意j≠k（1≤j,k≤m）有Dj∩Dk=φ ，且对任意的i（1≤i≤m），唯一存在数据元素xi?Di，有root,xi? H; 对应于D－｛root｝的划分，H－｛root,x1，....，root,xm｝有唯一的一个划分H1 , H2 ,..., Hm （m＞0），对任意j≠k（1≤j,k≤m）有Hj∩Hk=φ ，且对任意的i（1≤i≤m），Hi 是Di上的二元关系，（Di ,{Hi}）是一棵符合本定义的树，称为根root的子树。 树的其它表示形式 树的表示形式还有其它多种方法，如： （1） 嵌套集合法; （2） 凹入法。 等 6.2 二叉树（Binary Tree） 链式存储示例 6.3 遍历二叉树 和线索二叉树 二叉树遍历方式： 二叉树的非递归算法 建立二叉树算法 其它遍历算法-层次遍历 按层次（同一层从左至右）遍历二叉树的算法： void LayerOrder(Bitree T)//层序遍历二叉树 {??InitQueue(Q); ?? EnQueue(Q,T); ??while(!QueueEmpty(Q)) { ????DeQueue(Q,p); ?visit(p); ????if(p-lchild) EnQueue(Q,p-lchild); ?if(p-rchild) EnQueue(Q,p-rchild); ?} } 作业： 6.3.2 线索二叉树 问题的提出：通过遍历二叉树可得到结点的一个线性序列，在线性序列中，就存在结点和前驱和后继，但是在二叉树上只能找到结点的左孩子、右孩子，结点的前驱和后继只有在遍历过程中动态得到，那么，能否通过结点的两个链域查找出任一结点的前驱和后继? 想法： 我们知道，在二叉链表中有n+1个空链域， 因此, 可以用空链域来存放结点的前驱和后继。 线索二叉树就是利用n+1个空链域来存放结点的前驱和后继结点的信息。 如何构建线索二叉树： ⑴ 结点结构 在二叉链表中增加 ltag 和 rtag 两个标志域 称这种结点结构为线索链表； 其中指示前驱和后继的链域称为线索； 加上线索的二叉树称为线索二叉树； 对二叉树以某种次序遍历使其变为线索二叉树的过程称为线索化。 按中序遍历得到的线索二叉树称为中序线索二叉树；按先序遍历得到的线索二叉树称为先序线索二叉树；按后序遍历得到的线索二叉树称为后序线索二叉树； 作业： 线索二叉树算法的实现。 6.4 树和森林 2. 森林转换成二叉树 6.6 赫夫曼树 及其应用 Huffman树 引例：已知某系统在通信联络中只可能出现8种字符，其概率如下表所示: 赫夫曼编码的求解算法 typedef struct { char ch; unsigned int weight; unsigned int parent,lchild,rchild; }HTNode,*Huffmantree; Huffmantree HT; HT = new HTNode[2*n];//赫夫曼树的存储结构 或： HT = (HuffmanTree)malloc(2n*sizeof(HTNode)); void HuffmanCoding(HuffmanTree HT,HuffmanCode HC,int *w,int n) {//w存放n个字符的权值，构造赫夫曼树HT，并求出n个字符的编码 if (n=1) return; m = 2*n-1; //Huffman树结点数 HT = (HuffmanTree)malloc((m+1)*sizeof(HTNode)); //开辟空间 for(i=1; i=n; i++) {//叶子结点赋值 HT[i].weight = w[i-1]; HT[i].parent = 0; HT[i].lc