数据结构-树(2)

树的存储

树中的每个节点之间都有着不同的关系,如双亲,孩子,兄弟等等,我们在存储一棵树的同时也要把他们之间的关系存储进去。下面我们就要介绍四种表示方法:孩子表示法  双亲表示法   双亲孩子表示法   孩子兄弟表示法

孩子表示法

顾名思义,孩子表示法就是在每一个节点中都包含了它的孩子的信息。比如孩子的地址或者下标。

对于所有的树来说,我们都可以用链式存储,但是我们在定义节点的时候会遇到一个问题,这个节点中我们究竟需要几个指针域?一种方法就是,遍历整棵树,求出最大的度,(不知道度的看上一章),在定义节点的时候定义同样数量的的指针域,但是很明显这样会造成大量浪费。

 

同样我们可以用静态链表,也就是数组的方式来表示,但同样也会造成大量浪费,那有没有什么好的办法呢?当然有,有这么一种看着就很牛逼的方法,数组和链表相结合,虽然也有浪费,但是其实浪费是很少的

数据结构=个体+个体关系,我们要对给定的数据进行存储,其实就是存储这两部分,个体和他们之间的关系,我们把每一个个体存放到数组中,同时又对每一个个体添加了一个链表,来存放它和其它个体的关系,也就是存放它的孩子的下标。

双亲表示法

有孩子表示法自然就有双亲表示法,我们存储的不再是孩子的信息,而是双亲的信息,也就是父节点的下标

双亲孩子表示法

上面的两种方法都有各自的缺点,孩子表示法可以快速的找到它的子节点,但是如果需要寻找父节点则需要遍历整个数组;双亲表示法可以快速找到它的父节点,而要寻找它的孩子,也需要遍历整个数组。所以我们把二者结合一下,诞生了一个新的表示法。

对于孩子节点,第一他需要存放孩子节点的下标,第二它需要存储下一个孩子也就是它的兄弟的地址

//
typedef struct Child
{
 int pos;
 struct Child *next;
}*ChildPtr;
//

对于数组中的元素,第一他需要存储自身的值,第二他需要存储父节点的下标,第三他要存储第一个孩子的地址

//
struct Node
{
 char val;
 int parent;
 ChildPtr pFirst;
};
//

树定义

//
struct Tree{
    Node nodes[100];
    int r,n;//r存放根节点的位置,n存放节点数
};
//

孩子兄弟表示法

也叫二叉树表示法

把一个普通树转化成二叉树来存储,设法保证任意一个节点的左指针域指向它的第一个孩子,右指针域指向它的兄弟。Ps:一个普通的树转化成二叉树,它的根节点一定没有右子树

 

我们来看一下左图上面这棵树是如何变成下面那棵树的。

A   左指针指向它的第一个孩子:B,右指针指向它的兄弟:无

B   第一个孩子:E    它的兄弟:C

C   第一个孩子:无   它的兄弟:D

D   第一个孩子:F    它的兄弟:

F   第一个孩子:无   它的兄弟:G

G   第一个孩子:K    它的兄弟:无

K   第一个孩子:无   它的兄弟:无

H   第一个孩子:无   它的兄弟:I

I     第一个孩子:无   它的兄弟:J

J    第一个孩子:无   它的兄弟 :无

 

我们需要注意一下加粗的那个无,并不是说D真的没有兄弟,BCD之间互为兄弟。我们再看一下兄弟孩子表示法 设法保证任意一个节点的左指针域指向它的第一个孩子,右指针域指向它的兄弟。我们只要设法保证有指针指向它的兄弟即可,并没有要求是那个兄弟,但是出于习惯和常理,我们默认都是指向他右边的第一个兄弟(二叉树是一种有序树,左和右不一样),所以上面的无指的是F右边没有兄弟。

 

在下一篇博客我会讲解一些关于二叉树的东东

 

发表评论

邮箱地址不会被公开。 必填项已用*标注