數據結構第六章(樹)習題答案(上)

　　二算法設計題

　　 二叉樹的遍歷算法可寫為通用形式例如通用的中序遍歷為

　　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 ;//二叉樹類型 #include

　　#include

　　void CreatBinTree(BinTree *T)//輸入序列是先序序列

　　{ //構造二叉鏈表T是指向根的指針故修改了*T就修改了實參

　　char ch;

　　if ((ch=getchar())== )

　　*T=NULL;

　　else{ //讀入非空格

　　*T=(BinTNode *)malloc(sizeof(BinTNode));//生成結點

　　(*T)>data=ch;

　　CreatBinTree(&(*T)>lchild); //構造左子樹

　　CreatBinTree(&(*T)>rchild); //構造右子樹

　　}

　　}

　　//

　　void PrintNode(DataType x)

　　{ //題目要求的打印函數

　　printf(%cx);

　　}

　　//

　　void Inorder(BinTree Tvoid(* Visit)(DataType x))

　　{

　　if(T)

　　{

　　Inorder(T>lchildVisit);//遍歷左子樹

　　Visit(T>data); //通過函數指針調用它所指的函數訪問結點

　　Inorder(T>rchildVisit);//遍歷右子樹

　　}

　　}

　　void main()

　　{ //現在開始測試啦 BinTree root; //定義一個根結點

　　CreatBinTree(&root); //建立二叉鏈表

　　printf(\n);

　　Inorder(rootPrintNode);//調用函數注意傳遞的是函數名(它就是地址)

　　printf(\n);

　　}

　　//運行時請輸入ab c (注意b後和c後面各兩個空格)再回車可生成一個以a為根的兩片葉子的二叉樹看看打印的結果對不對?

　　 以二叉鏈表為存儲結構分別寫出求二叉樹結點總數及葉子總數的算法

　　解利用中序遍歷我們很容易地就能找到這個算法每訪問一次非空結點就給變量nodes加上; 每訪問到一個其左右子樹皆空的結點就給變量leaves加上最後就得到結果了

　　完整程序如下所示 //定義二叉樹鏈式存儲結構等內容為方便起見我們將這一段內容存為bintreeh文件以後只在程序中加入這個頭文件就是了 //bintreeh 文件開始 typedef char DataType;//定義DataType類型

　　typedef struct node{

　　DataType data;

　　struct node *lchild *rchild;//左右孩子子樹

　　}BinTNode; //結點類型 typedef BinTNode *BinTree ;//二叉樹類型 #include

　　#include

　　void CreatBinTree(BinTree *T)

　　{ //構造二叉鏈表注意:輸入序列是先序序列

　　char ch;

　　if ((ch=getchar())== )

　　*T=NULL;

　　else{ //讀入非空格

　　*T=(BinTNode *)malloc(sizeof(BinTNode));//生成結點

　　(*T)>data=ch;

　　CreatBinTree(&(*T)>lchild); //構造左子樹

　　CreatBinTree(&(*T)>rchild); //構造右子樹

　　}

　　}//文件結束 //以下兩個函數為題目要求算法 int Node(BinTree T)

　　{ //算結點數

　　int static nodes=;//靜態變量保留每次遞歸調用後的值

　　if(T)

　　{ //使用中序遍歷

　　Node(T>lchild); //遍歷左子樹

　　nodes++; //結點數加

　　Node(T>rchild); //遍歷右子樹

　　}

　　return nodes;

　　} int Leaf(BinTree T)

　　{ //算葉子數

　　int static leaves=;//靜態變量保證其值不會隨遞歸調用而消失

　　if(T)

　　{ //使用中序遍歷

　　Leaf(T>lchild); //遍歷左子樹

　　if(!(T>lchild||T>rchild))//左右孩子均為空

　　leaves++; //葉子數加

　　Leaf(T>rchild); //遍歷右子樹

　　}

　　return leaves;

　　}//算法結束 #include

　　void main()

　　{ //測試程序

　　BinTree root;

　　CreatBinTree(&root);

　　int nodes=Node(root);

　　int leaves=Leaf(root);

　　printf(\nnodes=%d leaves=%dnodesleaves);

　　}

　　以二叉鏈表為存儲結構分別寫出求二叉樹高度及寬度的算法所謂寬度是指二叉樹的各層上具有結點數最多的那一層上的結點總數

　　解要想求出二叉樹的高度可以采用前序遍歷設一個個記錄高度的變量h 在訪問結點時查詢該結點是否有孩子有則高度加其中根結點比特殊自身算一層 要求二叉樹的寬度的話則可根據樹的高度設置一個數組在訪問結點時計算該結點下一層的孩子數並存入相應數組元素中遍歷左子樹後向上返回一層計算右子樹的寬度並取出最大的一個數組元素作為樹的寬度

　　#include

　　#include bintreeh

　　#define M //假設二叉樹最多的層數

　　int Height(BinTree T)//求樹的深度

　　{ //求深度算法由阮允准更正在此深表感謝

　　int lhighrhighhigh=;

　　if(T!=NULL)

　　{

　　lhigh=Height(T>lchild);//左子樹高度

　　rhigh=Height(T>rchild);//右子樹高度

　　high=(lhigh>rhigh?lhigh:rhigh)+;//樹的高度等於左子樹右子樹之間的大者加上根結點

　　}

　　return high;

　　} 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

　　Width(T->lchild);//遍歷左子樹

　　i--; //往上退一層

　　Width(T->rchild);//遍歷右子樹

　　}

　　return max;

　　}//算法結束 void main()

　　{ //測試程序

　　BinTree root;

　　CreatBinTree (&root);

　　printf("\nHeight of BinTree:%d",Height(root));

　　printf("\nWidth of BinTree:%d",Width(root));

　　}

　　6.25 以二叉鏈表為存儲結構， 寫一算法交換各結點的左右子樹。TW.WinGwiT.Com

　　要交換各結點的左右子樹，最方便的辦法是用後序遍歷算法，每訪問一個結點時把兩棵子樹的指針進行交換，最後一次訪問是交換根結點的子樹。

　　#include

　　#include "bintree.h"

　　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 PrintNode(BinTree T)

　　{ //以前序序列打印結點數據

　　if(T)

　　{

　　printf("%c",T->data);

　　PrintNode(T->lchild);

From:http://tw.wingwit.com/Article/program/sjjg/201311/23663.html