第六章-树.pptVIP

5、建立二叉树的存储结构 不同的数据输入的方法相应有不同的存储结构的建立算法 6.3.2线索二叉树 何谓线索二叉树？ 线索链表的遍历算法 如何建立线索链表？ 6.6 赫夫曼树及其应用 最优树的定义 如何构造最优树 赫夫曼编码 由森林转换成二叉树的转换规则为: 若 F = Φ，则 B = Φ; 由 ROOT( T1 ) 对应得到Node(root); 否则， 由 (t11, t12, …, t1m ) 对应得到 LBT; 由 (T2, T3,…, Tn ) 对应得到 RBT。 T1 T11,T12,…,T1m T2,…,Tn LBT RBT root 由此，树和森林的各种操作均可与二叉树的各种操作相对应。 应当注意的是，和树对应的二叉树，其左、右子树的概念 已改变为： 左是孩子，右是兄弟 四、中序遍历算法的非递归描述 Status InOrder_iter( BiTree T, Status (*visit)(TElemType e)){ // 利用栈实现中序遍历二叉树，T为指向二叉树的根结点的指针 InitStack(S); Push（S，T）；//根指针进栈 while(!StackEmpty(S)) { while(GetTop(S,p) p ) Push(S,p-lchild);//向左走到尽头 Pop(S,p); // 空指针退栈 if (！StackEmpty（S））{ // 访问结点，向右一步 Pop(S,p); if(!Visit(p-data)) return ERROR; Push(S,p-rchild); }//if } //while return OK; }//InOrder_iter 五、遍历算法的应用举例 2、统计二叉树中叶子结点的个数 3、求二叉树的深度(后序遍历) 4、复制二叉树(后序遍历) 5、建立二叉树的存储结构 1、查询二叉树中某个结点 6、用二叉树表示表达式 1）. 在二叉树不空的前提下,和根结点的元素进行比较,若相等,则找到返回 TRUE; 2）.否则在左子树中进行查找,若找到,则返回 TRUE; 3). 否则继续在右子树中进行查找,若找到,则返回 TRUE,否则返回 FALSE; 1、查询二叉树中某个结点 Status Preorder (BiTree T, ElemType x, BiTree p) { // 若二叉树中存在和 x 相同的元素，则 p 指向该结点并返回 OK, // 否则返回 FALSE } if (T) { }//if else return FALSE; if (T-data==x) { p = T; return OK,} else { if ( Preorder(T-lchild, x, p) ) return OK; else return( Preorder(T-rchild, x, p) ) ; }//else 2、统计二叉树中叶子结点的个数 算法基本思想: 先序(或中序或后序)遍历二叉树，在遍历过程中查找叶子结点，并计数。 由此，需在遍历算法中增添一个“计数”的参数，并将算法中“访问结点” 的操作改为:若是叶子，则计数器增1。 void CountLeaf (BiTree T, int count){ if ( T ) { if ((!T-lchild) (!T-rchild)) count++; // 对叶子结点计数 CountLeaf( T-lchild, count); CountLeaf( T-rchild, count); } // if } // CountLeaf int CountLeaf (BiTree T){ //返回指针T所指二叉树中所有叶子结点个数 if (!T ) return 0; if (!T-lchild !T-rchild) return 1; else{ m = CountLeaf( T-lchild); n = CountLeaf( T-rchild); return (m+n); } //else } // CountLeaf 3、求二叉树的深度(后序遍历) 算法基本思想: 从二叉树深度的定义可知，二叉树的深度应为其左、右子树深度的最大值加1。由此，需先分别求