数据结构：树与二叉树

1、树的基本概念

1.1树的定义

树是n个结点的有限集。

若n=0，称为空树；若n>0称为非空树，非空树有且仅有一个称之为根的结点。

除根结点以外的其余结点可分成m个互不相交的有限集T1,T2,......Tm,每个有限集合本身又是一棵树，并且称为根的子树。

我们可以根据下面这张图来理解。

根结点：非空树中无前驱结点的结点。图中A就是根结点

结点的度：结点拥有的子树。例如A结点拥有三棵子树，所以它的度为3

深度：树种结点的最大层次，图中的树深度为4

接下来我们介绍各个结点之间的关系：

叶子：也是终端结点，即没有子树的结点

孩子与双亲：一个结点伸出的子树之间的关系

堂/兄弟：同一层次结点的关系

（树的概念可以类比族谱，这样更容易理解）

1.2树的基本术语

树可以分成有序树和无序树：

有序树指的是结点各子树从左至右有序不能互换（例如：二叉树）

无序树中各结点子树可以互换位置。

学习了树的基本知识，下面就引出森林的概念：

如图所示，这是一个再正常不过的树，A是根结点，T1,T2,T3是它的子树。这时如果我们把A结点和B,C,D结点的连接断开，变成下面这个样子，就称为森林：

此时，B,C,D是三棵相互独立的树。

这就是森林，即m棵互不相交的树的集合。

1.3树的其他表示方式

树所包含的逻辑结构还可以用广义表，嵌套集合等形式表示，大家根据图片就可理解。

2、二叉树的基本知识

2.1二叉树的概念

二叉树是一种特殊的树，它只有左子树和右子树。其基本特点如下：

1、结点的度小于等于2

2、是有序树（子树有序，不能颠倒）

我们来看一个例子：具有三个结点的二叉树可能有几种不同形态，普通树呢？

二叉树由于子树有序不能颠倒，所以共有5种形态：

而普通的树是无序的，只用考虑层次，顾只有两种：

 

 2.2二叉树的性质

我们首先介绍两种特殊的二叉树

1、满二叉树：

如图就是一个满二叉树，它具有以下特点：

每层结点数都是最大结点数（每层都满）

叶子结点全部在最底层

每一结点位置都有元素

综上，我们可以很轻松地给出结论，一棵深度为k的满二叉树，它的共有个结点。

2、完全二叉树：

我们设完全二叉树有k层，当k-1层是满二叉树，只有最后一层叶子不满，且全部集中在左边时即称为完全二叉树，如图所示：

那么我们再来辨析以下下面呢几棵树哪个是完全二叉树：

我们给出结果，图1是满二叉树，图三是完全二叉树，其余的都不是。

下面我们介绍二叉树最重要的4条性质：

性质1：在二叉树的第i层至多有个结点

我们可以这样理解：

第一层的结点是根结点，只有一个，所以= 1。

第二层有两个结点，所以=2。

第三层有四个结点，所以=4。

性质2：深度为k的二叉树至多有 个结点

同样，这是一个等比数列求和的问题，第一行为，第二行，如此类推，最终求和结果就是 

性质3：对任意一棵二叉树，如果终端结点数（叶子结点）为0，度为2的结点数为n2，则n0=n2+1

性质4：具有n个节点的完全二叉树深度为⌈log2(n+1)⌉或⌊log2n⌋+1

也可以这样理解-1<n<-1