// c6-5.h 樹的二叉鏈表(孩子—兄弟)存儲(chǔ)結(jié)構(gòu)(見圖6.32) typedef struct CSNode {TElemType data;CSNode *firstchild,*nextsibling; }CSNode,*CSTree;

一棵樹無(wú)論有多少叉，它最多有一個(gè)長(zhǎng)子和一個(gè)排序恰在其下的兄弟。根據(jù)這樣的定
義，則每個(gè)結(jié)點(diǎn)的結(jié)構(gòu)就都統(tǒng)一到了二叉鏈表結(jié)構(gòu)上。這樣有利于對(duì)結(jié)點(diǎn)進(jìn)行操作。圖
633 是圖628(a)所示之樹的二叉鏈表(孩子—兄弟)存儲(chǔ)結(jié)構(gòu)。

// func6-2.cpp bo6-5.cpp和algo7-1.cpp調(diào)用 void PreOrderTraverse(CSTree T,void(*Visit)(TElemType)) { // 先根遍歷孩子—兄弟二叉鏈表結(jié)構(gòu)的樹Tif(T){Visit(T->data); // 先訪問(wèn)根結(jié)點(diǎn)PreOrderTraverse(T->firstchild,Visit); // 再先根遍歷長(zhǎng)子子樹PreOrderTraverse(T->nextsibling,Visit); // 最后先根遍歷下一個(gè)兄弟子樹} }

// bo6-5.cpp 樹的二叉鏈表(孩子—兄弟)存儲(chǔ)(存儲(chǔ)結(jié)構(gòu)由c6-5.h定義)的基本操作(17個(gè)) #define ClearTree DestroyTree // 二者操作相同 #include"func6-2.cpp" // 包括PreOrderTraverse() void InitTree(CSTree &T) { // 操作結(jié)果：構(gòu)造空樹TT=NULL; } void DestroyTree(CSTree &T) { // 初始條件：樹T存在。操作結(jié)果：銷毀樹Tif(T){if(T->firstchild) // T有長(zhǎng)子DestroyTree(T->firstchild); // 銷毀T的長(zhǎng)子為根結(jié)點(diǎn)的子樹if(T->nextsibling) // T有下一個(gè)兄弟DestroyTree(T->nextsibling); // 銷毀T的下一個(gè)兄弟為根結(jié)點(diǎn)的子樹free(T); // 釋放根結(jié)點(diǎn)T=NULL;} } typedef CSTree QElemType; // 定義隊(duì)列元素類型 #include"c3-2.h" // 定義LinkQueue類型(鏈隊(duì)列) #include"bo3-2.cpp" // LinkQueue類型的基本操作 void CreateTree(CSTree &T) { // 構(gòu)造樹Tchar c[20]; // 臨時(shí)存放孩子結(jié)點(diǎn)(設(shè)不超過(guò)20個(gè))的值CSTree p,p1;LinkQueue q;int i,l;InitQueue(q);printf("請(qǐng)輸入根結(jié)點(diǎn)(字符型,空格為空): ");scanf("%c%*c",&c[0]);if(c[0]!=Nil) // 非空樹{T=(CSTree)malloc(sizeof(CSNode)); // 建立根結(jié)點(diǎn)T->data=c[0];T->nextsibling=NULL;EnQueue(q,T); // 入隊(duì)根結(jié)點(diǎn)的指針while(!QueueEmpty(q)) // 隊(duì)不空{(diào)DeQueue(q,p); // 出隊(duì)一個(gè)結(jié)點(diǎn)的指針printf("請(qǐng)按長(zhǎng)幼順序輸入結(jié)點(diǎn)%c的所有孩子: ",p->data);gets(c);l=strlen(c);if(l>0) // 有孩子{p1=p->firstchild=(CSTree)malloc(sizeof(CSNode)); // 建立長(zhǎng)子結(jié)點(diǎn)p1->data=c[0];for(i=1;i<l;i++){p1->nextsibling=(CSTree)malloc(sizeof(CSNode)); // 建立下一個(gè)兄弟結(jié)點(diǎn)EnQueue(q,p1); // 入隊(duì)上一個(gè)結(jié)點(diǎn)p1=p1->nextsibling;p1->data=c[i];}p1->nextsibling=NULL;EnQueue(q,p1); // 入隊(duì)最后一個(gè)結(jié)點(diǎn)}elsep->firstchild=NULL; // 長(zhǎng)子指針為空}}elseT=NULL; // 空樹 } Status TreeEmpty(CSTree T) { // 初始條件：樹T存在。操作結(jié)果：若T為空樹，則返回TURE；否則返回FALSEif(T) // T不空return FALSE;elsereturn TRUE; } int TreeDepth(CSTree T) { // 初始條件：樹T存在。操作結(jié)果：返回T的深度CSTree p;int depth,max=0;if(!T) // 樹空return 0;if(!T->firstchild) // 樹無(wú)長(zhǎng)子return 1;for(p=T->firstchild;p;p=p->nextsibling){ // 求子樹深度的最大值depth=TreeDepth(p);if(depth>max)max=depth;}return max+1; // 樹的深度=子樹深度最大值+1 } TElemType Value(CSTree p) { // 返回p所指結(jié)點(diǎn)的值return p->data; } TElemType Root(CSTree T) { // 初始條件：樹T存在。操作結(jié)果：返回T的根if(T)return Value(T);elsereturn Nil; } CSTree Point(CSTree T,TElemType s) { // 返回二叉鏈表(孩子—兄弟)樹T中指向元素值為s的結(jié)點(diǎn)的指針。另加LinkQueue q;QElemType a;if(T) // 非空樹{InitQueue(q); // 初始化隊(duì)列EnQueue(q,T); // 根結(jié)點(diǎn)入隊(duì)while(!QueueEmpty(q)) // 隊(duì)不空{(diào)DeQueue(q,a); // 出隊(duì),隊(duì)列元素賦給aif(a->data==s)return a;if(a->firstchild) // 有長(zhǎng)子EnQueue(q,a->firstchild); // 入隊(duì)長(zhǎng)子if(a->nextsibling) // 有下一個(gè)兄弟EnQueue(q,a->nextsibling); // 入隊(duì)下一個(gè)兄弟}}return NULL; } Status Assign(CSTree &T,TElemType cur_e,TElemType value) { // 初始條件：樹T存在，cur_e是樹T中結(jié)點(diǎn)的值。操作結(jié)果：改cur_e為valueCSTree p;if(T) // 非空樹{p=Point(T,cur_e); // p為cur_e的指針if(p) // 找到cur_e{p->data=value; // 賦新值return OK;}}return ERROR ; // 樹空或沒找到 } TElemType Parent(CSTree T,TElemType cur_e) { // 初始條件：樹T存在，cur_e是T中某個(gè)結(jié)點(diǎn)// 操作結(jié)果：若cur_e是T的非根結(jié)點(diǎn)，則返回它的雙親；否則函數(shù)值為“空”CSTree p,t;LinkQueue q;InitQueue(q);if(T) // 樹非空{(diào)if(Value(T)==cur_e) // 根結(jié)點(diǎn)值為cur_ereturn Nil;EnQueue(q,T); // 根結(jié)點(diǎn)入隊(duì)while(!QueueEmpty(q)){DeQueue(q,p);if(p->firstchild) // p有長(zhǎng)子{if(p->firstchild->data==cur_e) // 長(zhǎng)子為cur_ereturn Value(p); // 返回雙親t=p; // 雙親指針賦給tp=p->firstchild; // p指向長(zhǎng)子EnQueue(q,p); // 入隊(duì)長(zhǎng)子while(p->nextsibling) // 有下一個(gè)兄弟{p=p->nextsibling; // p指向下一個(gè)兄弟if(Value(p)==cur_e) // 下一個(gè)兄弟為cur_ereturn Value(t); // 返回雙親EnQueue(q,p); // 入隊(duì)下一個(gè)兄弟}}}}return Nil; // 樹空或沒找到cur_e } TElemType LeftChild(CSTree T,TElemType cur_e) { // 初始條件：樹T存在，cur_e是T中某個(gè)結(jié)點(diǎn)// 操作結(jié)果：若cur_e是T的非葉子結(jié)點(diǎn)，則返回它的最左孩子；否則返回“空”CSTree f;f=Point(T,cur_e); // f指向結(jié)點(diǎn)cur_eif(f&&f->firstchild) // 找到結(jié)點(diǎn)cur_e且結(jié)點(diǎn)cur_e有長(zhǎng)子return f->firstchild->data;elsereturn Nil; } TElemType RightSibling(CSTree T,TElemType cur_e) { // 初始條件：樹T存在，cur_e是T中某個(gè)結(jié)點(diǎn)// 操作結(jié)果：若cur_e有右兄弟，則返回它的右兄弟；否則返回“空”CSTree f;f=Point(T,cur_e); // f指向結(jié)點(diǎn)cur_eif(f&&f->nextsibling) // 找到結(jié)點(diǎn)cur_e且結(jié)點(diǎn)cur_e有右兄弟return f->nextsibling->data;elsereturn Nil; // 樹空 } Status InsertChild(CSTree &T,CSTree p,int i,CSTree c) { // 初始條件：樹T存在，p指向T中某個(gè)結(jié)點(diǎn)，1≤i≤p所指結(jié)點(diǎn)的度+1，非空樹c與T不相交// 操作結(jié)果：插入c為T中p結(jié)點(diǎn)的第i棵子樹// 因?yàn)閜所指結(jié)點(diǎn)的地址不會(huì)改變，故p不需是引用類型int j;if(T) // T不空{(diào)if(i==1) // 插入c為p的長(zhǎng)子{c->nextsibling=p->firstchild; // p的原長(zhǎng)子現(xiàn)是c的下一個(gè)兄弟(c本無(wú)兄弟)p->firstchild=c;}else // 找插入點(diǎn){p=p->firstchild; // 指向p的長(zhǎng)子j=2;while(p&&j<i){p=p->nextsibling;j++;}if(j==i) // 找到插入位置{c->nextsibling=p->nextsibling;p->nextsibling=c;}else // p原有孩子數(shù)小于i-1return ERROR;}return OK;}else // T空return ERROR; } Status DeleteChild(CSTree &T,CSTree p,int i) { // 初始條件：樹T存在，p指向T中某個(gè)結(jié)點(diǎn)，1≤i≤p所指結(jié)點(diǎn)的度// 操作結(jié)果：刪除T中p所指結(jié)點(diǎn)的第i棵子樹// 因?yàn)閜所指結(jié)點(diǎn)的地址不會(huì)改變，故p不需是引用類型CSTree b;int j;if(T) // T不空{(diào)if(i==1) // 刪除長(zhǎng)子{b=p->firstchild;p->firstchild=b->nextsibling; // p的原次子現(xiàn)是長(zhǎng)子b->nextsibling=NULL;DestroyTree(b);}else // 刪除非長(zhǎng)子{p=p->firstchild; // p指向長(zhǎng)子j=2;while(p&&j<i){p=p->nextsibling;j++;}if(j==i) // 找到第i棵子樹{b=p->nextsibling;p->nextsibling=b->nextsibling;b->nextsibling=NULL;DestroyTree(b);}else // p原有孩子數(shù)小于ireturn ERROR;}return OK;}elsereturn ERROR; } void PostOrderTraverse(CSTree T,void(*Visit)(TElemType)) { // 后根遍歷孩子—兄弟二叉鏈表結(jié)構(gòu)的樹TCSTree p;if(T){if(T->firstchild) // 有長(zhǎng)子{PostOrderTraverse(T->firstchild,Visit); // 后根遍歷長(zhǎng)子子樹p=T->firstchild->nextsibling; // p指向長(zhǎng)子的下一個(gè)兄弟while(p){PostOrderTraverse(p,Visit); // 后根遍歷下一個(gè)兄弟子樹p=p->nextsibling; // p指向再下一個(gè)兄弟}}Visit(Value(T)); // 最后訪問(wèn)根結(jié)點(diǎn)} } void LevelOrderTraverse(CSTree T,void(*Visit)(TElemType)) { // 層序遍歷孩子—兄弟二叉鏈表結(jié)構(gòu)的樹TCSTree p;LinkQueue q;InitQueue(q);if(T){Visit(Value(T)); // 先訪問(wèn)根結(jié)點(diǎn)EnQueue(q,T); // 入隊(duì)根結(jié)點(diǎn)的指針while(!QueueEmpty(q)) // 隊(duì)不空{(diào)DeQueue(q,p); // 出隊(duì)一個(gè)結(jié)點(diǎn)的指針if(p->firstchild) // 有長(zhǎng)子{p=p->firstchild;Visit(Value(p)); // 訪問(wèn)長(zhǎng)子結(jié)點(diǎn)EnQueue(q,p); // 入隊(duì)長(zhǎng)子結(jié)點(diǎn)的指針while(p->nextsibling) // 有下一個(gè)兄弟{p=p->nextsibling;Visit(Value(p)); // 訪問(wèn)下一個(gè)兄弟EnQueue(q,p); // 入隊(duì)兄弟結(jié)點(diǎn)的指針}}}} }
// main6-5.cpp 檢驗(yàn)bo6-5.cpp的主程序 #include"c1.h" typedef char TElemType; TElemType Nil=' '; // 以空格符為空 #include"c6-5.h" #include"bo6-5.cpp" void vi(TElemType c) {printf("%c ",c); } void main() {int i;CSTree T,p,q;TElemType e,e1;InitTree(T);printf("構(gòu)造空樹后,樹空否? %d(1:是0:否) 樹根為%c 樹的深度為%d\n",TreeEmpty(T),Root(T),TreeDepth(T));CreateTree(T);printf("構(gòu)造樹T后,樹空否? %d(1:是0:否) 樹根為%c 樹的深度為%d\n",TreeEmpty(T),Root(T),TreeDepth(T));printf("先根遍歷樹T:\n");PreOrderTraverse(T,vi);printf("\n請(qǐng)輸入待修改的結(jié)點(diǎn)的值新值: ");scanf("%c%*c%c%*c",&e,&e1);Assign(T,e,e1);printf("后根遍歷修改后的樹T:\n");PostOrderTraverse(T,vi);printf("\n%c的雙親是%c,長(zhǎng)子是%c,下一個(gè)兄弟是%c\n",e1,Parent(T,e1),LeftChild(T,e1),RightSibling(T,e1));printf("建立樹p:\n");InitTree(p);CreateTree(p);printf("層序遍歷樹p:\n");LevelOrderTraverse(p,vi);printf("\n將樹p插到樹T中，請(qǐng)輸入T中p的雙親結(jié)點(diǎn)子樹序號(hào): ");scanf("%c%d%*c",&e,&i);q=Point(T,e);InsertChild(T,q,i,p);printf("層序遍歷樹T:\n");LevelOrderTraverse(T,vi);printf("\n刪除樹T中結(jié)點(diǎn)e的第i棵子樹，請(qǐng)輸入e i: ");scanf("%c%d",&e,&i);q=Point(T,e);DeleteChild(T,q,i);printf("層序遍歷樹T:\n",e,i);LevelOrderTraverse(T,vi);printf("\n");DestroyTree(T); }
代碼的運(yùn)行結(jié)果：

構(gòu)造空樹后,樹空否? 1(1:是0:否) 樹根為樹的深度為0
請(qǐng)輸入根結(jié)點(diǎn)(字符型,空格為空): R
請(qǐng)按長(zhǎng)幼順序輸入結(jié)點(diǎn)R的所有孩子: ABC
請(qǐng)按長(zhǎng)幼順序輸入結(jié)點(diǎn)A的所有孩子: DE
請(qǐng)按長(zhǎng)幼順序輸入結(jié)點(diǎn)B的所有孩子:
請(qǐng)按長(zhǎng)幼順序輸入結(jié)點(diǎn)C的所有孩子: F
請(qǐng)按長(zhǎng)幼順序輸入結(jié)點(diǎn)D的所有孩子:
請(qǐng)按長(zhǎng)幼順序輸入結(jié)點(diǎn)E的所有孩子:
請(qǐng)按長(zhǎng)幼順序輸入結(jié)點(diǎn)F的所有孩子: GHK
請(qǐng)按長(zhǎng)幼順序輸入結(jié)點(diǎn)G的所有孩子:
請(qǐng)按長(zhǎng)幼順序輸入結(jié)點(diǎn)H的所有孩子:
請(qǐng)按長(zhǎng)幼順序輸入結(jié)點(diǎn)K的所有孩子:
構(gòu)造樹T后,樹空否? 0(1:是0:否) 樹根為R 樹的深度為4
先根遍歷樹T:(見圖628(a))
R A D E B C F G H K
請(qǐng)輸入待修改的結(jié)點(diǎn)的值新值: D d
后根遍歷修改后的樹T:
d E A B G H K F C R
d的雙親是A,長(zhǎng)子是,下一個(gè)兄弟是E
建立樹p:
請(qǐng)輸入根結(jié)點(diǎn)(字符型,空格為空): f
請(qǐng)按長(zhǎng)幼順序輸入結(jié)點(diǎn)f的所有孩子: ghk
請(qǐng)按長(zhǎng)幼順序輸入結(jié)點(diǎn)g的所有孩子:
請(qǐng)按長(zhǎng)幼順序輸入結(jié)點(diǎn)h的所有孩子:
請(qǐng)按長(zhǎng)幼順序輸入結(jié)點(diǎn)k的所有孩子:
層序遍歷樹p:(見圖629)
f g h k
將樹p插到樹T中，請(qǐng)輸入T中p的雙親結(jié)點(diǎn)子樹序號(hào): R 3
層序遍歷樹T:(見圖630)
R A B f C d E g h k F G H K
刪除樹T中結(jié)點(diǎn)e的第i棵子樹，請(qǐng)輸入e i: C 1
層序遍歷樹T:(見圖631)

R A B f C d E g h k

轉(zhuǎn)載于:https://www.cnblogs.com/KongkOngL/p/3945943.html

總結(jié)

以上是生活随笔為你收集整理的树的存储结构（树的二叉链表(孩子—兄弟)）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。