-
孩子鏈表示法
鎖定
- 中文名
- 孩子鏈表示法
- 外文名
- child chain notation
- 學 科
- 計算機科學
- 領 域
- 數據結構
- 存儲方式
- 鏈式存儲
- 有關術語
- 樹
目錄
- 1 定義
- 2 樹
- 3 雙親表示法與孩子兄弟表示法
孩子鏈表示法定義
孩子鏈表示法是指同一雙親的孩子鏈成單鏈，每個節點帶有指向孩子鏈的指針。樹的所有結點都有唯一的父節點，但是每個結點都有不確定數量的子結點
[1]
。每個結點由三部分組成：存儲數據元素值的數據部分、指向它的第一個子結點的指針、指向它的兄弟結點的指針。孩子鏈表示法是樹最常用的存儲方式。
[2]
孩子表示法也用一組連續的存儲空間來存放樹的所有結點，每個空間存放一個結點的信息；但是附加信息不再存放本結點的雙親結點的位置信息，而是存放本結點的孩子結點的位置信息。由於樹的結點可能會有多個孩子結點，因此孩子結點的位置信息無法直接存放，可以把每個結點的孩子結點的位置信息排列起來成為一個線性表，以單鏈表作為存儲結構（這樣n個結點就有n個孩子鏈表），每個結點的附加信息裏存放上本結點的孩子鏈表的地址信息。
[3]
#include<stdio.h>
#include<stdlib.h>
#define MAX_SIZE 20
#define TElemType char
//孩子表示法
typedef struct CTNode{
int child;//鏈表中每個結點存儲的不是數據本身，而是數據在數組中存儲的位置下標
struct CTNode * next;
}ChildPtr;
typedef struct {
TElemType data;//結點的數據類型
ChildPtr* firstchild;//孩子鏈表的頭指針
}CTBox;
typedef struct{
CTBox nodes[MAX_SIZE];//存儲結點的數組
int n,r;//結點數量和樹根的位置
}CTree;
//孩子表示法存儲普通樹
CTree initTree(CTree tree){
printf("輸入節點數量：\n");
scanf("%d",&(tree.n));
for(int i=0;i<tree.n;i++){
printf("輸入第 %d 個節點的值：\n",i+1);
fflush(stdin);
scanf("%c",&(tree.nodes[i].data));
tree.nodes[i].firstchild=(ChildPtr*)malloc(sizeof(ChildPtr));
tree.nodes[i].firstchild->next=NULL;
printf("輸入節點 %c 的孩子節點數量：\n",tree.nodes[i].data);
int Num;
scanf("%d",&Num);
if(Num!=0){
ChildPtr * p = tree.nodes[i].firstchild;
for(int j = 0 ;j<Num;j++){
ChildPtr * newEle=(ChildPtr*)malloc(sizeof(ChildPtr));
newEle->next=NULL;
printf("輸入第 %d 個孩子節點在順序表中的位置",j+1);
scanf("%d",&(newEle->child));
p->next= newEle;
p=p->next;
}
}
}
return tree;
}
void findKids(CTree tree,char a){
int hasKids=0;
for(int i=0;i<tree.n;i++){
if(tree.nodes[i].data==a){
ChildPtr * p=tree.nodes[i].firstchild->next;
while(p){
hasKids = 1;
printf("%c ",tree.nodes[p->child].data);
p=p->next;
}
break;
}
}
if(hasKids==0){
printf("此節點為葉子節點");
}
}
int main()
{
CTree tree;
tree = initTree(tree);
//默認數根節點位於數組notes[0]處
tree.r=0;
printf("找出節點 F 的所有孩子節點：");
findKids(tree,'F');
return 0;
}
孩子鏈表示法樹
在計算機科學中，樹（tree）是一種抽象數據類型（ADT）或是實現這種抽象數據類型的數據結構，用來模擬具有樹狀結構性質的數據集合。它是由n（n>0）個有限節點組成一個具有層次關係的集合。樹是由根結點和若干顆子樹構成的。樹是由一個集合以及在該集合上定義的一種關係構成的。集合中的元素稱為樹的結點，所定義的關係稱為父子關係。父子關係在樹的結點之間建立了一個層次結構。在這種層次結構中有一個結點具有特殊的地位，這個結點稱為該樹的根結點，或稱為樹根。它具有以下的特點：
1、每個節點都只有有限個子節點或無子節點；
2、沒有父節點的節點稱為根節點；
3、每一個非根節點有且只有一個父節點；
4、除了根節點外，每個子節點可以分為多個不相交的子樹；
5、樹裏面沒有環路(cycle)。
孩子鏈表示法雙親表示法與孩子兄弟表示法
雙親表示法，樹的一種存儲方式。讓每個結點記住其父結點的位置。存儲數據元素的結點由兩部分組成：存儲數據元素值的數據字段，以及存儲父結點位置的父指針字段。樹的所有結點可存放在一個數組中（稱“靜態雙親表示法”），也可組織成一個鏈表（稱“動態雙親表示法”）。雙親表示法採用順序表（也就是數組）存儲普通樹，其實現的核心思想是：順序存儲各個節點的同時，給各節點附加一個記錄其父節點位置的變量。
孩子兄弟表示法就是既表示出每個結點的第一個孩子結點，也表示出每個結點的下一個兄弟結點。孩子兄弟表示法需要為每個結點設計三個域：一個數據元素域、一個指向該結點的第一個孩子結點的指針域、一個指向該結點的下一個兄弟結點的指針域。孩子兄弟表示法的最大優點是可以方便地實現樹和二叉樹的相互轉換，但是它的缺點也和孩子表示法的缺點一樣：就是從當前結點查找雙親結點比較麻煩，需要從樹的根結點開始逐個結點比較查找
[4]
。
- 參考資料
-
- 1. 賀林卿, 李海．數據庫系統工程師考試全程指導：清華大學出版社，2006
- 2. 夏徵農，陳至立主編；幹福熹編,大辭海 信息科學卷,上海辭書出版社,2015.12,第110頁
- 3. 葉軍偉.樹型數據結構存儲方法的探討[J].科技創業家,2014(07):155. ．中國知網[引用日期2019-07-20]
- 4. 袁關偉,趙家剛.基於遞歸算法在孩子兄弟法表示的樹中查找任一結點的雙親結點算法的設計與實現[J].現代計算機(專業版),2011(19):3-6. ．中國知網[引用日期2019-07-20]
