嚴蔚敏《數據結構(c語言版)習題集》算法設計題第六章答案

　　第六章 樹和二叉樹

　　

　　int Is_Descendant_C(int uint v)//在孩子存儲結構上判斷u是否v的子孫是則返回否則返回

　　{

　　if(u==v) return ;

　　else

　　{

　　if(L[v])

　　if (Is_Descendant(uL[v])) return ;

　　if(R[v])

　　if (Is_Descendant(uR[v])) return ; //這是個遞歸算法

　　}

　　return ;

　　}//Is_Descendant_C

　　

　　int Is_Descendant_P(int uint v)//在雙親存儲結構上判斷u是否v的子孫是則返回否則返回

　　{

　　for(p=u;p!=v&&p;p=T[p]);

　　if(p==v) return ;

　　else return ;

　　}//Is_Descendant_P

　　

　　這一題根本不需要寫什麼算法見書後注釋:兩個整數的值是相等的

　　

　　int Bitree_Sim(Bitree BBitree B)//判斷兩棵樹是否相似的遞歸算法

　　{

　　if(!B&&!B) return ;

　　else if(B&&B&&Bitree_Sim(B>lchildB>lchild)&&Bitree_Sim(B>rchildB>rchild))

　　return ;

　　else return ;

　　}//Bitree_Sim

　　

　　void PreOrder_Nonrecursive(Bitree T)//先序遍歷二叉樹的非遞歸算法

　　{

　　InitStack(S);

　　Push(ST); //根指針進棧

　　while(!StackEmpty(S))

　　{

　　while(Gettop(Sp)&&p)

　　{

　　visit(p>data);

　　push(Sp>lchild);

　　} //向左走到盡頭

　　pop(Sp);

　　if(!StackEmpty(S))

　　{

　　pop(Sp);

　　push(Sp>rchild); //向右一步

　　}

　　}//while

　　}//PreOrder_Nonrecursive

　　

　　typedef struct {

　　BTNode* ptr;

　　enum {} mark;

　　} PMType; //有mark域的結點指針類型

　　void PostOrder_Stack(BiTree T)//後續遍歷二叉樹的非遞歸算法用棧

　　{

　　PMType a;

　　InitStack(S); //S的元素為PMType類型

　　Push (S{T}); //根結點入棧

　　while(!StackEmpty(S))

　　{

　　Pop(Sa);

　　switch(amark)

　　{

　　case :

　　Push(S{aptr}); //修改mark域

　　if(aptr>lchild) Push(S{aptr>lchild}); //訪問左子樹

　　break;

　　case :

　　Push(S{aptr}); //修改mark域

　　if(aptr>rchild) Push(S{aptr>rchild}); //訪問右子樹

　　break;

　　case :

　　visit(aptr); //訪問結點返回

　　}

　　}//while

　　}//PostOrder_Stack

　　分析:為了區分兩次過棧的不同處理方式在堆棧中增加一個mark域mark=表示剛剛訪問此結點mark=表示左子樹處理結束返回mark=表示右子樹處理結束返回每次根據棧頂元素的mark域值決定做何種動作

　　

　　typedef struct {

　　int data;

　　EBTNode *lchild;

　　EBTNode *rchild;

　　EBTNode *parent;

　　enum {} mark;

　　} EBTNodeEBitree; //有mark域和雙親指針域的二叉樹結點類型

　　void PostOrder_Nonrecursive(EBitree T)//後序遍歷二叉樹的非遞歸算法不用棧

　　{

　　p=T;

　　while(p)

　　switch(p>mark)

　　{

　　case :

　　p>mark=;

　　if(p>lchild) p=p>lchild; //訪問左子樹

　　break;

　　case :

　　p>mark=;

　　if(p>rchild) p=p>rchild; //訪問右子樹

　　break;

　　case :

　　visit(p);

　　p>mark=; //恢復mark值

　　p=p>parent; //返回雙親結點

　　}

　　}//PostOrder_Nonrecursive

　　分析:本題思路與上一題完全相同只不過結點的mark值是儲存在結點中的而不是暫存在堆棧中所以訪問完畢後要將mark域恢復為以備下一次遍歷

　　

　　typedef struct {

　　int data;

　　PBTNode *lchild;

　　PBTNode *rchild;

　　PBTNode *parent;

　　} PBTNodePBitree; //有雙親指針域的二叉樹結點類型

　　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

　　

　　int ck; //這裡把k和計數器c作為全局變量處理

　　void Get_PreSeq(Bitree T)//求先序序列為k的結點的值

　　{

　　if(T)

　　{

　　c++; //每訪問一個子樹的根都會使前序序號計數器加

　　if(c==k)

　　{

　　printf(Value is %d\nT>data);

　　exit ();

　　}

　　else

　　{

　　Get_PreSeq(T>lchild); //在左子樹中查找

　　Get_PreSeq(T>rchild); //在右子樹中查找

　　}

　　}//if

　　}//Get_PreSeq

　　main()

　　{

　　

　　scanf(%d&k);

　　c=; //在主函數中調用前要給計數器賦初值

　　Get_PreSeq(Tk);

　　

　　}//main

　　

　　int LeafCount_BiTree(Bitree T)//求二叉樹中葉子結點的數目

　　{

　　if(!T) return ; //空樹沒有葉子

　　else if(!T>lchild&&!T>rchild) return ; //葉子結點

　　else return Leaf_Count(T>lchild)+Leaf_Count(T>rchild);//左子樹的葉子數加上右子樹的葉子數

　　}//LeafCount_BiTree

　　

　　void Bitree_Revolute(Bitree T)//交換所有結點的左右子樹

　　{

　　T>lchild<>T>rchild; //交換左右子樹

　　if(T>lchild) Bitree_Revolute(T>lchild);

　　if(T>rchild) Bitree_Revolute(T>rchild); //左右子樹再分別交換各自的左右子樹

　　}//Bitree_Revolute

　　

　　int Get_Sub_Depth(Bitree Tint x)//求二叉樹中以值為x的結點為根的子樹深度

　　{

　　if(T>data==x)

　　{

　　printf(%d\nGet_Depth(T)); //找到了值為x的結點求其深度

　　exit ;

　　}

　　else

　　{

　　if(T>lchild) Get_Sub_Depth(T>lchildx);

　　if(T>rchild) Get_Sub_Depth(T>rchildx); //在左右子樹中繼續尋找

　　}

　　}//Get_Sub_Depth

　　int Get_Depth(Bitree T)//求子樹深度的遞歸算法

　　{

　　if(!T) return ;

　　else

　　{

　　m=Get_Depth(T>lchild);

　　n=Get_Depth(T>rchild);

　　return (m>n?m:n)+;

　　}

　　}//Get_Depth

　　

　　void Del_Sub_x(Bitree Tint x)//刪除所有以元素x為根的子樹

　　{

　　if(T>data==x) Del_Sub(T); //刪除該子樹

　　else

　　{

　　if(T>lchild) Del_Sub_x(T>lchildx);

　　if(T>rchild) Del_Sub_x(T>rchildx); //在左右子樹中繼續查找

　　}//else

　　}//Del_Sub_x

　　void Del_Sub(Bitree T)//刪除子樹T

　　{

　　if(T>lchild) Del_Sub(T>lchild);

　　if(T>rchild) Del_Sub(T>rchild);

　　free(T);

　　}//Del_Sub

　　

　　void Bitree_Copy_Nonrecursive(Bitree TBitree &U)//非遞歸復制二叉樹

　　{

　　InitStack(S);InitStack(S);

　　push(ST); //根指針進棧

　　U=(BTNode*)malloc(sizeof(BTNode));

　　U>data=T>data;

　　q=
From:http://tw.wingwit.com/Article/program/sjjg/201311/23564.html