数据结构-树(2)

2018年1月28日2018年2月3日

树的存储

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

孩子表示法

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

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

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

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

双亲表示法

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

双亲孩子表示法

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

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

//
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右边没有兄弟。

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