数据结构--二叉树的概念与性质

柔光的暖阳◎ 2021-12-22 12:29 282阅读 0赞

### 文章目录 ###

*  概念
 *  二叉树的五种基本形态
 *  性质
 *   *  性质1
     *  性质2
     *   *  推广
     *  性质3
     *   *  推广
     *  性质4
     *  性质5
 *  特殊的二叉树
 *   *  满二叉树
     *  完全二叉树

# 概念 #

二叉树或为空树，或是有一个根节点加上两棵分别称为**左子树**和**右子树**的、互不相交的二叉树组成。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hqYzI1Ng_size_16_color_FFFFFF_t_70]

# 二叉树的五种基本形态 #

image

注：**二叉树不等同于度不大于2的树**，因为若两概念相同，则仅有左子树或仅有右子树的情况就是一种情况。

# 性质 #

## 性质1 ##

在二叉树的第 i i i层上至多有 2 i − 1 2^\{i-1\} 2i−1个节点

![在这里插入图片描述][20190629170650817.png]

## 性质2 ##

深度为 k k k的二叉树上至多含有 2 k − 1 2^k-1 2k−1个节点。  
（至少有k个节点）

证明：

思路就是让每一层都拥有最多的子树，即：  
 2 0 + 2 1 + 2 3 + . . . . . . + 2 k − 1 = 2 k − 1 2^0 + 2^1 + 2^3 + ...... + 2^\{k-1\} = 2^k - 1 20\+21\+23\+......\+2k−1=2k−1

### 推广 ###

满二叉树第 k k k层的节点个数比其第 `1 ~ k-1`层所有的节点多1个。

因为前 k − 1 k-1 k−1层的子树和为 2 0 + 2 1 + 2 3 + . . . . . . + 2 k − 2 = 2 k − 1 2^0 + 2^1 + 2^3 + ...... + 2^\{k-2\} = 2^\{k-1\} 20\+21\+23\+......\+2k−2=2k−1

而第 k k k层的子树有 2 k − 1 2^\{k-1\} 2k−1个。

## 性质3 ##

对任何一个二叉树，若他含有 n 0 n\_0 n0个叶子节点， n 2 n\_2 n2个度为2的节点，则币存在关系式： n 0 = n 2 + 1 n\_0 = n\_2 + 1 n0=n2\+1

证明：

设二叉树上节点总数为： n = n 0 + n 1 + n 2 n = n\_0 + n\_1 + n\_2 n=n0\+n1\+n2

二叉树上的分支总数为： b = n 1 + 2 n 2 b = n\_1 + 2n\_2 b=n1\+2n2

又因为二叉树上的分支总数还可以等于： b = n − 1 = n 0 + n 1 + n 2 − 1 b = n - 1 = n\_0 + n\_1 + n\_2 - 1 b=n−1=n0\+n1\+n2−1

所以即可推出， n 0 = n 2 + 1 n\_0 = n\_2 + 1 n0=n2\+1。

### 推广 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hqYzI1Ng_size_16_color_FFFFFF_t_70 1]

--------------------

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hqYzI1Ng_size_16_color_FFFFFF_t_70 2]

## 性质4 ##

具有 n n n个节点的完全二叉树的深度为 ⌊ l o g 2 n ⌋ + 1 \\lfloor log\_2n \\rfloor +1 ⌊log2n⌋\+1

证明：

设完全二叉树的深度为 k k k

则根据性质2得： 2 k − 1 ≤ n < 2 k 2^\{k-1\} \\le n \\lt 2^k 2k−1≤n<2k，即 k − 1 ≤ l o g 2 n < k k-1 \\le log\_2n \\lt k k−1≤log2n<k

又因为 k k k只能为整数，所以 k = ⌊ l o g 2 n 。 ⌋ + 1 k = \\lfloor log\_2n。 \\rfloor +1 k=⌊log2n。⌋\+1

## 性质5 ##

若对含 n n n个结点的完全二叉树从上到下且从左至右进行 1 至 n n n的编号， 则对完全二叉树中任意一个编号为 i i i的结点:

1.  若 i = 1 i=1 i=1，则该结点是二叉树的根，无双亲， 否则，编号为 ⌊ i / 2 ⌋ \\lfloor i / 2 \\rfloor ⌊i/2⌋的结点为其双亲结点;
2.  若 2 i > n 2i \\gt n 2i>n，则该结点无左孩子，否则，编号为 2 n 2n 2n的结点为其左孩子结点;
3.  若 2 i + 1 > n 2i+1 \\gt n 2i\+1>n，则该结点无右孩子结点，否则，编号为 2 i + 1 2i + 1 2i\+1的结点为其右孩子结点。

# 特殊的二叉树 #

## 满二叉树 ##

深度为 k 且含有 2k-1 个结点的二叉树

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hqYzI1Ng_size_16_color_FFFFFF_t_70 3]

## 完全二叉树 ##

树中所含的 n 个结点和满二叉树中编号为 1 至 n 的结点一一对应。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hqYzI1Ng_size_16_color_FFFFFF_t_70 4]

若完全二叉树有 k k k层，则前 k − 1 k-1 k−1层都是满二叉树，第 k k k层集中在左部。叶节点只会出现在第 k − 1 k-1 k−1层或第 k k k层。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hqYzI1Ng_size_16_color_FFFFFF_t_70]: /images/20211220/f3669d922d014ac58148cdecb46926ca.png
[20190629170650817.png]: /images/20211220/7df96fef536c43cfa07001e03140f452.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hqYzI1Ng_size_16_color_FFFFFF_t_70 1]: /images/20211220/d074f86124114ef486a36af50eaedfaa.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hqYzI1Ng_size_16_color_FFFFFF_t_70 2]: /images/20211220/4031c6372fc44964acf789e6c6217f99.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hqYzI1Ng_size_16_color_FFFFFF_t_70 3]: /images/20211220/519859511b974dacb88b2575fc07b950.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hqYzI1Ng_size_16_color_FFFFFF_t_70 4]: /images/20211220/df955b91df3440178ba78fec1f41d226.png