数据结构——二叉树四种遍历的实现-2

数据结构——二叉树四种遍历的实现-1

https://developer.aliyun.com/article/1507984

2、特殊二叉树

1）斜树

 所有结点都只有左子树的二叉树被称为左斜树。

 所有结点都只有右子树的二叉树被称为右斜树。

 斜树有点类似线性表，所以线性表可以理解为一种特殊形式的树。

2）满二叉树

 对于一棵二叉树，如果它的所有根结点和内部结点都存在左右子树，且所有叶子结点都在同一层，这样的树就是满二叉树。

 满二叉树有如下几个特点：

   1）叶子结点一定在最后一层；

   2）非叶子结点的度为 2；

   3）深度相同的二叉树，满二叉树的结点个数最多，为 （其中 h 代表深度）。

2）完全二叉树

 对一棵具有 n 个结点的二叉树按照层序进行编号，如果编号 i 的结点和同样深度的满二叉树中的编号 i 的结点在二叉树中位置完全相同，则被称为 完全二叉树。

 满二叉树一定是完全二叉树，而完全二叉树则不一定是满二叉树。

 完全二叉树有如下几个特点：

   1）叶子结点只能出现在最下面两层。

   2）最下层的叶子结点一定是集中在左边的连续位置；倒数第二层如果有叶子结点，一定集中在右边的连续位置。

   3）如果某个结点度为 1，则只有左子树，即 不存在只有右子树 的情况。

   4）同样结点数的二叉树，完全二叉树的深度最小。

 如下图所示，就不是一棵完全二叉树，因为 5 号结点没有右子树，但是 6 号结点是有左子树的，不满足上述第 2 点。

3、二叉树的性质

 接下来我们来看下，二叉树有哪些重要的性质。

1）性质1

 【性质1】二叉树的第 i(i≥1) 层上至多有 个结点。

 既然是至多，就只需要考虑满二叉树的情况，对于满二叉树而言，当前层的结点数是上一层的两倍，第一层的结点数为 1，所以第 i 的结点数可以通过等比数列公式计算出来，为 。

2）性质2

 【性质2】深度为 h 的二叉树至多有 结点。

 对于任意一个深度为 h 的二叉树，满二叉树的结点数一定是最多的，所以我们可以拿满二叉树进行计算，它的每一层的结点数为 。

 利用等比数列求和公式，得到总的结点数为：

3）性质3

 【性质3】对于任意一棵二叉树 T，如果叶子结点数为 x0，度为 2 的结点数为 x2，则

x0=x2+1

 令 x1 代表度 为 1 的结点数，总的结点数为 n，则有：

n=x0+x1+x2

 任意一个结点到它孩子结点的连线我们称为这棵树的一条边，对于任意一个非空树而言，边数等于结点数减一，令边数为 e，则有：

e=n−1

对于度为 1 的结点，可以提供 1 条边，如图中的黄色结点；对于度为 2 的结点，可以提供 2 条边，如图中的红色结点。所以边数又可以通过度为 1 和 2 的结点数计算得出：

                               e=x1+2x2 

联立上述三个等式，得到：

                               e=n−1=x0+x1+x2−1=x1+2x2  

化简后，得证：

                               x0=x2+1

4）性质4

 【性质4】具有 n 个结点的完全二叉树的深度为 [log2n]+1。

 由【性质2】可得，深度为 ℎh 的二叉树至多有 个结点。所以，假设一棵树的深度为 h，它的结点数为 n，则必然满足：

由于是完全二叉树，它一定比深度为 ℎ−1h−1 的结点数要多，即：

将上述两个不等式，稍加整理，得到：

然后，对不等式两边取以2为底的对数，得到： 

这里，由于 h 一定是整数，所以有：

三、二叉树的存储和创建

1、顺序表存储

 二叉树的顺序存储就是指利用数组对二叉树进行存储。结点的存储位置即数组下标，能够体现结点之间的逻辑关系，比如父结点和孩子结点之间的关系，左右兄弟结点之间的关系 等等。

1）完全二叉树

 来看一棵完全二叉树，我们对它进行如下存储。

 编号代表了数组下标的绝对位置，映射后如下：

2）非完全二叉树

 对于非完全二叉树，只需要将对应不存在的结点设置为空即可。

 编号代表了数组下标的绝对位置，映射后如下：

3）稀疏二叉树

 对于较为稀疏的二叉树，就会有如下情况出现，这时候如果用这种方式进行存储，就比较浪费内存了。

 编号代表了数组下标的绝对位置，映射后如下：

2、链表存储

 二叉树每个结点至多有两个孩子结点，所以对于每个结点，设置一个 数据域 和 两个 指针域 即可，指针域 分别指向 左孩子结点 和 右孩子结点。

typedef char datatype_bt;
typedef struct btreenode{
  datatype_bt data;
  struct btreenode *lchild；  // 指向左孩子节点
    struct btreenode *rchild;   // 指向右孩子节点
}btree_node,*btree_pnode;

数据结构——二叉树四种遍历的实现-3

https://developer.aliyun.com/article/1507986