第六章樹和二叉樹題解

2019-11-17 05:36:29

字體：大中小

來源：轉載

供稿：網友

　　　　　　　　　　　　　　　　　　　　第六章樹和二叉樹
6.33
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 */
6.34
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 */
6.35
這一題根本不需要寫什么算法,見書后注釋:兩個整數的值是相等的.
6.36
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 */
6.37
void PReOrder_Nonrecursive(Bitree T)/*先序遍歷二叉樹的非遞歸算法*/
{
InitStack(S);
Push(S,T); /*根指針進棧*/
while(!StackEmpty(S))
{
    while(Gettop(S,p)&&p)
    {
      visit(p->data);
      push(S,p->lchild);
    } /*向左走到盡頭*/
    pop(S,p);
    if(!StackEmpty(S))
    {
     pop(S,p);
     push(S,p->rchild); /*向右一步*/
    }
}/*while*/
}/*PreOrder_Nonrecursive */
6.38
typedef strUCt {
                     BTNode* ptr;
                     enum {0,1,2} mark;
                   } PMType; /*有mark域的結點指針類型 */
void PostOrder_Stack(BiTree T)/*后續遍歷二叉樹的非遞歸算法,用棧*/
{
PMType a;
InitStack(S); /*S的元素為PMType類型*/
Push (S,{T,0}); /*根結點入棧*/
while(!StackEmpty(S))
{
    Pop(S,a);
    switch(a.mark)
    {
      case 0:
        Push(S,{a.ptr,1}); /*修改mark域*/
        if(a.ptr->lchild) Push(S,{a.ptr->lchild,0}); /*訪問左子樹*/
        break;
      case 1:
        Push(S,{a.ptr,2}); /*修改mark域*/
        if(a.ptr->rchild) Push(S,{a.ptr->rchild,0}); /*訪問右子樹*/
        break;
      case 2:
        visit(a.ptr); /*訪問結點,返回*/
    }
}/*while*/
}//PostOrder_Stack
分析:為了區分兩次過棧的不同處理方式,在堆棧中增加一個mark域,mark=0表示剛剛訪問此結點,mark=1表示左子樹處理結束返回,mark=2表示右子樹處理結束返回.每次根據棧頂元素的mark域值決定做何種動作.
6.39
typedef struct {
                     int data;
                     EBTNode *lchild;
                     EBTNode *rchild;
                     EBTNode *parent;
                     enum {0,1,2} mark;
                  } EBTNode,EBitree; /*有mark域和雙親指針域的二叉樹結點類型 */
void PostOrder_Nonrecursive(EBitree T)/*后序遍歷二叉樹的非遞歸算法,不用棧*/
{
p=T;
while(p)
    switch(p->mark)
    {
      case 0:
        p->mark=1;
        if(p->lchild) p=p->lchild; /*訪問左子樹*/
        break;
      case 1:
        p->mark=2;
        if(p->rchild) p=p->rchild; /*訪問右子樹*/
        break;
      case 2:
        visit(p);
        p->mark=0; /*恢復mark值*/
        p=p->parent; /*返回雙親結點*/
    }
}/*PostOrder_Nonrecursive*/
分析:本題思路與上一題完全相同,只不過結點的mark值是儲存在結點中的,而不是暫存在堆棧中,所以訪問完畢后要將mark域恢復為0,以備下一次遍歷.
6.40
typedef struct {
                     int data;
                     PBTNode *lchild;
                     PBTNode *rchild;
                     PBTNode *parent;
                   } PBTNode,PBitree; /*有雙親指針域的二叉樹結點類型 */
void Inorder_Nonrecursive(PBitree T)/*不設棧非遞歸遍歷有雙親指針的二叉樹*/
{
p=T;
while(p->lchild) p=p->lchild; /*向左走到盡頭*/
while(p)
{
    visit(p);
    if(p->rchild) /*尋找中序后繼:當有右子樹時*/
    {
      p=p->rchild;
      while(p->lchild) p=p->lchild; /*后繼就是在右子樹中向左走到盡頭*/
    }
    else if(p->parent->lchild==p) p=p->parent; /*當自己是雙親的左孩子時后繼就是雙親*/
    else
    {
      p=p->parent;
      while(p->parent&&p->parent->rchild==p) p=p->parent;
      p=p->parent;
    } /*當自己是雙親的右孩子時后繼就是向上返回直到碰到自己是在其左子樹中的祖先*/
}/*while*/
}/*Inorder_Nonrecursive */
6.41
int c,k; /*這里把k和計數器c作為全局變量處理 */
void Get_PreSeq(Bitree T)/*求先序序列為k的結點的值*/
{
if(T)
{
    c++; /*每訪問一個子樹的根都會使前序序號計數器加1*/
    if(c==k)
    {
      printf("Value is %d/n",T->data);
      exit (1);
    }
    else
    {
      Get_PreSeq(T->lchild); /*在左子樹中查找*/
      Get_PreSeq(T->rchild); /*在右子樹中

上一篇：第九章　查找　題解

下一篇：點陣的漢字程序