一、树

1.1 树的概念

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

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

如下图:

• 节点的度：一个节点含有的子树的个数称为该节点的度；

上图:A的度为4 B的度为2

• 叶节点或终端节点：度为0的节点称为叶节点；

上图:L、M、N、C、H、I、J、K都是叶节点.

• 非终端节点或分支节点：度不为0的节点；

上图:B、D、F、H、I等都是分支结点(非终端结点).

• 双亲节点或父节点：若一个节点含有子节点，则这个节点称为其子节点的父节点；

上图：A是B的父节点, B是F的父节点

• 孩子节点或子节点：一个节点含有的子树的根节点称为该节点的子节点；

如上图：B是A的孩子节点 F是B的孩子节点

• 兄弟节点：具有相同父节点的节点互称为兄弟节点；

如上图：B、C是兄弟节点 F和G也是兄弟结点 但是G和H可不是兄弟结点哦,他们不是同一个父亲结点.

• 树的度：一棵树中，最大的节点的度称为树的度； 如上图：A的度最大,所以树的度为4

• 节点的层次：用于表示一棵树有多少层.

从根开始定义起，根为第1层，根的子节点为第2层，以此类推；不要和数组下标从0开始搞混了.

• 树的高度或深度：树中节点的最大层次；

如上图：树的高度为4

• 堂兄弟节点：双亲在同一层的节点互为堂兄弟；

如上图：G、H互为堂兄弟节点,他们的父亲结点在同一层.

• 节点的祖先：

从这个结点出发,往上走(父亲结点),直到根节点,这路径的所有结点,都是这个结点的祖先.

例如:M的祖先是F、B、A

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

如上图：所有节点都是A的子孙

• 森林：由m（m>0）棵互不相交的树的集合称为森林.

教大家一个好记的方法,将一棵树的根节点去掉,就是森林了.

1.2 树的表示方法:

很明显,树的结构相对于线性表要复杂很多,想要表示并存储树就显得比较麻烦.要保存每个结点的值,还需要表示树的结构,一般有这些表示方法:

1.双亲表示法:

双亲表示法(了解一下思路即可)

采用顺序表存储,将树每个结点除了存储数据以外,还存储其父亲结点的下标.

由于树中每个结点的父亲是唯一的，所以可以采用父亲数组表示法实现唯一地表示任何一棵树。在这种表示法下，寻找一个结点的父结点只需要O(1)时间。在树中可以从一个结点出发找出一条向上延伸到达其祖先的道路，即从一个结点到其父亲结点，再到其父亲的父亲等其他祖先结点，这就可以求出根结点。

在树的双亲表示法中，对于涉及查询儿子和兄弟信息的树操作，可能要遍历整个数组。为了节省查询时间，可以规定指示儿子的数组下标值大于父亲的数组下标值，(即儿子下面)而指示兄弟结点的数组下标值随着兄弟的从左到右是递增的。(兄弟在边上)

typedef char DataType;
#define  MAX_Node 20
typedef struct NodeType
{
  DataType  data;   //该结点存储的数据
  int Parent;     //该结点的父亲的数组下标,对于根结点,父亲下标设置为-1
}NodeType;
struct TreeType
{
  int NodeCount;          //树的结点个数
  NodeType Node[MAX_Node];  //树结点
};

2.孩子表示法:

孩子表示法(不推荐)

方法1:(个人感觉好low)

每个结点有若干个指针域MistyRose，指向其孩子。由于孩子的数目不一，指针域要创建这棵树的度数个,这样每个树结点的结构一样,但是贼浪费空间.特别是有的树结点的度很大,有的很小的时候.

//了解即可
typedef int DataType;
struct Node
{
  DataType _data; // 结点中的数据域
  struct Node* child1;
  struct Node* child2;
  struct Node* child3;
  //........
};

方法2:

由于是存储儿子结点时浪费空间,我们就可以将儿子结点用链表存储。这种表示法用一个线性表来存储树的所有结点信息，称为结点表。

对每个结点建立一个孩子表。孩子表中只存储孩子结点的地址信息，可以是指针，数组下标。由于每个结点的儿子数目不定，因此儿子表常用单链表来实现。

//了解思想即可
//把每个结点的孩子结点排列起来,以单链表作为存储结构
//n个结点有n个孩子链表,如果是叶子结点此单链表为空
//然后n个头指针又组成一个线性表,采用顺序存储结构,放进一个一维数组
typedef struct Node   //孩子结点
{
  int child;    //孩子
  struct Node * next;
}Node;
typedef struct Box  //表头结构
{
  int data;
  Node * FirstChild;
}Box;
typedef struct Tree
{
  Box nodes[MAXSIZE];
  int r, n;     //根的位置    结点数
}Tree;

3. 孩子兄弟表示法

孩子兄弟表示法:(很不错的表示方法)

即树的左边为孩子,右边为兄弟表示法又称为二叉树表示法或二叉链表表示法。

每个结点除了data域(数据域)外，还含有两个域:

①、最左边的孩子 ②、右边的兄弟

可以用一个小故事来方便我们理解.

由于没有计划生育,一对夫妻生的孩子是没有限制的,孩子太多就很难管理,父母为了解决这个问题,先生第一个孩子,等这个孩子长大一点之后,教这个大儿子(最左边的孩子)帮忙带其他孩子(兄弟).父母只需要关注大儿子就好,找到大儿子,就可以找到其他小儿子们了.

图解:

示例代码:

typedef int DataType;
struct Node
{
struct Node* _firstChild1; // 第一个孩子结点
struct Node* _pNextBrother; // 指向其下一个兄弟结点
DataType _data; // 结点中的数据域
};

树形结构在文件系统中得到了应用:

例如:讲解linux基本指令时,提到了linux的文件系统结构图.

(图片来源于:百度)

二、"二叉树"的基本概念

2.1 二叉树的介绍

如果说"树"是没有计划生育的,那么"二叉树"就是进行了计划生育的父母,一个父亲结点,至多只能有两个孩子,即每个结点的孩子的个数是:0 1 2

各位友友们现实生活中见过二叉树吗?

2.2 特殊的二叉树:

1. 满二叉树：一个二叉树，如果每一个层的结点数都达到最大值(即有两个孩子)，则这个二叉树就是满二叉树。也就是说，如果一个二叉树的层数为k，且结点总数是2k -1，则它就是满二叉树。

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

奇怪的二叉树:

只有左孩子的二叉树:

只有右孩子的二叉树:

2.3 二叉树的性质

1. 若规定根节点所在层数为1，则一棵非空二叉树的第i层上最多有2k 个结点.

当这颗树是满二叉树时,第k层的结点数为最大值,可以参考上面的满二叉树的图,知道一层最多是2k 个结点.

若规定根节点的层数为1，则深度为h的二叉树的最大结点数是2h -1.

对任何一棵二叉树, 如果度为0其叶结点个数为n0 , 度为2的分支结点个数为n2 ,则有n0＝n2＋1 (这个性质划重点)

若规定根节点的层数为1，具有n个结点的满二叉树的深度log2 (n+1)

三、一些经典的练习题:

1.在一棵具有5层的满二叉树中结点总数为_____.

2.根的层次为1，有64个结点的完全二叉树的深度为____.

3.具有100个结点的完全二叉树的深度为______.

4.已知一棵完全二叉树中共有768个结点，则该树中共有_______个叶子结点。

5.在具有 2n 个结点的完全二叉树中，叶子结点个数为_____.

6.某二叉树共有 399 个结点，其中有 199 个度为 2 的结点，则该二叉树中的叶子结点数为_____.

答案:

1. 31

解释:

5层满二叉树的结点个数是25 -1=31个

2. 7

解释:

6层满二叉树的结点个数是26 -1=63,则64个结点是七层的,最后一层只有一个叶子结点的完全二叉树.

3. 7

解释:

6层最多是26 -1=63个结点,而7层最多是27 -1=127,

64<100<127

故深度比6大,深度是7

4. 384

解释:

叶子结点即度为0的结点,总共有768个结点.

5. n

解释:

和上题一个思路, 2n=(n2+1)+n2+n1,此时不难知道(因为n1=0,则n2就不是整数)n1=1,

故n2=n-1,n0=n

6. 200(不解释).