s[top].tag=1; bt=s[top].t->rchild; ｝∥沿右分枝向下遍历 }∥结束while(bt!=null ||top>0) return(null);∥ｑ、p无公共祖先 ｝∥结束Ancestor
6.48以二叉链表作为存储结构，设计按层次遍历二叉树的算法。 【算法6.48】
void Level(BiTree bt) ∥层次遍历二叉树 {if(bt)
{QueueInit(Q); ∥Q是以二叉树结点指针为元素的队列 QueueIn(Q,bt)；
while(!QueueEmpty(Q))
{p=QueueOut(Q); ∥出队 printf(p->data); ∥访问结点 if(p->lchild) QueueIn(Q,p->lchild); ∥非空左子女入队 if(p->rchild) QueueIn(Q,p->rchild); ∥非空右子女入队 } }∥if(bt) }
6.49编写算法查找二叉链表中数据域值为x的结点（假定各结点的数据域值各不相同），并打印出x所有祖先的数据域值。
【题目分析】后序遍历最后访问根结点，当访问到值为x的结点时，栈中所有元素均为该结点的祖先。 【算法6.49】
void Search(BiTree bt,ElemType x)
∥在二叉树bt中，查找值为x的结点，并打印其所有祖先
{typedef struct {BiTree t;
int tag; ∥tag=0表示左子女被访问，tag=1右子女被访问 }stack;
stack s[]; ∥栈容量足够大 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->data==x)
{printf(“所查结点的所有祖先结点的值为:\\n”);∥找到x for(i=1;i<=top;i++) printf(s[i].t->data); return; } ∥输出祖先值后结束
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) }结束search
6.50设计这样的二叉树，用它可以表示父子、夫妻和兄弟三种关系，并编写一个查找任意父亲结点的所有儿子结点的过程。
【题目分析】用二叉树表示出父子，夫妻和兄弟三种关系，可以用根结点表示父（祖先），根结点的左子女表示妻，妻的右子女表示子。这种二叉树可以看成类似树的孩子兄弟链表表示法；根结点是父，根无右子女，左子女表示妻，妻的右子女（右子女的右子女等）均可看成兄弟（即父的所有儿子），兄弟结点又成为新的父，其左子女是兄弟（父的儿子）妻，妻的右子女（右子女的右子女等）又为儿子的儿子等等。首先递归查找某父亲结点，若查找成功，则其左子女是妻，妻的右子女及右子女的右子女等均为父亲的儿子。 【算法6.50】
BiTree Search(BiTree t,ElemType father) ∥在二叉树上查找值为father的结点 {int tag=0;
if(t==null) p=null; ∥二叉树上无father结点 else if(t->data==father) {tag=1; p=t;}∥查找成功
else{p=Search(t->lchild,father); if(tag==0)p=Search(t->rchild,father);}
return p; }∥结束Search
void PrintSons(BiTree t,ElemType x) ∥在二叉树上查找结点值为x的所有的儿子
{p=Serach(t,x); ∥在二叉树t上查找父结点x if(p && p->lchild) ∥存在父结点,且有妻
{q=p->lchild; q=q->rchild; ∥先指向其妻结点，再找到第一个儿子 while(q!=null)
{printf(q->data); q=q->rchild;}∥输出父的所有儿子 }
}∥结束PrintSons
6.51 编写递归算法判定两棵二叉树是否相等。
【题目分析】首先判断二叉树的根是否相等，如是，再判断其左、右子树是否相等。 【算法6.51】
int BTEqual(BiTree t, BiTree x) {∥判定二叉树t和二叉树x是否相等 if(!t && !x) return true;
if(t && x && t->data==x->data && BTEqual(t->lchild,x->lchild) && BTEqual(t->rchild,x->rchild) return ture;
else return false; }
6.52已知一棵高度为Ｋ具有ｎ个结点的二叉树，按顺序方式存储，编写将树中最大序号叶子结点的祖先结点全部打印输出的算法。
【题目分析】二叉树中最大序号的叶子结点,是在顺序存储方式下编号最大的结点
【算法6.52】
void Ancesstor(ElemType bt[]) ∥打印最大序号叶子结点的全部祖先 {c=m; ∥m=2K-1
while(bt[c]==0) c--;∥找最大序号叶子结点,该结点存储时在最后 f=c/2; ∥c的双亲结点f
while(f!=0) ∥从结点c的双亲结点直到根结点，路径上所有结点均为祖先结点 {printf(bt[f]); f=f/2; }∥逆序输出，最老的祖先最后输出 }∥结束
6.53设二叉树以二叉链表作为存储结构，编写算法对二叉树进行非递归的中序遍历。 【算法6.53】
void InOrder(BiTree bt) ∥对二叉树进行非递归中序遍历
{BiTree s[],p=bt; ∥s是元素为二叉树结点指针的栈，容量足够大 int top=0; while(p || top>0)
{while(p) {s[++top]=p; bt=p->lchild;} ∥沿左子树向下
if(top>0)
{p=s[top--]; printf(p->data); p=p->rchild;} ∥退栈，访问，转右子树
} }∥结束
6.54设T是一棵满二叉树，写一个把T的后序遍历序列转换为先序遍历序列的递归算法。
【题目分析】对一般二叉树，仅根据一个先序（或中序、或后序）遍历，不能确定另一个遍历序列。但由于满二叉树“任一结点的左右子树均含有数量相等的结点”，根据此性质，可将任一遍历序列转为另一遍历序列。 【算法6.54】
void PostToPre(ElemType post[],pre[],int l1,h1,l2,h2)
∥将满二叉树的后序序列转为先序序列，l1,h1,l2,h2是序列初始和最后结点的下标。 {if(h1>=l1)
{pre[l2]=post[h1]; ∥根结点 visit(pre[l2]); ∥访问根结点 half=(h1-l1)/2; ∥左或右子树的结点数 PostToPre(post,pre,l1,l1+half-1,l2+1,l2+half) ∥将左子树后序序列转为先序序列
PostToPre(post,pre,l1+half,h1-1,l2+half+1,h2) ∥将右子树后序序列转为先序序列 }
}∥ PostToPre t
6.55若二叉树BT的每个结点，其左、右子树都为空，或者其左、右子树都不空，这种二叉树有时称为“严格二叉树”。由“严格二叉树”的前序序列和后序序列可以唯一确定该二叉树。写出根据这种二叉树的前序序列和后序序列确定该二叉树的递归算法。
【问题分析】前序序列的第一个结点是二叉树的根，若该结点后再无其它结点，则该结点是叶子；否则，该结点必有左、右子树，且根结点后的第一个结点就是