第5章树和二叉树--2.ppt

§6.3 遍历二叉树 6.3.1 先序、中序和后序遍历 6.3.2 算术表达式的二叉树表示 6.3.3 二叉树的运算举例 6.3.4 按层次遍历二叉树 6.3.5 创建二叉链表 举例1. 计算二叉树中的结点数： 方法一： int Number(BiTree bt){ //二叉树结点数＝1+左子树结点数+右子树结点数 if(!bt) return 0; //空二叉树，没有结点 else { nl=Number(bt-lchild);//计算左子树结点数 nr=Number(bt-rchild);//计算右子树结点数 return 1+nl+nr; } } 计算二叉树中的结点数之方法二： void Number(BiTree bt, int n) { //通过变参传递累加器n的值，n在传入时应赋初值0 if(!bt) return; n++; //累加结点数 Number(bt-lchild, n); Number(bt-rchild, n); } 计算二叉树中的结点数之方法三： void Number(BiTree bt) { //通过全局变量n传递累加器的值，n的初值为0 if(!bt) return; n++; //n是全局变量 Number(bt-lchild); Number(bt-rchild); } 举例2，计算二叉树中叶子的数目： 方法一： int Leafs(BiTree bt) { //叶子数＝左子树叶子数+右子树叶子数 if(!bt) return 0; //空二叉树 if(！bt-lchild ！bt-rchild) return 1; //树叶 LL=Leafs(bt-lchild); //计算左子树的叶子数 LR=Leafs(bt-rchild); //计算右子树的叶子数 return LL+LR; } 计算二叉树中叶子的数目之方法二： void Leafs(BiTree bt，int n){ //在对二叉树的遍历过程中对叶子数计数, n的初值为0 if(!bt) return ; if(!bt-lchild !bt-rchild) n++; //叶子 Leafs(bt-lchild, n); Leafs(bt-rchild, n); } 举例3，计算二叉树的深度： 方法一： int Height(BiTree bt) { //H=1+Max(左子树深度，右子树深度) if(!bt) return 0; hl=Height(bt-lchild); //计算bt的左子树深度 hr=Height(bt-rchild); //计算bt的右子树深度 return 1+(hlhr ? hl:hr) } 举例3，计算二叉树的深度： 方法二(P124算法6.4)： void Height(BiTree bt, int h, int depth){ //h为当前结点的层次值，h的初值为1； //depth为当前求得的最大深度，depth的初值为0 if(bt){ if(hdepth) depth=h; Height(bt-lchild,h+1,depth);//遍历左子树 Height(bt-rchild,h+1,depth);//遍历右子树 }//end if }//Height 举例4，互换二叉树的左右子树： 方法一： void Exchange(BiTree bt) { if(!bt)return; bt-lchild?bt-rchild; //互换bt的左右子树 Exchange(bt-lchild); Exchange(bt-rchild); } 互换二叉树的左右子树之方法二： void Exchange(BiTree bt) { if(!bt)return; Exchange(bt-lchild); Exchange(bt-rchild); bt-lchild?bt-rchild; //互换bt的左右子树 } 互换二叉树的左右子树之方法三： void Exchange(BiTree bt){ if