用二叉链表存树（孩子兄弟表示法）_二叉链表存储树

用二叉链表存树（孩子兄弟表示法）

用二叉链表的左子树指向该节点最左边的孩子，右子树指向该节点的兄弟，以达到存树的目的

储存结构

typedef struct Node {
	int data;
	struct Node* firstchild;
	struct Node* nextbro;
}Tree;
1
2
3
4
5

建树的方式跟二叉树基本是相同的

Tree* creatTree()
{
	Tree* T;
	char data;
	data = getchar();
	if (data == '#')
	{
		T = NULL;
	}
	else
	{
		T = (Tree*)malloc(sizeof(Tree));
		T->data = data;
		T->firstchild = creatTree();
		T->nextbro = creatTree();
	}
	return T;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

例如，

A结点的左边第一个孩子是B，A没有兄弟，那么

A→firstchild = B; A→nextbro = NULL;

B 的孩子为E，兄弟为C、D，那么

B的firstchild指向E节点，B的nextbro指向C 结点，

C 的孩子为G，兄弟为D

C→firstchild = G,C→bextbro = D;

D 没有孩子也没有兄弟，

D→firstchild = NULL.D→nextbro = NULL;

E 的孩子为K，没有兄弟

E→firstchild = K，E→nextbro = NULL;

G没有孩子也没有兄弟，

G→firstchild = NULL,G→nextbro = NULL;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

因此，此树在二叉链表中的结构表示为

二叉链表只是用来存储这棵树，但是此树的叶子结点或者度等还是看原来树的结构

例题：

Description

一棵树采用孩子兄弟表示法存储，每个结点的值为一个字母，
要求：
(1)编写算法，输入该树对应的二叉树的先序序列建立二叉链表；
(2)统计并输出该树的叶子结点数。
(3)输出根结点的度。（注意：不是树的度）

Input

该树对应的二叉树的先序序列，空指针位置输入#

Output

叶子点树和根结点的度，以空格分隔。

Sample Input

AB#CD##E###

1
2

Sample Output

3 3
1

#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 100
typedef struct Node {
    int data;
    struct Node* firstchild;
    struct Node* nextbro;
}Tree;
Tree* creatTree()
{
    Tree* T;
    char data;
    data = getchar();
    if (data == '#')
    {
        T = NULL;
    }
    else
    {
        T = (Tree*)malloc(sizeof(Tree));
        T->data = data;
        T->firstchild = creatTree();
        T->nextbro = creatTree();
    }
    return T;
}
 
void preOrder(Tree* T,int *n0)
{
    if (T != NULL)
        {if (T->firstchild == NULL)
            {
                *n0 = *n0 + 1;
            }
        preOrder(T->firstchild, n0);
        preOrder(T->nextbro, n0);
    }
}
void root(Tree* T,int *n)
{
    if (T!= NULL)
    {
        *n = *n+1;
        root(T->nextbro,n);
    }
}
int main()
{
    Tree *T;
    int n0 = 0, n1 = 0, n2 = 0;
    T = creatTree();
    preOrder(T, &n0);
    printf("%d ", n0);
    int n = 0;
    root(T->firstchild, &n);
    printf("%d", n);
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58