树与二叉树堆：树

目录

树：

树的概念：

 树的相关概念：

1、结点的度：

2、叶节点：度为0的节点

3、非终端节点或分支节点：

4、父节点和子节点：

5、兄弟节点：

6、树的度：

7、树的层次或则结点的层次：

8、堂兄弟节点：

9、祖先节点：

10、子孙节点：

11、森林：

树的结构与递归：

树与非树的判断：

树的实现： 

树的实际运用：  

---

树：

树的概念：

树是一种非线性的数据结构，它是由n (n>=0)个有限结点组成一个具有层次关系的集合。把它叫做树是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。

• 有一个特殊的结点，称为根结点，根结点没有前驱结点
• 除根结点外，其余结点被分成M(M>0)个互不相交的集合T1、T2、...... Tm，其中每一个集合Ti(1<= i<=m)又是一棵结构与树类似的子树。每棵子树的根结点有且只有一个前驱，可以有0个或多个后继

• 简单来说，树是一种逻辑和物理上都不连续的数据结构 

如图所示，就像是一种树形结构，但是注意！树形结构中，子树之间不能有交集，否则就不是树形结构 

 树的相关概念：

在树的相关概念中，一般使用树和人类情缘关系的概念进行结合描述。

1、结点的度：

一个结点的子节点个数，这个不包括子结点的子节点！

2、叶节点：度为0的节点

3、非终端节点或分支节点：

度不为0的节点，也因此所以树可以分为，根、叶节点、分支节点

4、父节点和子节点：

一个结点既可以是父亲结点也可以是孩子结点

5、兄弟节点：

同一个父节点的节点之间的相互称呼

6、树的度：

就看那个节点的度最大，那么这个节点的度就是所在树的度

7、树的层次或则结点的层次：

树的高度就是树的最大层次、且树的层次一般从1开始。

8、堂兄弟节点：

各自的父节点是兄弟节点

9、祖先节点：

因为没有单指，所以这个节点这条分支上都可以说是他的祖先节点

10、子孙节点：

子孙节点就是该的子节点衍生出去的节点都可以说苏该节点的子孙

11、森林：

多颗不相关不相交的树就叫森林。

树的结构与递归：

              

如图所示，一个树一定是由一个根和多颗子树构成的，子树又可以变为一个根和更小的几个子树构成，直到拆解为叶节点，这种就是递归！ 

树与非树的判断：

以上三者都不是树： 

1. 子树是不相交的
2. 除了根结点外，每个结点有且仅有一个父结点  

树的实现： 

树结构相对线性表就比较复杂了，要存储表示起来就比较麻烦了，既然保存值域，也要保存结点和结点之间的关系，实际中树有很多种表示方式如：双亲表示法，孩子表示法、孩子双亲表示法以及孩子兄弟表示法等。

我们这里就简单的了解其中最常用的孩子兄弟表示法 ，也就是左兄弟又孩子表示法。

• 左孩子是指 指向左边的第一个孩子，右兄弟是指 指向它右边的第一个兄弟 

                                   

所以想要找一个节点的所有的子节点（不包括子节点的子节点），可以通过左孩子，然后在用左孩子的右兄弟开始遍历，一直遍历右兄弟，直到空为止

树的实际运用：  

---