孩子兄弟鏈表演算法

① 用孩子兄弟表示法建立的樹如何求其各個節點的度

② 樹的孩子兄弟表示法實例（C++實現的）}

孩子兄弟表示法
樹的左兒子右兄弟表示法又稱為二叉樹表示法或二叉鏈表表示法。每個結點除了data域外，還含有兩個域，分別指向該結點的最左兒子和右鄰兄弟。這種表示法常用二叉鏈表實現，因此又稱為二叉鏈表表示法。若用指針實現，其類型定義為：
typedef
NodeType
*TPosition;
struct
NodeType
ElemType
data;
TPosition
Leftmost_Child,Right_Sibling;
}
用樹的左兒子右兄弟表示法可以直接實現樹的大部分操作，只有在對樹結點作Parent操作時需遍歷樹。如果要反復執行Parent操作，可在結點記錄中再開辟一個指向父結點的指針域，也可以利用最右兒子單元中的Right_Sibling作為指向父結點的指針(否則這里總是空指針)。當執行Parent(v)時，可以先通過Right_Sibling逐步找出結點v的最右兄弟，再通過最右兄弟的Right_Sibling(父親指針)找到父結點。這個結點就是結點v的父親。在這樣的表示法下，求一個結點的父親所需要的時間正比於該結點右邊的兄弟個數。不過，這時每個記錄中需要多用一位(bit)空間，用以標明該記錄中的right_sibling是指向右鄰兄弟還是指向父親。
考慮到對於現在的計算機，內存已經不是很重要的限制因素了。我們下面就採取增加一個parent域的方案，以改進左兒子右兄弟表示法中Parent操作的效率。因此重新定義樹的類型如下：
typedef
NodeType
*TPosition;
struct
NodeType
ElemType
data;
TPosition
Parent,Leftmost_Child,Right_Sibling;
//增加一個Parent域
}
如果是
二叉樹，還可以用
一維數組表示，父節點i（i從1開始）
，
左孩子2i，右孩子
2i+1；

③ 樹採用孩子兄弟鏈表來表示,編寫演算法，統計樹中結點總數

孩子兄弟表示法是一顆二叉樹，其左孩子為原樹的孩子，右孩子是其兄弟
若有樹表示為
typedef
struct
BiTNode
{
int
data;
struct
BiTNode
*lchild,*rchild;
}BiTNode,*BTree;
那麼，統計結點總數
int
fun(BTree
tree)
{
if(tree)//樹非空時候
return
fun(tree->lchild)+fun(tree->rchild)+1;
else
return
0;//否則返回0
}

④ 編寫演算法,求以孩子-兄弟鏈表表示的樹中的葉子結點個數

⑤ 假設樹的存儲結構採用孩子兄弟表示法,寫出樹的先序遍歷演算法。該演算法的函數頭為: voidPreOrderTree(

以下兩種描述形式之一均可：

void PreOrderTree(TNode *root, void (*Visit)())

{ p= root; if(p）{Visit(p-> data);

PreOrderTree(p- > firstchild);

PreOrderTree(p-> nextsibling) ；}}

或者:

void PreOrderTree(TNode*root, void ( * Visit)())

{ p= root;

while(p | | ! StackEmpty(s)){

while(p) {Visit(p- > data) ;Push(s,p) ;p=p- > firstchild;}

p= Pop(s);p= p-> nextsibling;}}

(5)孩子兄弟鏈表演算法擴展閱讀

孩子兄弟表示法，採用的是鏈式存儲結構，其存儲樹的實現思想是：從樹的根節點開始，依次用鏈表存儲各個節點的孩子節點和兄弟節點。

因此，該鏈表中的節點應包含以下 3 部分內容：

1、節點的值；

2、指向孩子節點的指針；

3、指向兄弟節點的指針；

用 C 語言代碼表示節點結構為：

#define ElemType char

typedef struct CSNode{

ElemType data;

struct CSNode * firstchild,*nextsibling;

}CSNode,*CSTree;

⑥ 樹以孩子-兄弟鏈表表示，請寫出按層遍歷的演算法

struct LinkNode { TreeNode *node; struct LinkNode *next; }; void Traversal(TreeNode *root) { LinkNode *head; LinkNode *rear; if (root == NULL) return; rear = (LinkNode *)malloc(sizeof(LinkNode)); rear->next = NULL; rear->node = root; head = rear; while(head != NULL) { if (head->node->child != NULL) { rear->next = (LinkNode *)malloc(sizeof(LinkNode)); rear = rear->next; rear->node = head->node->child; rear->next = NULL; TreeNode *tmp = head->node->child->brother; while(tmp != NULL) { rear->next = (LinkNode *)malloc(sizeof(LinkNode)); rear = rear->next; rear->node = tmp; rear->next = NULL; tmp = tmp->brother; } } printf("%d ", head->node->data); tmp = head; head = head->next; free(head); } }

⑦ 設計遞歸演算法，將以「孩子－兄弟鏈表」表示的樹中的結點數據按層次逐一輸出。

fun(CSTree p)
{
if(p!=NULL)
{
printf("%d",p->data);
CSTree q=p;
}
else
return;
if(p->nextsibling!=NULL)
p=p->nextsibling;
while(p!=NULL)
{
printf("%d",p->data);
p=p->nextsibling;
}
while(q!=NULL)
{
fun(q->firstchild);
q=q->nextsibling;
}
}

⑧ 數據結構，二叉樹遍歷，孩子兄弟表示法，演算法設計題

對於一般的家譜樹(一般的多叉樹)來說，我們可以很清楚的看出層次關系，樹的層數表示代數（一共多少代人），樹的最後一層表示最後一代人，由於多叉鏈表法表示的不方便，因此被迫無奈採用孩子兄弟表示法(二叉鏈表法).

假設我的家譜是這樣的：

我們要做的是：這時我們要找有多少代人，以及最後以一代人出來。

如果根據第一個圖來說找代數就是樹的高度，最後一代人就是樹的最後一層，二叉鏈表法中卻不如第一個圖來的直觀，但是只要把握二叉鏈表法的本質還是很清晰的，根據孩子兄弟表示法的特性，（看二叉鏈表法的圖）結點3的左子樹保存的是其孩子，結點3的右子樹保存的是其堂兄弟(對照第一個圖來看)。假設我們每一個節點都有一個變數用來存儲它是第幾代的，那麼從結點1開始，我們要找結點10是第幾代的話，應該這么做：結點1是第一代，然後經過結點5是第二袋，然後看到結點10是第三代。因為第i個結點的左子樹是他的孩子，既然是孩子，代數必須+1，而右子樹是和第i結點同輩份的（堂兄弟），因此不能加1。本質來說就是往左走代數+1，向右走代數不變。這就是這題目的思路，通過這個方法你就可以知道有多少代人了，且每個節點都有保存了代數信息（用變數存起來了），再次遍歷樹把最後一代的結點輸出即可。清晰了嗎？清晰了我就開始寫程序。

⑨ 編寫演算法，對一顆以孩子-兄弟鏈表表示的樹統計每層結點的個數.（是每層結點個數不單單是葉子結點個數）

typedef struct CSNode
{
Elemtype data;
struct CSNode *firstchild,*nextsibling;
}CSNode,*CSTree;
typedef struct node{
CSTree child;
struct node *next;
} * nd;
count(CSTree T){
nd p,q,e;
CSTree r;
int i,c;
//i記錄層數，c記錄每層的結點數；
p=(nd)malloc(sizeof(struct node));
p->child=T;p->next=NULL;
q=p;i=1;
while(q){
c=0;p->next=NULL;
while(q){
r=q->child->firstchild;
while(r){
c++;
if(r->firstchild){
e=(nd)malloc(sizeof(struct node));e->child=r->firstchild;e->next=NULL;
e->next=p->next;p->next=e;
}
r=r->nextsibling;
}
e=q;q=q->next;free(e);
}
printf("第%d層結點數為：%d\n",i,c);
i++;
q=p->next;
}
}

⑩ 已知一棵樹的由根至葉子結點按層次輸出的 結點序列及每個結點的度 試編寫演算法，構造此樹的 孩子兄弟鏈表

CSTree CreateCSTNode(char e); void BuildCSTree(CSTree &T, char *node, int *degree) /* 由結點的層序序列node和各結點的度degree構造樹的孩子兄弟鏈表T */ { int i, j, present=1; CSTree Tree; if(NULL == node) { return; } Tree = CreateCSTNode(node); T = Tree; for(i=0; node!=''; i++) { if(degree!=0) { Tree = CreateCSTNode(node); Tree->firstChild = Tree; present ++; for(j=2; jnextSibling = Tree; present ++; } } } } CSTree CreateCSTNode(char e) { CSTNode *p = NULL; p = (CSTNode*)malloc(sizeof(CSTNode)); p->data = e; p->firstChild = NULL; p->nextSibling = NULL; return p; }