【文章內容簡介】 int NodeNum。 NodeNum=CreateBiTree(amp。T)。 printf(%d,BiTreeDepth(NodeNum))。 Print(T,NodeNum)。 } 主函數(shù) 進入 TC 如圖 。 按完全二叉樹的順序存儲的序列為： ab○ cd○○○○ ef○○○○○○○○○ g “ ○ ” 表示為空結點。 本函數(shù)采用二叉鏈表存儲結點，按下列序列輸入：abc○○ de○ g ○○ f○○○ 得：先序序列： abcdegf 中序序列： cbegdfa 后序序列： cgefdba a b c d e f g 圖 6 . 3 二叉樹 二叉樹遍歷簡介 typedef char TElemType。 define TRUE 1 define FALSE 0 define OK 1 define ERROR 0 define OVERFLOW 2 typedef int Status。 //定義二叉樹及結點的結構。 typedef struct BiTNode { TElemType data。 struct BiTNode *lchild,*rchild。 }BiTNode,*BiTree。 Status InitBiTree(BiTree *T) { //創(chuàng)建一顆空樹 *T=NULL。 return OK。 } 初始化二叉樹 void DestroyBiTree(BiTree *T) { if(*T) { if((*T)lchild) DestroyBiTree(amp。(*T)lchild)。 if((*T)rchild) DestroyBiTree(amp。(*T)rchild)。 free(*T)。 *T=NULL。 } } 銷毀完全二叉樹 構造二叉樹 void CreateBiTree(BiTree *T) { TElemType ch。 int i。 InitBiTree(T)。 scanf(%c,amp。ch)。 if(ch==39。 39。) T=NULL。 else { *T=(BiTree)malloc(sizeof(BiTNode))。 if(!*T) exit(OVERFLOW)。 (*T)data=ch。 CreateBiTree(amp。(*T)lchild)。 CreateBiTree(amp。(*T)rchild)。 } } 輸出二叉樹結點 Status visitT(TElemType e) { printf(%c ,e)。 return OK。 } 先序遍歷二叉樹 Status PreOrderTraverse(BiTree T,Status(*Visit)(TElemType)) { if(T) { Visit(Tdata)。 PreOrderTraverse(Tlchild,Visit)。 PreOrderTraverse(Trchild,Visit)。 return OK。 } else return ERROR。 } 中序遍歷二叉樹 Status InOrderTraverse(BiTree T,Status(*Visit)(TElemType)) { if(T) { InOrderTraverse(Tlchild,Visit)。 Visit(Tdata)。 InOrderTraverse(Trchild,Visit)。 return OK。 } else return ERROR。 } 后序遍歷二叉樹 Status PostOrderTraverse(BiTree T,Status(*Visit)(TElemType)) { if(T) { PostOrderTraverse(Tlchild,Visit)。 PostOrderTraverse(Trchild,Visit)。 Visit(Tdata)。 return OK。 } else return ERROR。 } main() { BiTree T。 clrscr()。 printf(Input BiTree by PreOrder:)。 CreateBiTree(amp。T)。 printf(PreOrder:)。 PreOrderTraverse(T,visitT)。 printf(\nInOrder:)。 InOrderTraverse(T,visitT)。 printf(\nPostOrder:)。 PostOrderTraverse(T,visitT)。 DestroyBiTree(amp。T)。 } 主函數(shù) 進入 TC 建立完全二叉樹執(zhí)行結果 二叉樹遍歷執(zhí)行結果 實驗七：實驗目的及要求 ?理解圖的抽象數(shù)據(jù)類型的定義，及在 C語言環(huán)境中的表示方法。 ?理解圖的基本操作的算法，及在 C語言環(huán)境中一些主要基本操作的實現(xiàn)。 ?在 C語言環(huán)境下實現(xiàn)圖的應用操作： ①使用鄰接矩陣存儲結構，實現(xiàn)無向網的創(chuàng)建和輸出。 ②利用基本操作集，實現(xiàn)采用鄰接表表示的無向圖的非遞歸的廣度優(yōu)先遍歷算法。 實驗內容 無向圖創(chuàng)建和輸出 ? 鄰接矩陣存儲結構 ? 創(chuàng)建無向圖 ? 查找頂點是否在圖中 ? 輸出無向網的鄰接矩陣 ? 主函數(shù) 生成無向圖并顯示 非遞歸 廣度優(yōu)先遍歷 ? 存儲結構 ? 鄰接表存儲的無向圖 ? 查找指定頂點的鄰接點 ? 銷毀圖 ? 輸出圖的鄰接表 ? 廣度優(yōu)先遍歷 ? 主函數(shù) 非遞歸廣度優(yōu)先遍歷 退出 鄰接矩陣存儲結構 define INFINITY 1024 define MAX_VERTEX_NUM 20 define MAX_NAME 3 typedef int VRType。 typedef char InfoType。 typedef int Status。 typedef char VertexType[MAX_NAME]。 typedef enum{DG,DN,UDG,UDN}GraphKind。 //有向圖、有向網、無向圖、無向網 鄰接矩陣存儲結構 typedef struct { VRType adj。 //對無權圖用 1或 0表示相鄰否；帶權圖則為權值類型 InfoType *info。 //該弧相關信息的指針 }ArcCell, AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM]。 //圖的結構定義。 typedef struct { VertexType vexs[MAX_VERTEX_NUM]。 //頂點向量 AdjMatrix arcs。 //相鄰矩陣 int vexnum,arum。 //圖的當前頂點數(shù)和弧數(shù) GraphKind kind。 //圖的種類標志 }MGraph。 創(chuàng)建無向圖 ? 在本函數(shù)創(chuàng)建鄰接矩陣時，權值賦為“ INFINITY”，當在 Display()輸出時才顯示成“ *”，圖 “ *”是為了使顯示的鄰接矩陣更簡捷，易懂。 ? 在輸入弧時，為了突出修改權值的操作，沒有對輸錯的弧 (即圖中不存在的頂點的弧 )進行判斷，只以弧的輸入計數(shù)對程序進行控制，讀者可自行添加。 ? 如讀者希望創(chuàng)建無向圖，對本函數(shù)只需做兩點修改： ? ①在初始建立鄰接矩陣時，初始值賦為 0。 ? ②在輸入的弧信息中，只輸入兩個頂點，不需要輸入權值，而且在鄰接矩陣中將 0修改為 1。 ? 有向圖和有向網的創(chuàng)建與無向圖、無向網的創(chuàng)建類似，需注意的是在輸入弧信息后修改鄰接矩陣時，只修改一條弧的信息，如輸入弧 (VV 5)，則只將第 1行第二列的 0或 *修改為 5。 流程圖 源代碼 創(chuàng)建無向圖 開始 輸入 無向網的 頂點 數(shù) 、弧數(shù) 輸入各個頂點 如： 用兩層循環(huán)創(chuàng)建圖的鄰接矩陣，每個值為最大值 k =0 k 弧 數(shù) ? N Y k +1 輸入 弧的兩個 頂點 、權值 查找結點，修改鄰接矩陣中該弧的權值 結束 如 v 1 , v 2 , v 3 , v 4 , v 5 如 5 , 6 如v 1 , v 2 , v 3, v 4 , v 5 V 1,v 2,v3,v 4,v 5 如 v1 ， v2 ， 5 如v 1 , v 2 , v 3 , v 4 , v5 V 1,v 2,v 3,v 4,v5 將第 1 行第 2 列的 * 修改成 5 將第 2 行第 1 列的 * 修改成 5 * * * * * * * * * * * * * * * * * * * * * * * * * 創(chuàng)建無向圖 ? Status CreateUDN(MGraph *G) ? { ? int i,j,k,w。 VertexType va,vb。 ? printf(Please input vexnum, arum:)。 ? scanf(%d,%d,amp。(*G).vexnum,amp。(*G).arum)。 ? printf(Please input %d vexs:\n,(*G).vexnum)。 ? for(i=0。i(*G).vexnum。++i) scanf(%s,(*G).vexs[i])。 ? for(i=0。i(*G).vexnum。++i) ? for(j=0。j(*G).vexnum。++j){ ? (*G).arcs[i][j].adj=INFINITY。 (*G).arcs[i][j].info=NULL。 } ? printf(Input details(eg. V1 V2 5): \n)。 ? for(k=0。k(*G).arum。++k){ ? scanf(%s%s%d,va,vb,amp。w)。i=LocateVex(*G,va)。 j=LocateVex(*G,vb)。 ? (*G).arcs[i][j].adj=(*G).arcs[j][i].adj=w。 ? }(*G).kind=UDN。 ? } 查找頂點是否在圖中 int LocateVex(MGraph G,VertexType u) {//查找頂點 u是否存在于圖的頂點向量中。 int i。 for(i=0。i。++i) if(strcmp(u,[i])==0) return i。 return 1。 } 輸出無向網的鄰接矩陣 void Display(MGraph G) {