树的概念及结构

树的概念

树是一种非线性的数据结构，它是由n(n>=0)个有限结点组成的一个具有层次关系的集合。把它叫做树。

树的特点

有一个特殊结点，称为根结点，根结点没有前驱结点。

除根结点外，其余结点被分成M(M>0)互不相交的集合T1,T2,,,Tm，其中每一个集合Ti(1<=i<=m)又是一颗结构与树类似的子树。

每棵子树的根结点有且仅有一个前驱，可以有0个或多个后继。

因此，树是递归定义的。

树中专有名词

节点的度:一个节点含有的子树的个数称为该节点的度。

叶节点(终端节点):度为0的结点称为叶节点。

非终端节点(分支节点):度不为0的节点。

父节点(双亲节点):若一个节点含有子节点，则这个节点称为其子节点的父节点。

子节点(孩子节点):一个结点含有的子树的根节点称为该节点的子节点。

兄弟节点:具有相同父节点的节点互称为兄弟节点。

树的度:一棵树中，最大的节点的度称为树的度。

节点的层次:从根开始定义起，根为第一层，根的子节点为第二层，以此类推。

树的高度(深度):树中结点的最大层次。

堂兄弟节点:双亲在同一层的节点互称为堂兄弟节点。

节点的祖先:从根到该节点所经分支上的所有节点。

子孙:以某节点为根的子树中任一节点都称为该节点的子孙。

森林:由m(m>0)棵互不相交的树组成的集合称为森林。

树的表示

树结构相对于线性表就比较复杂了，要存储和表示起来就比较麻烦了，实际中树有很多种表示方法。如:双亲表示法，孩子表示法，孩子兄弟表示法等等。其中最常用的是左孩子右兄弟表示法。

左孩子右兄弟表示法中，所定义的节点类型大致是这样的:

typedef int DataType
struct Node
{
  struct Node* firstChild;   //第一个孩子结点
  struct Node* nextBrother;  //指向下一个兄弟结点
  DataType data;             //结点中的数据域
};

对于任意树，我们都可以用左孩子右兄弟法访问到树中的每一个节点:

二叉树的概念及其重要性质

二叉树的概念

二叉树是n个有限元素的集合，该集合或者为空、或者由一个称为根（root）的元素及两个不相交的、被分别称为左子树和右子树的二叉树组成，是有序树。当集合为空时，称该二叉树为空二叉树。在二叉树中，一个元素也称作一个结点。

二叉树的特点：

 每个结点最多有两棵子树，即二叉树不存在度大于2的结点。

 二叉树的子树有左右之分，其子树的次序不能颠倒。

数据结构中的二叉树

特殊的二叉树

满二叉树:一个二叉树，如果每一层的节点数都达到最大值，则这个二叉树就是满二叉树。也就是说，如果一个二叉树的层数为k,且节点总数是2^k-1,则它就是满二叉树。

完全二叉树:完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而引出来的。对于深度为k，有n个节点的二叉树，当且仅当其每一个节点都与深度为k的满二叉树中编号从1至n的节点一一对应时称之为完全二叉树，要注意的是满二叉树是一种特殊的完全二叉树。

总结:

满二叉树:若树的深度为k,那么它的每一层的节点都必须是满的。

完全二叉树:若树的深度为k,那么它的前k-1层的节点必须都是满的，第k层的节点数可以不是满的但必须是从左到右的。

二叉树的性质

性质一:若规定根节点的层数为1，则一课非空二叉树的第i层上最多有2^(i-1)个节点。

性质二:若规定根节点的层数为1，则深度为h的二叉树最大节点数为2^h-1个。

例题1:一棵完全二叉树的结点数为531，那么这棵树的高度为（ ）。

假设该完全二叉树的层数为K，则该完全二叉树的前K-1层的结点总数为2K-1-1，若该完全二叉树是满二叉树，则该满二叉树的结点总数为2K-1，所以深度为K的完全二叉树的结点总数范围为：2K-1-1 < N <= 2K-1。因为29 < 531 <= 210，所以该完全二叉树的高度为10。

性质三: 对任何一课二叉树，如果度为0的叶结点个数为n0,度为2的分支结点个数为n2,则有n0=n2+1;

例题1:某二叉树共有399个结点，其中199个度为2的结点，则该二叉树中的叶子结点数为（ ）。

根据性质三，叶子结点（度为0）的个数200个，由于199+200 = 399（该二叉树的总结点数），所以该二叉树的叶子结点数为200。

例题2:在具有2n个结点的完全二叉树中叶子结点个数为（ ）。

根据性质三，度为0的结点数和度为2的结点数之和应为奇数，因为该完全二叉树的结点总数为2n（偶数），所以二叉树中必然存在一个度为1的结点。于是可以推出：度为0的结点和度为2的结点总共有2n-1个。性质三：对任何一棵二叉树，度为0的叶结点个数比度为2的分支结点个数多1，所以该二叉树度为1的结点个数为n-1，度为0的结点数（即叶结点数）为n。

性质四:若规定根节点的层数为1，则具有n个节点的满二叉树的深度为h = log2(N+1)。

二叉树的存储结构

顺序结构

 顺序结构存储就是使用数组来存储，一般使用数组只适合表示完全二叉树，因为不是完全二叉树会有空间的浪费。而现实生活中只有堆（一种二叉树）才会使用数组来存储。二叉树的顺序存储在物理上是一个数组，在逻辑上是一棵二叉树。

链式结构

二叉树的链式存储结构是指，用链表来表示一棵二叉树，即用链来指示元素之间的逻辑关系。通常的方法是链表中每个结点由三个域组成，数据域和左右指针域，左右指针分别用来存储该结点左孩子和右孩子所在的结点的地址。

 链式结构又分为二叉链和三叉链，之后我们会用二叉链来实现二叉树的链式存储结构，三叉链运用于更高阶的数据结构，例如红黑树。