print（bt->data）;
PrintBinaryTree（bt->lchild,level+1）;
}
0.5编写算法判断二叉树是否是完全二叉树。
分析：
按层遍历完全二叉树，当遇到第一个空指针之后应该全都是空指针。
boolIsComplete（BinTreebt）
{
//按层遍历至第一个空指针
InitQueue（Q）;
EnQueue（Q,bt）;
while（!
QueueEmpty（Q））{
DeQueue（Q,p）;
if（p）{
EnQueue（Q,p->lchild）;
EnQueue（Q,p->rchild）;
}else
break;//遇到第一个空指针时停止遍历
}
//检查队列中剩余元素是否全部是空指针
while（!
QueueEmpty（Q））{
DeQueue（Q,p）;
if（!
p）returnfalse;//不是完全二叉树
}
returntrue;//完全二叉树
}
0.6编写算法求二叉树中给定结点的所有祖先。
分析：
进行后序遍历时，栈中保存的是当前结点的所有祖先。
所以，后序遍历二叉树，遇到该结点时，取出栈中的内容即是所有祖先。
//求二叉树bt中结点xptr的所有祖先
vectorAncestors（BinTreebt,BinTreexptr）
{
stacks;stacktag;
p=bt;
while（p||!
s.empty（））{
if（p）{
s.push（p）;tag.push
（1）;
p=p->lchild;
}else{
p=s.pop（）;f=tag.pop（）;
if（f==1）{
s.push（p）;tag.push
（2）;
p=p->rchild;
}else{
if（p==xptr）{
v=s;//当前栈的内容就是xptr的所有祖先
returnv;
}
p=NULL;
}
}
}//while
returnvector（）;//returnanullvector
}
注：
这里为描述方便借助了C++中的某些描述方式。
0.7编写算法求二叉树中两个结点的最近的共同祖先。
思路：
用后序遍历求出两者的所有祖先，依次比较。
//求二叉树bt中两个结点q和r的最近的共同祖先
BinTreeLastAncestor（BinTreebt,BinTreeq,BinTreer）
{
stacksq,sr;
stacks;stacktag;
//求q和r的所有祖先
p=bt;
while（p||!
s.empty（））{
if（p）{
s.push（p）;tag.push
（1）;
p=p->lchild;
}else{
p=s.pop（）;f=tag.pop（）;
if（f==1）{
s.push（p）;tag.push
（2）;
p=p->rchild;
}else{
if（p==q）sq=s;//q的所有祖先
if（p==r）sr=s;//s的所有祖先
p=NULL;
}
}
}
//先跳过不同层的祖先，然后依次比较同一层的祖先
if（sq.size（）>sr.size（））while（sq.size（）>sr.size（））sq.pop（）;
elsewhile（sr.size（）>sq.size（））sr.pop（）;
//求q和r的最近的共同祖先
while（!
sq.empty（）and（sq.top（）!
=sr.top（）））{//寻找共同祖先
sq.pop（）;sr.pop（）;
}
if（!
sq.empty（））
returnsq.top（）;
else
returnNULL;
}
0.8编写算法输出以二叉树表示的算术表达式（中缀形式），要求在必要的地方输出括号。
分析：
当左孩子的优先级低于根时需要加括号，根的优先级大于右孩子时也需要加括号。
voidPrintExpression（BinTreebt）
{
if（bt==NULL）return;
if（bt->lchild==NULLandbt->rchild==NULL）
print（bt->data）;//叶子结点直接打印
else{
//左子树
brackets=bt->lchildandis_operator（bt->lchild->data）
andcomp_operator（bt->lchild->data,bt->data）<0;//左孩子优先级低于根
if（brackets）print（“（“）;
PrintExpression（bt->lchild）;
if（brackets）print（“）”）;
//根结点
print（bt->data）;
//右子树
brackets=bt->rchildandis_operator（bt->lchild->data）
andcomp_operator（bt->data,bt->rchild->data）>0;//根的优先级大于右孩子
if（brackets）print（“（“）;
PrintExpression（bt->rchild）;
if（brackets）print（“）“）;
}
}
注：
is_operator（c）判断c是否是运算符；comp_operator（a,b）比较两个运算符的优先级。
boolis_operator（charc）{//判断c是否是运算符
returnc=='+'||c=='-'||c=='*'||c=='/';
}
intcomp_operator（charopl,charopr）{//比较两个运算符的优先级
return（opl=='*'||opl=='/'||opr=='+'||opr=='-'）?
+1:
-1;
}
0.9树采用孩子-兄弟链表存储，编写算法求树中叶子结点的个数。
分析：
树中的叶子没有孩子，即firstchild为空。
//求树t中叶子结点的个数
intLeafCount（CSTreet）
{
if（t==NULL）return0;//空树
if（t->firstchild==NULL）//没有孩子
return1+LeafCount（t->nextsibling）;
else
returnLeafCount（t->firstchild）+LeafCount（t->nextsibling）;
}
0.10采用孩子-兄弟链表存储树，编写算法求树的度。
分析：
度最大的结点的度数。
intDegree（CSTreet）
{
if（t==NULL）return0;
else
returnmax（Degree（t->firstchild）,1+Degree（t->nextsibling））;
}
0.11采用孩子-兄弟链表存储树，编写算法求树的深度。
intDepth（CSTreet）
{
if（t==NULL）return0;
else{
depchild=Depth（t->firstchild）;//孩子的深度
depsibling=Depth（t->nextsibling）;//兄弟的深度
returnmax（depchild+1,depsibling）;//取较大者
}
}
0.12已知二叉树的前序和中序序列，编写算法建立该二叉树。
分析：
划分先序序列a=（D,（L）,（R））和后序序列b=（（L）,D,（R）），然后对子序列（L）和（R）递归。
//根据先序序列a[si..ti]和中序序列b[sj..tj]构造二叉树
BinTreeCreateBinaryTree（Ta[],intsi,intti,Tb[],intsj,inttj）
{
if（n<=0）return0;//空树
//建立根结点
p=newBinNode（a[si]）;//以a[si]为数据域建立新结点
//根据根结点划分中序序列为b[sj..k-1]和b[k+1..tj]
k=sj;
while（b[k]!
=a[si]）k++;//在b[]中搜索根结点a[si]
//建立左右子树
p->lchild=CreateBinaryTree（a,si+1,si+k-sj,b,sj,k-1）;//建立左子树
p->rchild=CreateBinaryTree（a,si+k-sj+1,b,k+1,tj）;//建立右子树
returnp;
}
0.13树T的先根遍历序列为GFKDAIEBCHJ，后根遍历序列为DIAEKFCJHBG，
升级会员 