树和二叉树 北京师范大学.ppt

导航图(2) 树与二叉树 树的基本概念 二叉树 二叉树的遍历 线索化二叉树 哈夫曼树 树与森林 导航图(3) 树与二叉树 树的基本概念 二叉树 二叉树的遍历 线索化二叉树 哈夫曼树 树与森林 导航图(4) 树与二叉树 树的基本概念 二叉树 二叉树的遍历 线索化二叉树 哈夫曼树 树与森林 导航图(5) 树与二叉树 树的基本概念 二叉树 二叉树的遍历 线索化二叉树 哈夫曼树 树与森林 导航图(6) 树与二叉树 树的基本概念 二叉树 二叉树的遍历 线索化二叉树 哈夫曼树 树与森林 三、二叉树的遍历——算法(8) while(1) /*出栈处理循环*/ { if(s.elem[s.top]-rchild!=NULL) {/*如果栈顶结点右孩子不空，栈顶问题需要继续递归分解*/ p=s.elem[s.top]-rchild; /*p指向栈顶结点的右孩子*/ Push(s,p);/*问题p入栈*/ break;/*转去递归分解*/ } /*栈顶结点右孩子为空，才可以进行出栈处理，可能会将递归终点连续出栈*/ while(!IsSqstackEmpty(s)) { if(s.elem[s.top]-rchild==NULL||s.elem[s.top]-rchild==p) {/*栈顶问题是递归终点的条件：右孩子是空(一般首先遇到) 或者它的右孩子是原栈顶结点p（这个条件只有在出栈处理时才是递归终点的条件）*/ Pop(s,p); /*栈顶问题p出栈*/ sprintf(tmpstr,%c ,p-data);/*访问结点p*/ strcat(str,tmpstr); } else break;/*否则跳出弹出递归终点的循环*/ } 三、二叉树的遍历——算法(9) if(IsSqstackEmpty(s)) {/*栈空，则遍历结束*/ DestroySqstack(s); return; } }//出栈处理while(1) } } 三、二叉树的遍历——算法(10) 层序遍历 void LayerOrder(BTREE root, char *str) {/*层序遍历二叉树root,遍历结果放在str中，str一开始为空*/ char tmpstr[20]; SQQUEUE qu; BTREENODEPTR p; InitSqqueue(qu,MAXCOUNT); EnSqqueue(qu,root); /*将根结点入队*/ while(!IsSqqueueEmpty(qu)) /*只要队列不空就循环，队列空则遍历完毕*/ { DeSqqueue(qu,p);/*出队一个结点p*/ sprintf(tmpstr,%c ,p-data); strcat(str,tmpstr); /*访问结点p*/ if(p-lchild!=NULL)/*将左孩子入队*/ EnSqqueue(qu,p-lchild); if(p-rchild!=NULL) /*将左孩子入队*/ EnSqqueue(qu,p-rchild); } } 三、二叉树的遍历——算法的应用(1) 1．求二叉树的深度 int GetHeight(BTREE root) {/*返回二叉树root的深度值*/ int lh,rh; if(root==NULL)return 0; /*空树，深度是0*/ lh=GetHeight(root-lchild); /*递归调用获得左子树的深度*/ rh=GetHeight(root-rchild);/*递归调用获得右子树的深度*/ /*取左右子树深度值大者，作为子树的深度，这个树的深度是子树深度加1*/ if(lh=rh)return lh+1; else return rh+1; } 三、二叉树的遍历——算法的应用(2) 2．计算叶子结点的总数 int CountLeaf(BTREE root) {/*返回二叉树root中叶子结点总数*/ int lnum,rnum; if(root==NULL)return 0; /*空树，叶子结点个数是0*/ lnum=CountLeaf(root-lchild); /*递归调用求左子树叶子结点个数*/ rnum=CountLeaf(root-rchild);/*递归调用求右子树叶子结点个数*/ /*如果左右子树叶子的和是0，说明当前结点是叶子，返回1；否则返回左右子树叶子结点的和*/ if((lnum+rnum)==0)return 1; else return