树的存储
树中的每个节点之间都有着不同的关系,如双亲,孩子,兄弟等等,我们在存储一棵树的同时也要把他们之间的关系存储进去。下面我们就要介绍四种表示方法:孩子表示法 双亲表示法 双亲孩子表示法 孩子兄弟表示法。
孩子表示法
顾名思义,孩子表示法就是在每一个节点中都包含了它的孩子的信息。比如孩子的地址或者下标。
对于所有的树来说,我们都可以用链式存储,但是我们在定义节点的时候会遇到一个问题,这个节点中我们究竟需要几个指针域?一种方法就是,遍历整棵树,求出最大的度,(不知道度的看上一章),在定义节点的时候定义同样数量的的指针域,但是很明显这样会造成大量浪费。
同样我们可以用静态链表,也就是数组的方式来表示,但同样也会造成大量浪费,那有没有什么好的办法呢?当然有,有这么一种看着就很牛逼的方法,数组和链表相结合,虽然也有浪费,但是其实浪费是很少的
数据结构=个体+个体关系,我们要对给定的数据进行存储,其实就是存储这两部分,个体和他们之间的关系,我们把每一个个体存放到数组中,同时又对每一个个体添加了一个链表,来存放它和其它个体的关系,也就是存放它的孩子的下标。
双亲表示法
有孩子表示法自然就有双亲表示法,我们存储的不再是孩子的信息,而是双亲的信息,也就是父节点的下标
双亲孩子表示法
上面的两种方法都有各自的缺点,孩子表示法可以快速的找到它的子节点,但是如果需要寻找父节点则需要遍历整个数组;双亲表示法可以快速找到它的父节点,而要寻找它的孩子,也需要遍历整个数组。所以我们把二者结合一下,诞生了一个新的表示法。
对于孩子节点,第一他需要存放孩子节点的下标,第二它需要存储下一个孩子也就是它的兄弟的地址
// 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右边没有兄弟。
在下一篇博客我会讲解一些关于二叉树的东东