第6章樹(算法設計)習題練習答案

* 二叉樹的遍歷算法可寫為通用形式例如通用的中序遍歷為
　void Inorder(BinTreeTvoid(* visit)(DataType x)){
　　if (T){
　　　　Inorder(T>lchildVisit);//遍歷左子樹
　　　　Visit(T>data);//通過函數指針調用它所指的函數來訪問結點
　　　　Inorder(T>rchildVisit);//遍歷右子樹
　　　}
　}
　　其中Visit是一個函數指針它指向形如void f(DataType x)的函數因此我們可以將訪問結點的操作寫在函數f中通過調用語句Inorder(rootf)將f的地址傳遞給Visit來執行遍歷操作請寫一個打印結點數據的函數通過調用上述算法來完成書中節的中序遍歷

解
　　函數如下
　void PrintNode(BinTree T)
　　{
　　　printf(%cT>data);
　　}

　//定義二叉樹鏈式存儲結構
　typedef char DataType;//定義DataType類型
　typedef struct node{
　　　DataType data;　
　　　struct node *lchild *rchild;//左右孩子子樹
　　}BinTNode; //結點類型

　typedef BinTNode *BinTree ;//二叉樹類型

　void Inorder(BinTree Tvoid(* Visit)(DataType x))
　　{
　　　if(T)
　　　　{
　　　　　Inorder(T>lchildVisit);//遍歷左子樹
　　　　　Visit(T>data); //通過函數指針調用它所指的函數訪問結點
　　　　　Inorder(T>rchildVisit);//遍歷右子樹　
　　　　}
　　}

以二叉鏈表為存儲結構分別寫出求二叉樹結點總數及葉子總數的算法
解
　()求結點數的遞歸定義為
　　若為空樹結點數為
　　若只有根結點則結點數為
　　否則結點數為根結點的左子樹結點數+右子樹結點數+

　()求葉子數的遞歸定義為
　　若為空樹葉子數為
　　若只有根結點則葉子數為
　　否則葉子數為根結點的左子樹葉子數+右子樹葉子數

　typedef char DataType;//定義DataType類型
　typedef struct node{
　　　　DataType data;
　　　　struct node *lchild *rchild;//左右孩子子樹
　　}BinTNode; //結點類型
　typedef BinTNode *BinTree ;//二叉樹類型

　int Node(BinTree T)
　　{//算結點數
　　　if(T)
　　　　if (T>lchild==NULL)&&(T>rchild==NULL)
　　　　　return ;
　　　　else return Node(T>lchild)+Node(T>rchild)+;
　　　else return ;
　　}

　int Leaf(BinTree T)
　　{ //算葉子數
　　　if(T)
　　　　if (T>lchild==NULL)&&(T>rchild==NULL)
　　　　　return ;
　　　　else return Leaf(T>lchild)+Node(T>rchild);
　　　else return ;
　　} 

以二叉鏈表為存儲結構分別寫出求二叉樹高度及寬度的算法所謂寬度是指二叉樹的各層上具有結點數最多的那一層上的結點總數
解
　()根據遞歸定義二叉樹的高度為
　　　當為空樹時高度為
　　　當只有一個結點時高度為
　　　其他情況高度為max(根的左子樹高度根的右子樹高度)+

　int Height(BinTree T)
　　{
　　　int hlhr; 
　　　if(T)
　　　　{//非空樹 
　　　　　if(t>lchild==NUll)&&(t>rchild==NULL)//只含一個根結點
　　　　　　return ;
　　　　　else 
　　　　　　{
　　　　　　　hl=height(t>lchild);//根的左子樹高度
　　　　　　　hr=height(t>rchild);//根的右子樹高度
　　　　　　　if (hl>=hr)
　　　　　　　　return hl+;
　　　　　　　else return h+;
　　　　　　}
　　　　}
　　　else return ;
　　}

　()要求二叉樹的寬度的話則可根據樹的高度設置一個數組temptemp[i]用於存放第i層上的結點數(即寬度)在訪問結點時把相應計算該結點下一層的孩子數並存入相應數組元素中遍歷左子樹後向上返回一層計算右子樹的寬度並取出最大的一個數組元素作為樹的寬度

　#define M //假設二叉樹最多的層數
　int Width(BinTree T)
　　{ 
　　　int static n[M];//向量存放各層結點數
　　　int static i=;
　　　int static max=;//最大寬度
　　　if(T)
　　　　{
　　　　　if(i==) //若是訪問根結點
　　　　　　{ 
　　　　　　　n[i]++; //第層加
　　　　　　　i++; //到第層
　　　　　　　if(T>lchild)//若有左孩子則該層加
　　　　　　　　n[i]++;
　　　　　　　if(T>rchild)//若有右孩子則該層加
　　　　　　　　n[i]++;
　　　　　　}
　　　　　else
　　　　　　{ //訪問子樹結點
　　　　　　　i++; //下一層結點數
　　　　　　　if(T>lchild)
　　　　　　　　n[i]++;
　　　　　　　if(T>rchild) 
　　　　　　　　n[i]++;
　　　　　　}
　　　　　if(max<n[i])max=n[i];//取出最大值
　　　　　　Width(T>lchild);//遍歷左子樹
　　　　　i; //往上退一層
　　　　　Width(T>rchild);//遍歷右子樹
　　　　}
　　　return max;
　　}//算法結束

以二叉鏈表為存儲結構 寫一算法交換各結點的左右子樹
答
　　要交換各結點的左右子樹最方便的辦法是用後序遍歷算法每訪問一個結點時把兩棵子樹的指針進行交換最後一次訪問是交換根結點的子樹

　void ChangeBinTree(BinTree *T)
　　{ //交換子樹
　　　if(*T) 
　　　　{ //這裡以指針為參數使得交換在實參的結點上進行後序遍歷
　　　　　BinTree temp;
　　　　　ChangeBinTree(&(*T)>lchild);
　　　　　ChangeBinTree(&(*T)>rchild);
　　　　　temp=(*T)>lchild;
　　　　　(*T)>lchild=(*T)>rchild;
　　　　　(*T)>rchild=temp;
　　　　} 
　　}

以二叉鏈表為存儲結構寫一個拷貝二叉樹的算法void CopyTree(BinTree root BinTree *newroot)其中新樹的結點是動態申請的為什麼newroot要說明為BinTree型指針的指針? 
解
　　因為調用函數只能進行值傳遞當返回類型為void時就必須把實參的地址傳給函數否則函數不會對實際參數進行任何操作也就得不到所需結果了所以newroot要說明為BinTree型指針

　void CopyTree(BinTree rootBinTree *newroot)
　　{ //拷貝二叉樹
　　　if(root)//如果結點非空
　　　　{ //按前序序列拷貝
　　　　　*newroot=(BinTNode *)malloc(sizeof(BinTNode));//生成新結點
　　　　　(*newroot)>data=root>data;//拷貝結點數據
　　　　　CopyTree(root>lchild&(*newroot)>lchild);//拷貝左子樹
　　　　　CopyTree(root>rchild&(*newroot)>rchild);//拷貝右子樹
　　　　}
　　　else //如果結點為空
　　　*newroot=NULL;//將結點置空
　　}

以二叉鏈表為存儲結構分別寫出在二叉樹中查找值為x的結點及求x所在結點在樹中層數的算法
解
　　根據上幾題的算法可以得出本題的算法如下
　#define M //假設二叉樹最多的層數
　BinTree SearchBTree(BinTree *TDataType x)
　　{//以前序遍歷算法查找值為x的結點
　　　if(*T)
　　　　{
　　　　　if((*T)>data==x )return *T;
　　　　　SearchBTree(&(*T)>lchildx);
　　　　　SearchBTree(&(*T)>rchildx);
　　　　}
　　}

　int InLevel(BinTree TDataType x)
　　{
　　　int static l=;//設一靜態變量保存層數
　　　if(T)
　　　　{ 
　　　　　if(l==)//若是訪問根結點
　　　　　　{ 
　　　　　　　l++;//第層
　　　　　　　if(T>data==x)return l;
　　　　　　　if(T>lchild||T>rchild) 
　　　　　　　　l++;//若根有子樹則層數加
　　　　　　}
　　　　　else
　　　　　　{ //訪問子樹結點
　　　　　　　if(T>data==x)return l;
　　　　　　　if(T>lchild||T>rchild) 
　　　　　　　　l++;//若該結點有子樹則層數加
　　　　　　　else return ;
　　　　　　}
　　　　　InLevel(T>lchildx);//遍歷左子樹
　　　　　InLevel(T>rchildx);//遍歷右子樹
　　　　}
　　}

一棵n個結點的完全二叉樹以向量作為存儲結構試寫一非遞歸算法實現對該樹的前序遍歷
解
　　以向量為存儲結構的完全二叉樹其存儲在向量中的結點其實是按層次遍歷的次序存放的可以根據課本第頁的內容設計出算法

　typedef char DataType;//設結點數據類型為char
　#define M //設結點數不超過
　typedef DataType BinTree[M];

　void Preorder(BinTree T)
　　{ //前序遍歷算法
　　　int n=T[];
　　　int<
From:http://tw.wingwit.com/Article/program/sjjg/201311/23582.html