第二节树的表示方法和存储结构_福建IT网 (FJITW.COM)打造福建电脑销售、资讯、服务一体的平台-IT技术加油站

第二节树的表示方法和存储结构

一、树的表示方法
    树的表示方法一般有两种：
    ⑴ 自然界的树形表示法：用结点和边表示树，例如下图采用的就是自然界的树形表示法。树形表示法一般用于分析问题。
   ⑵ 括号表示法：先将根结点放入一对圆括号中，然后把它的子树按由左而右的顺序放入括号中，而对子树也采用同样方法处理：同层子树与它的根结点用圆括号括起来，同层子树之间用逗号隔开，最后用闭括号括起来。例如下图(b)可写成如下形式（r（a（w，x（d（h），e）），b（f），c（s，t（i（m，o，n），j），u）））

二、树的存储结构
    树的存储结构一般有两种
    1.静态的记录数组
    所有结点存储在一个数组中，数组元素为记录类型，包括数据域和长度为n(n为树的度)的数组，分别存储该结点的每一个儿子的下标。

Const
n=树的度；
max=结点数的上限；
Type
node=record
        data：<数据类型>； {数据域}s
        ch：array[1‥n] of integer；{指向各儿子的下标}
       end；
treetype=array[1..max]of node；
Var
tree：treetype；

该图用静态数组方法保存如右表

下标	数据域 tree[i].data	儿子的下标序列 tree[i].ch
1	r	2	3	4
2	a	5	6	0
3	b	7	0	0
4	c	8	9	10
5	w	0	0	0
6	x	11	12	0
7	f	0	0	0
8	s	0	0	0
9	t	13	14	0
10	u	0	0	0
11	d	15	0	0
12	e	0	0	0
13	i	16	17	18
14	j	0	0	0
15	h	0	0	0
16	m	0	0	0
17	o	0	0	0
18	n	0	0	0

2.动态的多重链表
由于树中结点可以有多个元素，所以可以用多重链表来描述比较方便。所谓多重链表，就是每个结点由数据域和n(n 为树的度)个指针域共n+1个域组成，其表示方法如下：

	Const n=树的度； Type treetype=^node； node=record data：datatype；{数据域} next：array[1‥n] of treetype；{指向各儿子的指针域} end； Var root：treetype；
上图用多重链表表示如下：

频道导航

第二节树的表示方法和存储结构

第二节树的表示方法和存储结构

您可能感兴趣的文章:

第二节 树的表示方法和存储结构

第二节 树的表示方法和存储结构

您可能感兴趣的文章:

第二节树的表示方法和存储结构

第二节树的表示方法和存储结构