哈夫曼树及应用(补充).ppt

* * { if(p= =r) /*找到r所指结点，则显示从根结点到r所指结点之间的路径*/ { for(i=1;i=top;i++) printf(“%d”,s[i ]-data); top=0; /* 强制退出循环 */ } else { q = p; /* 用q保存刚遍历过的结点 */ top--; p = NULL; /* 跳过前面左遍历，继续退栈 */ } } else p = p - RChild; /* 遍历右子树 */ } } } * * 例3 层次遍历二叉树 层次遍历是指从二叉树的第一层（根结点）开始，从上至下逐层遍历，在同一层中，则按照从左到右的顺序对结点逐个访问。以此类推，直到二叉树中所有结点均被访问且仅访问一次。 【问题分析】实现层次遍历，需要设置一个队列Q,暂存某层已访问过的结点，同时也保存了该层结点访问的先后次序。按照对该层结点访问的先后次序实现对其下层孩子结点的按次序访问。 【算法思想】 （1）初始化空队列Q; （2）若二叉树bt为空树，则直接返回； （3）将二叉树的根结点指针bt放入队列Q； （4）若队列非空，则重复如下操作： ①队头元素出队并访问该元素； ②若该结点的左孩子非空，则将该结点的左孩子结点指针入队； ③若该结点的右孩子非空，则将该结点的右孩子结点指针入队； * * 【算法描述】 int LayerOrder(BiTree bt) /*层次遍历二叉树bt*/ { SeqQueue * Q; BiTree p; InitQueue（Q）； /*初始化空队列Q*/ if(bt= =NULL) return ERROR; /* 若二叉树bt为空树，则结束遍历*/ EnterQueue(Q, bt); /* 若二叉树bt非空，则根结点bt入队，开始层次遍历*/ while (!IsEmpty(Q)) /*若队列非空，则遍历未结束，继续进行*/ { DeleteQueue(Q, p); /*队头元素出队并访问 */ visit(p-data); if(p- LChild ) EnterQueue(Q, p- LChild) ; /*若p的左孩子非空，则进队*/ if(p- RChild ) EnterQueue(Q, p- RChild) ; /*若p的右孩子非空，则进队*/ } /*while*/ return OK; } /* LayerOrder */ 构造二叉树 给定一棵二叉树的先序序列和中序序列，可唯一确定一棵二叉树 例：已知结点的先序遍历序列和中序遍历序列分别为： 先序遍历序列：18，14，7，3，11，22，35，27 中序遍历序列：3，7，11，14，18，22，27，35 18 14 7 3 11 22 35 27 1、对二叉树从1开始编号，要求每个结点的编号大于其左右孩子的编号，同一个结点的左右孩子中，其左孩子的编号小于其右孩子的编号，则可采用（ ）实现编号。 A）先序遍历 B）中序遍历 C）后序遍历 D）从根开始进行层次遍历 2、某二叉树的先序序列和后序序列正好相反，则该二叉树一定是（ ）的二叉树。 A）空或只有一个结点 B）高度等于其结点数 C）任一结点无左孩子 D）任一结点无右孩子 3、有n个叶子结点的哈夫曼树的结点总数为（ ） A）不确定 B）2n C）2n＋1 D）2n－1 C B D 4、除根结点外，树上每个结点（ ）。 A）可有任意多个孩子、任意多个双亲 B）可有任意多个孩子、一个双亲 C）可有一个孩子、任意多个双亲 D）可有一个孩子、一个双亲 5、树用双亲链表表示，则（ ）。 A）可容易地实现求双亲及子孙的运算 B）求双亲及子孙的运算均较困难 C）可容易地实现求双亲运算，但求子孙运算较困难 D）可容易地实现求子孙运算，但求双亲运算较困难 B C 6、若对一棵有16个结点地完全二叉树按层编号，则对于编号为7的结点x，它的双亲结点及右孩子结点的编号分别为（ ）。 A）2，14 B）2，15 C）3，14 D）3，15 7、如右图所示的二叉树， （1）其中序遍历序列为： （2）其先序遍历序列为： （3）其后序遍历序列为： （4）该二叉树的中序线索二叉树为： （5）该二叉树对应的森林为： D a b c d e f j h i * 例2：哈夫曼树用于电文编码 要传输的电文是{CAS；CAT；SAT；AT} 要传输的字符集是 D={C，A，S，T，