数据结构之树的基本概念

1树的定义

树是一种非线性的数据结构，它是若干节点的集合，是由唯一的根和若干个不相交的子树组成的，其中每一棵子树又是一棵树。由此可知，树是可以递归定义的，即在树的定义中又用到了树的定义。需要注意有一个特殊情况，就是树的节点可以为零，这个时候的树就是一棵空树。

如下图：

其中A节点就是根节点，而B、E、K、F、L等节点组成的树就是一棵子树。

2树的基本术语

以上图的树为例：

• 结点：A,B,C,D,E…等都是树的结点，结点不仅包含数据元素，同时也包含指向子树的分支。比如对于根节点A，它有三个子树，所以除了数据元素A，它也包含着三个指向每个子树的指针。
• 结点的度：结点有几个子树它的度就是几。例如A有三个子树，所以A的度就是3。
• 树的度：树中每个结点的度的最大值就是这个树的度。例如上面的树中，A,D有三个子树，这是最多的，所以这个树的度就是3。
• 叶子结点：也叫作终端节点，指度为0，也就是下面没有分支、子树的结点。如F,G,I,J,K,L,M都是叶子结点。
• 非终端结点：也叫分支结点，指度不为0的结点，也就是下面有分支，子树的结点。
• 孩子：结点子树的根，如A的孩子为B,C,D。
• 双亲：与孩子的定义对应，如B、C、D结点的双亲都是A.
• 兄弟：同一个双亲的孩子之间互为兄弟。如B、C、D互为兄弟，因为它们都是A结点的孩子。
• 祖先：从根到某结点的路径上的所有结点，都是这个结点的祖先。如K的祖先是A、B、E,因为从A到K的路径为A->B->E->K。
• 子孙：以某结点为根的子树中的所有结点，都是该结点的子孙。如D的子孙为H、I、J M。
• 层次:从根开始，根为第一层，根的孩子为第二层，根的孩子的孩子为第三层，以此类推。
• 树的高度(或者深度):树中结点的最大层次。如例子中的树共有4层，所以高度为4。
• 结点的深度和高度：
  1.结点的深度是从根结到该结点路径上的结点个数。
  2.从某结点往下走可能到达多个叶子结点，对应了多条通往这些叶子结点的路径，其中最长的那条路径的长度即为该结点在树中的高度，如结点D的高度为3，就是从D到M的路径长度。
  3.根结点的高度为树的高度，如结点A,其高度为4,是从A到K (L、M)这条路径的长度，也是整棵树的高度。
• 堂兄弟：双亲在同一层的结点互为堂兄弟。如G和H互为堂兄弟，因为G的双亲是C,H的双亲是D, C和D在同一层上。注意和兄弟的概念的区分。
• 有序树：树中结点的子树从左到右是有次序的，不能交换，这样的树叫作有序树。
• 无序树:树中结点的子树没有顺序，可以任意交换，这样的树叫作无序树。
• 丰满树:丰满树即理想平衡树，要求除最底层外，其他层都是满的。
• 森林：若干棵互不相交的树的集合。例子中如果把根A去掉，剩下的3棵子树互不相交，它们组成一个森林。

3树的存储结构

3.1顺序存储结构

树的顺序存储结构最直观的是双亲存储结构，用一位数组即可以实现。定义方法就为：

int tree[maxSize];

下面来举一个例子说明一个数组是如何表示一棵树的。

如上图，用数组下标表示树中的结点，数组元素的内容就表示该节点的双亲结点，这样有了结点（下标）以及结点直接的关系（内容），就可以表示一棵树了。比如下标5的内容为3，说明节点5的双亲结点为3；下标1处的结点内容为-1，说明1为根节点。

用这种存储结构来存储树，当知道一个结点后就可以很容易的找到其双亲结点。即已知结点i，那么它的双亲结点就是tree[i]，因此这样的存储方式称为双亲存储结构。

说明:

• 这里介绍的双亲存储结构是一种高度简化的形式，实际应用中一般不会仅是一个整型树组这么简单，可能是一个复杂的结构体数组，结构体内包含了实现实际用途所需要的信息。
• 树的双亲存储结构在克善斯卡尔算法中有重要应用。

3.2树的链式存储结构

树的链式存储结构最常用的有以下两种:
(1)孩子存储结构
孩子存储结构实质上就是图的邻接表存储结构。树就是一种特殊的图，把图中的多对多关系删减为一对多关系即得到树，因此图的存储结构完全可以用来存储树。
(2)孩子兄弟存储结构G
孩子兄弟存储结构与树和森林与二叉树的相互转换关系密切，因此放在树和森林与二叉树的相互转换这一节讲解。

说明:这里讲到的树的双亲存储结构、孩子存储结构和孩子兄弟存储结构在不同的学校试卷中可能出现不同的表述，最严格的表述应该是:

• 树的顺序存储结构的双亲表示法;
• 树的链式存储结构的孩子表示法或孩子兄弟表示法。

最后

以上就是结实砖头为你收集整理的数据结构之树的基本概念的全部内容，希望文章能够帮你解决数据结构之树的基本概念所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。