当然，本题也可以设置一个全局变量 Num，每遍历到一个结点时，判断每个结点是否为分支结点（左右结点都不为空，注意是双分支），若是，则 Num++。
## 06. 【解答】
采用递归算法实现交换二叉树的左右子树，首先交换 b 结点的左孩子的左右子树，然后交换 b 结点的右孩子的左右子树，最后交换 b 结点的左右孩子，当结点为空时递归结束（后序遍历的思想）。算法实现如下：
本题实质上就是一个遍历算法的实现，只不过用一个全局变量来记录访问的序号，求其他遍历序列的第 k 个结点也采用相似的方法。二叉树的遍历算法可以引申出大量的算法题，因此考生务必要熟练掌握二叉树的遍历算法。
## 08. 【解答】
删除以元素值 x 为根的子树，只要能删除其左右子树，就可以释放值为 x 的根结点，因此宜采用后序遍历。算法思想：删除值为 x 的结点，意味着应将其父结点的左（右）孩子指针置空，用层次遍历易于找到某结点的父结点。本题要求删除树中每个元素值为 x 的结点的子树，因此要遍历完整棵二叉树。算法实现如下：
voidDeleteXTree(BiTree&bt){//删除以 bt 为根的子树if(bt){DeleteXTree(bt->lchild);DeleteXTree(bt->rchild);//删除 bt 的左子树、右子树free(bt);//释放被删结点所占的存储空间}}//在二叉树上查找所有以 x 为元素值的结点，并删除以其为根的子树voidSearch(BiTreebt,ElemTypex){BiTreeQ[];//Q 是存放二叉树结点指针的队列，容量足够大if(bt){if(bt->data==x){//若根结点值为 x，则删除整棵树DeleteXTree(bt);exit(0);}InitQueue(Q);EnQueue(Q,bt);while(!IsEmpty(Q)){DeQueue(Q,p);if(p->lchild)//若左孩子非空if(p->lchild->data==x){//左子树符合则删除左子树DeleteXTree(p->lchild);p->lchild=NULL;}//父结点的左孩子置空elseEnQueue(Q,p->lchild);//左子树入队列if(p->rchild)//若右孩子非空if(p->rchild->data==x){//右孩子符合则删除右子树DeleteXTree(p->rchild);p->rchild=NULL;}//父结点的右孩子置空elseEnQueue(Q,p->rchild);//右孩子入队列}}
typedefstruct{BiTreet;inttag;}stack;//tag=0 表示左孩子被访问，tag=1 表示右孩子被访问voidSearch(BiTreebt,ElemTypex){//在二叉树 bt 中，查找值为 x 的结点，并打印其所有祖先stacks[];//栈容量足够大top=0;while(bt!=NULL||top>0){while(bt!=NULL&&bt->data!=x){s[++top].t=bt;s[top].tag=0;bt=bt->lchild;}//沿左分支向下}if(bt!=NULL&&bt->data==x){printf("所查结点的所有祖先结点的值为:\n");//找到 xfor(i=1;i<=top;i++)printf("%d",s[i].t->data);//输出祖先值后结束exit(1);}while(top!=0&&s[top].tag==1)top--;if(top!=0){s[top].tag=1;bt=s[top].t->rchild;}//沿右分支向下遍历}}//while (bt != NULL || top > 0)}
因为查找的过程就是后序遍历的过程，所以使用的栈的深度不超过树的深度。
## 10. 【解答】
后序遍历最后访问根结点，即在递归算法中，根是压在栈底的。本题要找 p 和 q 的最近公共祖先结点 r，不失一般性，设 p 在 q 的左边。算法思想：采用后序非递归算法，栈中存放二叉树结点的指针，当访问到某结点时，栈中所有元素均为该结点的祖先。后序遍历必然先遍历到结点 p，栈中元素均为 p 的祖先。先将栈复制到另一辅助栈中。继续遍历到结点 q 时，将栈中元素从栈顶开始逐个到辅助栈中去匹配，第一个匹配（相等）的元素就是结点 p 和 q 的最近公共祖先。算法实现如下：
typedefstruct{BiTreet;inttag;//tag=0 表示左孩子已被访问，tag=1 表示右孩子已被访问}stack;stacks[],s1[];//栈，容量足够大BiTreeAncestor(BiTreeROOT,BiTNode*p,BiTNode*q){//本算法求二叉树中 p 和 q 指向结点的最近公共结点top=0;bt=ROOT;while(bt!=NULL||top&gt;0){while(bt!=NULL){s[++top].t=bt;s[top].tag=0;bt=bt-&gt;lchild;}//沿左分支向下while(top!=0&amp;&amp;s[top].tag==1){//假定 p 在 q 的左侧，遇到 p 时，栈中元素均为 p 的祖先if(s[top].t==p){for(i=1;i&lt;=top;i++)}<!--page:175-->第5章树与二叉树163```cs1[i]=s[i];top1=top;}//将栈s的元素转入辅助栈s1保存if(s[top].t==q)for(i=top;i&gt;0;i--){//将栈中元素的树结点到s1中去匹配for(j=top1;j&gt;0;j--)if(s1[j].t==s[i].t)returns[i].t;//p和q的最近公共祖先已找到}top--;//退栈}//whileif(top!=0){s[top].tag=1;bt=s[top].t-&gt;rchild;}//沿右分支向下遍历}//whilereturnNULL;//p和q无公共祖先