第 6章 树型结构
树的基本概念
树的遍历
树的线性表示
树类的定义
树的存储结构
6.1 树的基本概念树 是由 n (n≥0) 个结点构成的有限集合,n=0的树称为 空树 ；当 n≠0 时，树中的结点应该满足以下两个条件：
(1) 有且仅有一个特定的结点称之为 根 ；
(2) 其余结点分成 m(m≥0) 个互不相交的有限集合 T1,
T2,…… Tm，其中每一个集合又都是一棵树，称
T1,T2,…… Tm为根结点的 子树 。
B D
E F G
A
H I
J K
C
图 6.1
在树中采用线段连接两个相关联的结点，如 A和 B，
D和 H等。其中 A和 D是上端结点,B和 H是下端结点。称 A、
D分别是 B,H的 双亲 （或 父母 或 前件 ）,B和 H分别为 A
和 D的 子女 （或 孩子 或 后件 ）。显然，双亲和子女的关系是相对而言的。图 6.1中,B是 A的子女，但又是 E和 F
的双亲。由于 E和 F的双亲为同一结点，称 E和 F互为 兄弟 。在任何一棵树中，除根结点外，其它任何一个结点有且仅有一个双亲，有 0个或多个子女，且它的子女恰巧为其子树的根结点。我们将一结点拥有的子女数称为该 结点的度,树中所有结点度的最大值称为 树的度 。图 6.1中,A的度为 3,B的度为 2，而 C的度为 0，整棵树的度为 3。称度为 0的结点为 终端结点 或 叶子结点,
称度不为 0的结点为非 终端结点 或 分支结点 。显然,A、
B,D,H均为分支结点，而 E,F,C,G,J,K,I均为叶子结点。
称树中连接两个结点的线段为 树枝 。在树中，
若从结点 Ki开始沿着树枝自上而下能到达结点 Kj，
则称从 Ki到 Kj存在一条 路径,路径的长度等于所经过的树枝的条数。在图 6.1中，从结点 A到结点 J存在一条路径，路径的长度为 3；从 D到 K也存在一条路径，
路径的长度为 2。仔细观察不难发现，从树根到树中任何一个结点均存在一条路径。
将从树根到某一结点 Ki的路径中 Ki前所经过的所有结点称为 Ki的 祖先 ；反之，以某结点 Ki为根的子树中的任何一个结点都称为 Ki的 子孙 。图 6.1中，
A,D,H均为 J和 K的祖先，而 G,H,I,J和 K均为 D的子孙。
树中 结点的层次,从树根开始定义，根结点为第一层，根的子女结点构成第二层，依次类推，若某结点 Kj位于第 i层，则其子女就位于第 i+1层。称树中结点的最大层次数为树的 深度 或 高度 。图 6.1中，
A结点位于第一层,B,C,D位于第 2层,E,F,G,H
和 I位于第三层等等，整棵树的高度为 4。
若树中任意结点的子树均看成是从左到右有次序的，不能随意交换，则称该树是 有序树 ；否则称之为 无序树 。下图 6.3中的两棵树，若看成是有序树，
它们是不等价的；若看成是无序树，两者相等。
D C
E F
A
B D
E F
A
B
由 m (m≥0) 棵互不相交的树构成的集合称为 森林 。森林和树的概念十分相近，一棵树中每个结点，
其子树的集合即为一个森林；而在森林中的每棵树之上加一个共同的根，森林就成为了一棵树。
C
图 6.3 有序树和无序树的比较树型结构的其他表示方法：
A(B(E,F),C,D(G,H(J,K),I))
(a) 图 6.1的括号表示法
B H
J
KG
I
E F
D
CA
(b)图 6.1的 嵌套集合表示法
A
B
E
F
C
D
G
H
J
K
I
(C)图 6.1的 凹入表示法
6.2 树类的定义
ADT tree {
数据对象 D：具有相同性质的数据元素构成的有限集合。
数据关系 R：如果 D为空或 D仅含一个元素，则 R为空；否则 D中存在一个特殊的结点 root，称之为根结点，其无前驱；其它结点被分成互不相交的 m(m?0)个集合，分别构成 root的 m
棵子树；若这些子树非空，则它们的根结点
rooti均称为整棵树根结点 root的后继结点；
而每棵子树也是一棵树，因而它们中数据元素间的关系也同样满足 R的定义。
树的基本操作如下：
（ 1） Inittree(T)
（ 2） Cleartree(T)
（ 3） Emptytree(T)
（ 4） Root(T)
（ 5） Child(T,a,i)
（ 6） Parent(T,a)
（ 7） Degree(T,a)
（ 8） Depth(T)
（ 9） Choose(T,C)
（ 10） Addchild（ T,a,i,t1）
（ 11） Delchild(T,a,i)
（ 12） Createtree(a,F)
（ 13） Equaltree(T1,T2)
（ 14） Numofnode(T)
（ 15） preorder(T)
（ 16） postorder(T)
（ 17） levelorder(T)
（ 18） Destroytree(T)
} ADT Tree
6.3 树的存储结构根据数据元素之间关系的不同表示方式，常用的树存储结构主要有三种：双亲表示法、孩子表示法和孩子兄弟表示法。
6.3.1 双亲表示法在树中，除根结点没有双亲外，其他每个结点的双亲是唯一确定的。因此，根据树的这种性质，存储树中结点时，可以包含两个信息：结点的值 data和体现结点之间相互关系的属性 __该结点的双亲 parent。
借助于每个结点的这两个信息便可唯一地表示任何一棵树。这种表示方法称为 双亲表示法 。
#define MAXSIZE 100
typedef char datatype; /*结点值的类型 */
typedef struct node /*结点的类型 */
{
datatype data;
int parent; /*结点双亲的下标 */
} node;
typedef struct tree
{
node treelist[MAXSIZE];/*存放结点的数组 */
int length,root ; /* 树中实际所含结点的个数及根结点的位置 */
} tree;
B C D
E F G
A
H
I KJ
data parent
A -1
B 0
C 0
D 0
E 1
F 1
G 3
H 3
I 6
J 6
K 6
0
1
2
3
4
5
6
7
8
9
10
root
(a) 一棵树
(b) (a)图的双亲表示法图 6,4
6.3.2 孩子表示法采用孩子表示法表示一棵树时，树中每个结点除了存储其自身的值之外，还必须指出其所有子女的位置，即整棵树中所有结点的相互关系是通过指明结点子女的位置来体现的，称这种表示法为孩子表示法。
根据子女位置的实现方法不同,孩子表示法分为三种：
指针方式的孩子表示法,数组方式的孩子表示法、
链表方式的孩子表示法 。
1、指针方式的孩子表示法指针方式的孩子表示法中每个结点通常包含两个域：一个是元素的值域 data，另一个为指针数组，数组中的每个元素均为一个指向该结点子女的指针；一棵 m度的树，其指针数组的大小即为 m。
#define m 3 /*树的度数 */
typedef char datatype; /*结点值的类型 */
typedef struct node
{ /*结点的类型 */
datatype data;
struct node *child[m];/*指向子女的指针数组 */
} node,*tree;
tree root;
其中 root表示指向树根结点的指针。
A
B ∧ C ∧ ∧ ∧ D ∧
E ∧ ∧ ∧ F ∧ ∧ ∧ G H ∧ ∧ ∧
I ∧ ∧ ∧ J ∧ ∧ ∧ K ∧ ∧ ∧
root data child[0] child[1] child[2]
图 6.4中 (a)图的指针方式的孩子表示法
2、数组方式的孩子表示法为了查找方便，可以将树中的所有结点存储在一个一维数组中，这样每个结点子女的位置便可以通过数组的下标来体现，称这种孩子表示法为数组方式的孩子表示法。
#define m 3
#define MAXSIZE 20
typedef char datatype;
typedef struct node {
datatype data;
int child[m];
} treenode;
treenode tree[MAXSIZE];
int root ; int length;
data child[0]
A 1
B 4
C -1
D 6
E -1
F -1
G 8
H -1
I -1
J -1
K -1
0
1
2
3
4
5
6
7
8
9
10
child[1] child[2]
2 3
5 -1
-1 -1
7 -1
-1 -1
-1 -1
9 10
-1 -1
-1 -1
-1 -1
-1 -1
root
图 6.4中 (a)图的数组方式的孩子表示法
3、链表方式的孩子表示法在树的链表方式的孩子表示法中，把每个结点的子女排列起来形成一个单链表，这样 n个结点就形成 n个单链表；而 n个单链表的头指针又组成一个线性表，为了查找方便，使用数组加以存储。
# define MAXSIZE 50
typedef char datatype;
typedef struct chnode { /*孩子结点的类型 */
int child;
struct chnode *next;
} chnode,* chpoint;
typedef struct { /* 树中每个结点的类型 */
datatype data;
chpoint firstchild;/*指向第一个子女的指针 */
} node;
typedef struct { /*树的类型 */
node treelist [MAXSIZE];
int length,root；
} tree;
A
B
C ∧
D
E ∧
F ∧
G
H ∧
I ∧
J ∧
K ∧
0
1
2
3
4
5
6
7
8
9
10
child
1 2 3 ∧
4 5 ∧
6 7 ∧
8 9 10 ∧
nextdata firstchild
treelist
root
图 6.4中 (a)图的链表方式的孩子表示法
6.3.3 孩子兄弟表示法所谓孩子兄弟表示法，即在存储树中每个结点时，除了包含该结点值域外，还设置两个指针域
firstchild和 rightsibling，分别指向该结点的第一个子女和其右兄弟，即以二叉链表方式加以存储，
因此该方法也常被称为二叉树表示法。
typedef char datatype;/*树中结点值的类型 */
typedef struct node {/*树中每个结点的类型 */
datatype data;
struct node * firstchild,*rightsibling;
} node,* pnode;
pnode root; /*指向树根结点的指针 */
A ∧
B C ∧ D ∧
E ∧ F ∧ ∧ G H ∧ ∧
I ∧ J ∧ K ∧ ∧
data firstchild rightsibling
root
图 6.4中 (a)图的孩子兄弟表示法
6.4 树的遍历所谓 树的遍历,指按某种规定的顺序访问树中的每一个结点一次，且每个结点仅被访问一次。树的遍历方式分为以下三种：
（ 1）树的 前序遍历,首先访问根结点，再依次按前序遍历的方式访问根结点的每一棵子树。
（ 2）树的 后序遍历,首先按后序遍历的方式访问根结点的每一棵子树，然后再访问根结点。
（ 3）树的 层次遍历,首先访问第一层上的根结点，
然后从左到右依次访问第二层上的所有结点，再以同样的方式访问第三层上的所有结点,……,最后访问树中最低一层的所有结点。
B C D
E F G
A
H I
前序遍历的结果：
ABCEFHIGD
后序遍历的结果：
BEHIFGCDA
层次遍历的结果：
ABCDEFGHI
以下以 指针方式的孩子表示法作为树的存储结构，
分别实现树的各种 遍历算法。
1、树的前序遍历的递归实现
void preorder(tree p) /*p为指向树根结点的指针 */
{
int i;
if (p!=NULL) /*树不为空 */
{
printf("%c",p->data);
for (i=0;i<m;++i)
preorder(p->child[i]);
}
}
2、树的后序遍历的递归实现
void postorder(tree p)
/*p为指向树根结点的指针 */
{
int i;
if (p!=NULL) /*树不为空 */
{
for (i=0;i<m;++i)
postorder(p->child[i]);
printf("%c",p->data);
}
}
3、按前序遍历顺序建立一棵 3度树的递归算法
void createtree (tree *p )
{ int i; char ch;
if ((ch=getchar())= =‘ ’) *p=NULL;
else
{ *p=(tree) malloc (sizeof(node));
/*产生树的根结点 */
(*p)->data=ch;
for (i=0;i<m;++i)
/*按前序遍历顺序依次产生每棵子树 */
createtree(&(*p)->child[i]);
}
}
4、树的层次遍历算法在树的层次遍历过程中，对于某一层上的每个结点被访问后，应立即将其所有子女结点按从左到右的顺序依次保存起来，该层上所有结点的这些子女结点正好构成下一层的所有结点，接下来应该被访问的就是它们。显然，这里用于保存子女结点的数据结构选择队列最合适，队列中的每个元素均为在排队等待访问的结点。
由于树的层次遍历首先访问的是根结点，因此初始时队列中仅包含根结点。只要队列不为空，就意味着还有结点未被访问，遍历就必须继续进行；
每次需访问一个结点时均取队头元素，访问完成后，
若其子女非空，则将其所有子女按顺序依次进队；
不断重复以上过程，直到队列为空。
void levelorder(tree t)
{tree queue[20]; /*存放等待访问的结点队列 */
int f,r,i; /*f,r分别为队头、队尾指针 */
tree p;
f=0; r=0; queue[0]=t;
while (f<=r) /*队列不为空 */
{ p=queue[f]; f++; printf("%c",p->data);
for (i=0;i<m;++i)
if (p->child[i])
{
++r; queue[r]=p->child[i];
}
}
}
6.5 树的线性表示树的线性表示便于树的输入、输出，同时在存储时也比较节省存储空间。本节主要介绍树的两种线性表示方法：括号表示法和层号表示法。
6.5.1 树的括号表示
1,树的括号表示 的规则为：
（ 1）若树 T为空树，则其括号表示为空；
（ 2）若树 T只包含一个结点，则其括号表示即为该结点本身；
（ 3）如果树 T由根结点 A和它的 m棵子树 T1,T2,…… Tm
构成，则其括号表示为：
A(T1的括号表示,T2的括号表示,…… Tm的括号表示 )
其中子树的括号表示同样应该遵循以上规则。
A
B C
F G H
D E
J I
A ( B,C ( F,G,H ),D,E ( J,I ) )
2、树的括号表示具有以下特点：
（ 1）,（,前面的元素一定为某棵树或子树的根结点,
而其所有子树中的结点一定位于该,（,和与之对应的
,）,之间；
（ 2）任何,（,和与之配对的,）,之间的括号表示序列同样满足 (1)中的性质。
图 6,10
3、树的括号表示到树的孩子表示的转换算法
（ 1）从左到右扫描树的括号表示；
（ 2）每当遇到左括号时，其前一个结点进栈，并读下一个符号；
（ 3）每当遇到右括号时，栈顶元素出栈。说明以栈顶元素为根的子树构造完毕，此时若栈为空，
算法结束，否则读下一个符号；
（ 4）每当遇见结点，则它一定为栈顶元素的子女，
将其挂到栈顶元素的某子女位置上，并读下一个符号；
（ 5）每当遇到,,,,则滑过该符号，并读下一个符号。
#define m 3 /* 树的度数 */
#define MAXSIZE 20 /* 树的孩子表示法对应的数组大小 */
#define BMAXSIZE 50 /*树的括号表示对应的数组大小 */
typedef char datatype; /* 树中结点值的类型 */
typedef struct node { /*树的孩子表示法中结点的类型 */
datatype data;
int child[m];
} treenode;
treenode tree[MAXSIZE]; /*树孩子表示法的存储数组 */
int root ; /*根结点的下标 */
int length; /*树中实际所含结点的个数 */
char p[BMAXSIZE]; /*存放树括号表示的数组 */
void bracktotree(char p[],int *root,int *length,treenode tree[])
{ /*将树的括号表示法转换成树的孩子表示法 */
int stack[MAXSIZE]; int top; int i,j,k,l,done;
k=0; j=0; *root=0; top=-1; done=1;
tree[j].data=p[k]; ++k;
for (i=0;i<m;++i) tree[j].child[i]=-1;
while (done)
{ if (p[k]=='(')
{ ++top; stack[top]=j; ++k; }
else if (p[k]==')')
{--top; if (top==-1) done=0; else ++k;}
else if (p[k]==',') ++k;
else { ++j; tree[j].data=p[k];
for (i=0;i<m;++i)
tree[j].child[i]=-1;
l=stack[top]; i=0;
while (tree[l].child[i]!=-1)
++i;
tree[l].child[i]=j; ++k;
}
}
*length=j;
}
6.5.2 树的层号表示设 j为树中的一个结点，若为 j赋予的一个整数值 lev(j)满足以下两个条件：
（ 1）如果结点 i为 j的后件,则 lev(i)>lev(j)；
（ 2）如果结点 i与 j为同一结点的后件，则
lev(i)=lev(j)。
称满足以上条件的整数值 lev(j)为结点 j的层号。
树的层号表示 为：首先根据层号的定义为树中的每个结点规定一个层号，然后按前序遍历的顺序写出树中所有的结点，并在每个结点之前加上其层号即可。
以下是上图中树的两种层号表示：
① 10A,20B,20C,30F,30G,30H,20D,20E,40J,40I
② 1A,2B,2C,5F,5G,5H,2D,2E,3J,3I
A
B C
F G H
D E
J I
树的层号表示到树的扩充孩子表示转换算法：
（ 1）从前往后扫描树的层号表示；
（ 2）若结点 i的层号比其前一个结点 j的层号大，说明结点 i位于结点 j的下一层,且正好为 j的第一个子女；
（ 3）若结点 i的层号与结点 j的层号相等，说明两结点位于同一层，它们拥有共同的双亲；
（ 4）若结点 i的层号比结点 j的层号小，说明结点 i
与结点 j的某个祖先结点互为兄弟，于是应该沿着 j的双亲向树根方向寻找 i的兄弟，从而找到它们共同的双亲。
#define m 3
#define MAXSIZE 20
typedef char datatype;
typedef struct node {
datatype data;
int child[m];
int parent;
} treenode;
typedef struct { /*层号表示法中结点的类型 */
datatype data;
int lev; /*存储结点的层号 */
} levelnode;
treenode tree[MAXSIZE];
int root ;
int length;
levelnode ltree[MAXSIZE];
void leveltotree(int length,levelnode ltree[],
int *root,treenode tree[])
{ /*将树的层号表示法转换成树的扩充孩子表示法 */
int i,j,k;
for (i=0;i<length;++i)
for (j=0;j<m;++j)
tree[i].child[j]=-1;
*root=0; tree[0].data=ltree[0].data;
tree[0].parent=-1;
for (i=1;i<length;++i)
{ tree[i].data=ltree[i].data;
j=i-1;
if (ltree[i].lev>ltree[j].lev)
{
tree[i].parent=j; tree[j].child[0]=i;
}
else {
while (ltree[i].lev<ltree[j].lev)
j=tree[j].parent;
tree[i].parent=tree[j].parent;
j=tree[j].parent;
k=0; /*将结点 i挂到双亲结点上 */
while (tree[j].child[k]!=-1)
++k;
tree[j].child[k]=i;
}
}
}
树的基本概念
树的遍历
树的线性表示
树类的定义
树的存储结构
6.1 树的基本概念树 是由 n (n≥0) 个结点构成的有限集合,n=0的树称为 空树 ；当 n≠0 时，树中的结点应该满足以下两个条件：
(1) 有且仅有一个特定的结点称之为 根 ；
(2) 其余结点分成 m(m≥0) 个互不相交的有限集合 T1,
T2,…… Tm，其中每一个集合又都是一棵树，称
T1,T2,…… Tm为根结点的 子树 。
B D
E F G
A
H I
J K
C
图 6.1
在树中采用线段连接两个相关联的结点，如 A和 B，
D和 H等。其中 A和 D是上端结点,B和 H是下端结点。称 A、
D分别是 B,H的 双亲 （或 父母 或 前件 ）,B和 H分别为 A
和 D的 子女 （或 孩子 或 后件 ）。显然，双亲和子女的关系是相对而言的。图 6.1中,B是 A的子女，但又是 E和 F
的双亲。由于 E和 F的双亲为同一结点，称 E和 F互为 兄弟 。在任何一棵树中，除根结点外，其它任何一个结点有且仅有一个双亲，有 0个或多个子女，且它的子女恰巧为其子树的根结点。我们将一结点拥有的子女数称为该 结点的度,树中所有结点度的最大值称为 树的度 。图 6.1中,A的度为 3,B的度为 2，而 C的度为 0，整棵树的度为 3。称度为 0的结点为 终端结点 或 叶子结点,
称度不为 0的结点为非 终端结点 或 分支结点 。显然,A、
B,D,H均为分支结点，而 E,F,C,G,J,K,I均为叶子结点。
称树中连接两个结点的线段为 树枝 。在树中，
若从结点 Ki开始沿着树枝自上而下能到达结点 Kj，
则称从 Ki到 Kj存在一条 路径,路径的长度等于所经过的树枝的条数。在图 6.1中，从结点 A到结点 J存在一条路径，路径的长度为 3；从 D到 K也存在一条路径，
路径的长度为 2。仔细观察不难发现，从树根到树中任何一个结点均存在一条路径。
将从树根到某一结点 Ki的路径中 Ki前所经过的所有结点称为 Ki的 祖先 ；反之，以某结点 Ki为根的子树中的任何一个结点都称为 Ki的 子孙 。图 6.1中，
A,D,H均为 J和 K的祖先，而 G,H,I,J和 K均为 D的子孙。
树中 结点的层次,从树根开始定义，根结点为第一层，根的子女结点构成第二层，依次类推，若某结点 Kj位于第 i层，则其子女就位于第 i+1层。称树中结点的最大层次数为树的 深度 或 高度 。图 6.1中，
A结点位于第一层,B,C,D位于第 2层,E,F,G,H
和 I位于第三层等等，整棵树的高度为 4。
若树中任意结点的子树均看成是从左到右有次序的，不能随意交换，则称该树是 有序树 ；否则称之为 无序树 。下图 6.3中的两棵树，若看成是有序树，
它们是不等价的；若看成是无序树，两者相等。
D C
E F
A
B D
E F
A
B
由 m (m≥0) 棵互不相交的树构成的集合称为 森林 。森林和树的概念十分相近，一棵树中每个结点，
其子树的集合即为一个森林；而在森林中的每棵树之上加一个共同的根，森林就成为了一棵树。
C
图 6.3 有序树和无序树的比较树型结构的其他表示方法：
A(B(E,F),C,D(G,H(J,K),I))
(a) 图 6.1的括号表示法
B H
J
KG
I
E F
D
CA
(b)图 6.1的 嵌套集合表示法
A
B
E
F
C
D
G
H
J
K
I
(C)图 6.1的 凹入表示法
6.2 树类的定义
ADT tree {
数据对象 D：具有相同性质的数据元素构成的有限集合。
数据关系 R：如果 D为空或 D仅含一个元素，则 R为空；否则 D中存在一个特殊的结点 root，称之为根结点，其无前驱；其它结点被分成互不相交的 m(m?0)个集合，分别构成 root的 m
棵子树；若这些子树非空，则它们的根结点
rooti均称为整棵树根结点 root的后继结点；
而每棵子树也是一棵树，因而它们中数据元素间的关系也同样满足 R的定义。
树的基本操作如下：
（ 1） Inittree(T)
（ 2） Cleartree(T)
（ 3） Emptytree(T)
（ 4） Root(T)
（ 5） Child(T,a,i)
（ 6） Parent(T,a)
（ 7） Degree(T,a)
（ 8） Depth(T)
（ 9） Choose(T,C)
（ 10） Addchild（ T,a,i,t1）
（ 11） Delchild(T,a,i)
（ 12） Createtree(a,F)
（ 13） Equaltree(T1,T2)
（ 14） Numofnode(T)
（ 15） preorder(T)
（ 16） postorder(T)
（ 17） levelorder(T)
（ 18） Destroytree(T)
} ADT Tree
6.3 树的存储结构根据数据元素之间关系的不同表示方式，常用的树存储结构主要有三种：双亲表示法、孩子表示法和孩子兄弟表示法。
6.3.1 双亲表示法在树中，除根结点没有双亲外，其他每个结点的双亲是唯一确定的。因此，根据树的这种性质，存储树中结点时，可以包含两个信息：结点的值 data和体现结点之间相互关系的属性 __该结点的双亲 parent。
借助于每个结点的这两个信息便可唯一地表示任何一棵树。这种表示方法称为 双亲表示法 。
#define MAXSIZE 100
typedef char datatype; /*结点值的类型 */
typedef struct node /*结点的类型 */
{
datatype data;
int parent; /*结点双亲的下标 */
} node;
typedef struct tree
{
node treelist[MAXSIZE];/*存放结点的数组 */
int length,root ; /* 树中实际所含结点的个数及根结点的位置 */
} tree;
B C D
E F G
A
H
I KJ
data parent
A -1
B 0
C 0
D 0
E 1
F 1
G 3
H 3
I 6
J 6
K 6
0
1
2
3
4
5
6
7
8
9
10
root
(a) 一棵树
(b) (a)图的双亲表示法图 6,4
6.3.2 孩子表示法采用孩子表示法表示一棵树时，树中每个结点除了存储其自身的值之外，还必须指出其所有子女的位置，即整棵树中所有结点的相互关系是通过指明结点子女的位置来体现的，称这种表示法为孩子表示法。
根据子女位置的实现方法不同,孩子表示法分为三种：
指针方式的孩子表示法,数组方式的孩子表示法、
链表方式的孩子表示法 。
1、指针方式的孩子表示法指针方式的孩子表示法中每个结点通常包含两个域：一个是元素的值域 data，另一个为指针数组，数组中的每个元素均为一个指向该结点子女的指针；一棵 m度的树，其指针数组的大小即为 m。
#define m 3 /*树的度数 */
typedef char datatype; /*结点值的类型 */
typedef struct node
{ /*结点的类型 */
datatype data;
struct node *child[m];/*指向子女的指针数组 */
} node,*tree;
tree root;
其中 root表示指向树根结点的指针。
A
B ∧ C ∧ ∧ ∧ D ∧
E ∧ ∧ ∧ F ∧ ∧ ∧ G H ∧ ∧ ∧
I ∧ ∧ ∧ J ∧ ∧ ∧ K ∧ ∧ ∧
root data child[0] child[1] child[2]
图 6.4中 (a)图的指针方式的孩子表示法
2、数组方式的孩子表示法为了查找方便，可以将树中的所有结点存储在一个一维数组中，这样每个结点子女的位置便可以通过数组的下标来体现，称这种孩子表示法为数组方式的孩子表示法。
#define m 3
#define MAXSIZE 20
typedef char datatype;
typedef struct node {
datatype data;
int child[m];
} treenode;
treenode tree[MAXSIZE];
int root ; int length;
data child[0]
A 1
B 4
C -1
D 6
E -1
F -1
G 8
H -1
I -1
J -1
K -1
0
1
2
3
4
5
6
7
8
9
10
child[1] child[2]
2 3
5 -1
-1 -1
7 -1
-1 -1
-1 -1
9 10
-1 -1
-1 -1
-1 -1
-1 -1
root
图 6.4中 (a)图的数组方式的孩子表示法
3、链表方式的孩子表示法在树的链表方式的孩子表示法中，把每个结点的子女排列起来形成一个单链表，这样 n个结点就形成 n个单链表；而 n个单链表的头指针又组成一个线性表，为了查找方便，使用数组加以存储。
# define MAXSIZE 50
typedef char datatype;
typedef struct chnode { /*孩子结点的类型 */
int child;
struct chnode *next;
} chnode,* chpoint;
typedef struct { /* 树中每个结点的类型 */
datatype data;
chpoint firstchild;/*指向第一个子女的指针 */
} node;
typedef struct { /*树的类型 */
node treelist [MAXSIZE];
int length,root；
} tree;
A
B
C ∧
D
E ∧
F ∧
G
H ∧
I ∧
J ∧
K ∧
0
1
2
3
4
5
6
7
8
9
10
child
1 2 3 ∧
4 5 ∧
6 7 ∧
8 9 10 ∧
nextdata firstchild
treelist
root
图 6.4中 (a)图的链表方式的孩子表示法
6.3.3 孩子兄弟表示法所谓孩子兄弟表示法，即在存储树中每个结点时，除了包含该结点值域外，还设置两个指针域
firstchild和 rightsibling，分别指向该结点的第一个子女和其右兄弟，即以二叉链表方式加以存储，
因此该方法也常被称为二叉树表示法。
typedef char datatype;/*树中结点值的类型 */
typedef struct node {/*树中每个结点的类型 */
datatype data;
struct node * firstchild,*rightsibling;
} node,* pnode;
pnode root; /*指向树根结点的指针 */
A ∧
B C ∧ D ∧
E ∧ F ∧ ∧ G H ∧ ∧
I ∧ J ∧ K ∧ ∧
data firstchild rightsibling
root
图 6.4中 (a)图的孩子兄弟表示法
6.4 树的遍历所谓 树的遍历,指按某种规定的顺序访问树中的每一个结点一次，且每个结点仅被访问一次。树的遍历方式分为以下三种：
（ 1）树的 前序遍历,首先访问根结点，再依次按前序遍历的方式访问根结点的每一棵子树。
（ 2）树的 后序遍历,首先按后序遍历的方式访问根结点的每一棵子树，然后再访问根结点。
（ 3）树的 层次遍历,首先访问第一层上的根结点，
然后从左到右依次访问第二层上的所有结点，再以同样的方式访问第三层上的所有结点,……,最后访问树中最低一层的所有结点。
B C D
E F G
A
H I
前序遍历的结果：
ABCEFHIGD
后序遍历的结果：
BEHIFGCDA
层次遍历的结果：
ABCDEFGHI
以下以 指针方式的孩子表示法作为树的存储结构，
分别实现树的各种 遍历算法。
1、树的前序遍历的递归实现
void preorder(tree p) /*p为指向树根结点的指针 */
{
int i;
if (p!=NULL) /*树不为空 */
{
printf("%c",p->data);
for (i=0;i<m;++i)
preorder(p->child[i]);
}
}
2、树的后序遍历的递归实现
void postorder(tree p)
/*p为指向树根结点的指针 */
{
int i;
if (p!=NULL) /*树不为空 */
{
for (i=0;i<m;++i)
postorder(p->child[i]);
printf("%c",p->data);
}
}
3、按前序遍历顺序建立一棵 3度树的递归算法
void createtree (tree *p )
{ int i; char ch;
if ((ch=getchar())= =‘ ’) *p=NULL;
else
{ *p=(tree) malloc (sizeof(node));
/*产生树的根结点 */
(*p)->data=ch;
for (i=0;i<m;++i)
/*按前序遍历顺序依次产生每棵子树 */
createtree(&(*p)->child[i]);
}
}
4、树的层次遍历算法在树的层次遍历过程中，对于某一层上的每个结点被访问后，应立即将其所有子女结点按从左到右的顺序依次保存起来，该层上所有结点的这些子女结点正好构成下一层的所有结点，接下来应该被访问的就是它们。显然，这里用于保存子女结点的数据结构选择队列最合适，队列中的每个元素均为在排队等待访问的结点。
由于树的层次遍历首先访问的是根结点，因此初始时队列中仅包含根结点。只要队列不为空，就意味着还有结点未被访问，遍历就必须继续进行；
每次需访问一个结点时均取队头元素，访问完成后，
若其子女非空，则将其所有子女按顺序依次进队；
不断重复以上过程，直到队列为空。
void levelorder(tree t)
{tree queue[20]; /*存放等待访问的结点队列 */
int f,r,i; /*f,r分别为队头、队尾指针 */
tree p;
f=0; r=0; queue[0]=t;
while (f<=r) /*队列不为空 */
{ p=queue[f]; f++; printf("%c",p->data);
for (i=0;i<m;++i)
if (p->child[i])
{
++r; queue[r]=p->child[i];
}
}
}
6.5 树的线性表示树的线性表示便于树的输入、输出，同时在存储时也比较节省存储空间。本节主要介绍树的两种线性表示方法：括号表示法和层号表示法。
6.5.1 树的括号表示
1,树的括号表示 的规则为：
（ 1）若树 T为空树，则其括号表示为空；
（ 2）若树 T只包含一个结点，则其括号表示即为该结点本身；
（ 3）如果树 T由根结点 A和它的 m棵子树 T1,T2,…… Tm
构成，则其括号表示为：
A(T1的括号表示,T2的括号表示,…… Tm的括号表示 )
其中子树的括号表示同样应该遵循以上规则。
A
B C
F G H
D E
J I
A ( B,C ( F,G,H ),D,E ( J,I ) )
2、树的括号表示具有以下特点：
（ 1）,（,前面的元素一定为某棵树或子树的根结点,
而其所有子树中的结点一定位于该,（,和与之对应的
,）,之间；
（ 2）任何,（,和与之配对的,）,之间的括号表示序列同样满足 (1)中的性质。
图 6,10
3、树的括号表示到树的孩子表示的转换算法
（ 1）从左到右扫描树的括号表示；
（ 2）每当遇到左括号时，其前一个结点进栈，并读下一个符号；
（ 3）每当遇到右括号时，栈顶元素出栈。说明以栈顶元素为根的子树构造完毕，此时若栈为空，
算法结束，否则读下一个符号；
（ 4）每当遇见结点，则它一定为栈顶元素的子女，
将其挂到栈顶元素的某子女位置上，并读下一个符号；
（ 5）每当遇到,,,,则滑过该符号，并读下一个符号。
#define m 3 /* 树的度数 */
#define MAXSIZE 20 /* 树的孩子表示法对应的数组大小 */
#define BMAXSIZE 50 /*树的括号表示对应的数组大小 */
typedef char datatype; /* 树中结点值的类型 */
typedef struct node { /*树的孩子表示法中结点的类型 */
datatype data;
int child[m];
} treenode;
treenode tree[MAXSIZE]; /*树孩子表示法的存储数组 */
int root ; /*根结点的下标 */
int length; /*树中实际所含结点的个数 */
char p[BMAXSIZE]; /*存放树括号表示的数组 */
void bracktotree(char p[],int *root,int *length,treenode tree[])
{ /*将树的括号表示法转换成树的孩子表示法 */
int stack[MAXSIZE]; int top; int i,j,k,l,done;
k=0; j=0; *root=0; top=-1; done=1;
tree[j].data=p[k]; ++k;
for (i=0;i<m;++i) tree[j].child[i]=-1;
while (done)
{ if (p[k]=='(')
{ ++top; stack[top]=j; ++k; }
else if (p[k]==')')
{--top; if (top==-1) done=0; else ++k;}
else if (p[k]==',') ++k;
else { ++j; tree[j].data=p[k];
for (i=0;i<m;++i)
tree[j].child[i]=-1;
l=stack[top]; i=0;
while (tree[l].child[i]!=-1)
++i;
tree[l].child[i]=j; ++k;
}
}
*length=j;
}
6.5.2 树的层号表示设 j为树中的一个结点，若为 j赋予的一个整数值 lev(j)满足以下两个条件：
（ 1）如果结点 i为 j的后件,则 lev(i)>lev(j)；
（ 2）如果结点 i与 j为同一结点的后件，则
lev(i)=lev(j)。
称满足以上条件的整数值 lev(j)为结点 j的层号。
树的层号表示 为：首先根据层号的定义为树中的每个结点规定一个层号，然后按前序遍历的顺序写出树中所有的结点，并在每个结点之前加上其层号即可。
以下是上图中树的两种层号表示：
① 10A,20B,20C,30F,30G,30H,20D,20E,40J,40I
② 1A,2B,2C,5F,5G,5H,2D,2E,3J,3I
A
B C
F G H
D E
J I
树的层号表示到树的扩充孩子表示转换算法：
（ 1）从前往后扫描树的层号表示；
（ 2）若结点 i的层号比其前一个结点 j的层号大，说明结点 i位于结点 j的下一层,且正好为 j的第一个子女；
（ 3）若结点 i的层号与结点 j的层号相等，说明两结点位于同一层，它们拥有共同的双亲；
（ 4）若结点 i的层号比结点 j的层号小，说明结点 i
与结点 j的某个祖先结点互为兄弟，于是应该沿着 j的双亲向树根方向寻找 i的兄弟，从而找到它们共同的双亲。
#define m 3
#define MAXSIZE 20
typedef char datatype;
typedef struct node {
datatype data;
int child[m];
int parent;
} treenode;
typedef struct { /*层号表示法中结点的类型 */
datatype data;
int lev; /*存储结点的层号 */
} levelnode;
treenode tree[MAXSIZE];
int root ;
int length;
levelnode ltree[MAXSIZE];
void leveltotree(int length,levelnode ltree[],
int *root,treenode tree[])
{ /*将树的层号表示法转换成树的扩充孩子表示法 */
int i,j,k;
for (i=0;i<length;++i)
for (j=0;j<m;++j)
tree[i].child[j]=-1;
*root=0; tree[0].data=ltree[0].data;
tree[0].parent=-1;
for (i=1;i<length;++i)
{ tree[i].data=ltree[i].data;
j=i-1;
if (ltree[i].lev>ltree[j].lev)
{
tree[i].parent=j; tree[j].child[0]=i;
}
else {
while (ltree[i].lev<ltree[j].lev)
j=tree[j].parent;
tree[i].parent=tree[j].parent;
j=tree[j].parent;
k=0; /*将结点 i挂到双亲结点上 */
while (tree[j].child[k]!=-1)
++k;
tree[j].child[k]=i;
}
}
}
