第6章 树和二叉树.doc

第6章树和二叉树

[问题]
假设一棵二叉树的先序序列为EBADCFHGIKJ和中序序列为ABCDEFGHIJK。请画出该树。
[解答] 
E
 
B F
 
A D H
 
C G I
 
K
 
J

[问题]
假设一棵二叉树的层序序列为ABCDEFGHIJ和中序序列为DBGEHJACIF。请画出该树。
 
A
 
B C
 
D E F
 
G H I
 
J

[问题]
试利用栈的基本操作写出先序遍历二叉树的非递归算法。
[解答提示]
-。
将if (!visit(p->data)) return ERROR;提前。
 

[问题]
编写递归算法,将二叉树中所有结点的左、右子树相互交换。
Status Exchange-lr(Bitree bt){
//将bt所指二叉树中所有结点的左、右子树相互交换
if (bt && (bt->lchild || bt->rchild)) {
bt->lchild<->bt->rchild;
Exchange-lr(bt->lchild);
Exchange-lr(bt->rchild);
}
return OK;
}//Exchange-lr
 

[问题]
编写递归算法,对于二叉树中每一个元素值为x的结点,删去以它为根的子树,并释放相应的空间。
[解答]
Status Del-subtree(Bitree bt){
//删除bt所指二叉树,并释放相应的空间
if (bt) {
Del-subtree(bt->lchild);
Del-subtree(bt->rchild);
free(bt);
}
return OK;
}//Del-subtree
 
Status Search-del(Bitree bt, TelemType x){
//在bt所指的二叉树中,查找所有元素值为x的结点,并删除以它为根的子树
if (bt){
if (bt->data=x) Del-subtree(bt);
else {
Search-Del(bt->lchild, x);
Search-Del(bt->rchild, x);
}
}
return OK;
}//Search-Del
 
第六章树和二叉树

int Is_Descendant_C(int u,int v)//在孩子存储结构上判断u是否v的子孙,是则返回1,否则返回0
{
  if(u==v) return 1;
  else
  {
    if(L[v])
      if (Is_Descendant(u,L[v])) return 1;
    if(R[v])
      if (Is_Descendant(u,R[v])) return 1; //这是个递归算法
  }
  return 0;
}//Is_Descendant_C

int Is_Descendant_P(int u,int v)//在双亲存储结构上判断u是否v的子孙,是则返回1,否则返回0
{
  for(p=u;p!=v&&p;p=T[p]);
  if(p==v) return 1;
  else return 0;
}//Is_Descendant_P

这一题根本不需要写什么算法,见书后注释:两个整数的值是相等的.

int Bitree_Sim(Bitree B1,Bitree B2)//判断两棵树是否相似的递归算法
{
  if(!B1&&!B2) return 1;
  else if(B1&&B2&&Bitree_Sim(B1->lchild,B2->lchild)&&Bitree_Sim(B1->rchild,B2->rchild))
    return 1;
  else return 0;
}//Bitree_Sim

void PreOrder_NotRecurve(Bitree T)//先序遍历二叉树的非递归算法
{
  InitStack(S);
  Push(S,T); //根指针进栈
  while(!StackEmpty(S))
  {
    while(Gettop(S,p)&&p)
    {
      visit(p->data);
      push(S,p->lchild);
    } //