孩子兄弟链表算法

① 用孩子兄弟表示法建立的树如何求其各个节点的度

② 树的孩子兄弟表示法实例（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; }