数据结构--树(定义与存储结构)

时间:2021-08-31 11:54:03

树基本定义

树的定义

数是具有n个节点的有限集。如图即是一个树形结构。

数据结构--树(定义与存储结构)

节点分类

节点的度:一个节点拥有的子节点即成为节点的度,比如A节点,有B和C两个子节点,那么A节点的度=2。

叶节点(终端节点):没有子节点的节点,比如G、H、I....

如图:

数据结构--树(定义与存储结构)

节点间关系

孩子节点:某一个节点的子节点称为孩子节点。比如B、C节点是A节点的孩子节点。

双亲节点:与孩子节点相反。比如,A节点是B、C的双亲节点。

兄弟节点:同一个双亲节点的孩子节点,之间称为兄弟节点。比如,B、C为兄弟节点。

如图:

数据结构--树(定义与存储结构)


树的存储结构


依据博客最上面第一张图进行下面不同表示法的分析。

双亲表示法

双亲的含义我们上面讲述过了。下图中data代表各个节点,parent代表该节点对应双亲的下表地址。

数据结构--树(定义与存储结构)

这种结构对于查找双亲很方便,但是对于查找孩子节点就比较麻烦,需要遍历全树。

孩子表示法

孩子表示法,与双亲表示法恰恰相反,双亲节点记录自己的孩子节点,获取最大的数的度,本图中数的最大度为3,所以如图所示

数据结构--树(定义与存储结构)


双亲孩子表示法

基于孩子表示法演变,如图所示,将双亲表示法与孩子表示法进行了结合。

这样可以很方便的获取到某个节点的双亲节点及孩子节点。

但是对于获取某个几点的兄弟节点,还是要遍历全树。

数据结构--树(定义与存储结构)

孩子兄弟表示法

如图所示,双亲节点记录了,第一个孩子几点,第一个孩子节点记录他的孩子几点及兄弟节点。

数据结构--树(定义与存储结构)

以上各种表示法,根据业务的要求,选择不同的表示法,每种表示法都有自己的优缺点。