数据结构之二叉树的基本介绍（一）

墨蓝 2022-05-25 05:15 191阅读 0赞

### 1.0 二叉树的特点 ###

1.  每个节点最多有两个子树 就是度为 0 - 2
2.  二叉树是有序的  
    左边的树叫左子树，右边的树叫右子树，即使只有一个子树，也要分出他是左子树还是右子树![这里写图片描述][70]

为什么说二叉树和树是两种数据结构呢？就是因为二叉树是有序的这个原因

### 2.0 几种特殊的二叉树 ###

#### 2.1 斜树 ####

只有左子树或者只有右子树  
![这里写图片描述][70 1]

#### 2.2 满二叉树 ####

满二叉树就是所有分支结点都存在左右子树，所有的叶子结点都在同一层上  
特点是

1.  度只为0 或者只为2
2.  所有叶子结点只能在最下层

*不会画图是硬伤*  
![这里写图片描述][70 2]

#### 2.3 完全二叉树 ####

给上面的满二叉树编号，从左到右，从上到下顺序编号 如图5-15（a）  
然后在给另一个二叉树编号，如果这个二叉树的第i个编号和满二叉树的第i个编号位置一样 则就是完全二叉树  
![这里写图片描述][70 3]

### 3.0 二叉树的性质 ###

1.  二叉树的第i层上最多有 2i−1  2 i − 1 个结点
2.  在深度为k的二叉树中，最多有2k−1  2 k − 1 个结点
3.  在一科二叉树中，如果叶子结点的个数是n0  n 0 ,度为2的结点个数为n2  n 2  则 n0  n 0  = n2  n 2 \+1 这个上面那两个明白这个就ok
4.  具有n个结点的完全二叉树的深度为⌊log2n⌋  ⌊ l o g 2 n ⌋  这个也很好理解吗 就是对第2条性质的取对数呗
5.  对于一个完全二叉树开始从1编号，  
    
    
    1.  .对于i>1的元素 则它的双亲结点是 ⌊i/2⌋  ⌊ i / 2 ⌋ 
    2.  如果2\*i <= n 那么结点i的左孩子为 2i 否则的话没有左孩子
    3.  如果2\*i +1 <= n 那么结点i的右孩子为 2i +1 否则的话没有右孩子

[70]: /images/20220525/f889acca6cff410ab88185a49e3683d9.png
[70 1]: /images/20220525/e041c841566b47b6bd39a486f5acb170.png
[70 2]: /images/20220525/29a5eb4a812c43ada5ca718c27a4d69b.png
[70 3]: /images/20220525/cbdbfd111a754c309a756b57eaee69e8.png