数据结构之二叉树的定义

冷不防 2022-02-12 10:53 332阅读 0赞

### 二叉树 ###

*  定义及其逻辑表示
 *   *   *   *  定义
             *  逻辑表示
 *  性质

# 定义及其逻辑表示 #

#### 定义 ####

一个二叉树是一个有穷的结点集合。这个集合可以为空，若不为空，则它是由根节点和成为其左子树和右子树的两个不相交的二叉树组成。

#### 逻辑表示 ####

下面是二叉树常见的五种基本形态：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0MjU2MjI3_size_16_color_FFFFFF_t_70]

# 性质 #

二叉数的深度小于等于结点数N，可以证明平均深度是O（**√n**）。如图所示，斜二叉树也称为退化二叉树，斜二叉树结构最差，深度达到最大N，它已退化为线性表。在一棵二叉树中，如果所有分支结点都存在左子树和有子树，并且所有叶结点都在同一层上，这样的一棵二叉树称为完美二叉树，也称为满二叉树。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0MjU2MjI3_size_16_color_FFFFFF_t_70 1]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0MjU2MjI3_size_16_color_FFFFFF_t_70 2]  
**1.一个二叉树第 i 层的最大结点数为pow（2，n-1）(n>=1) (这里用c语言的幂函数来表示)**  
**2.深度为 k 的 二叉树 一共有最大结点总数pow（2，n）- 1 ，(n>=1)**  
**3.对于任何的非空二叉树T，若n0表示叶结点的个数，n2是度为2的非叶结点个数，那么两者满足关系 n0 = n2 + 1**  
**4.n1是二叉树中度为1的结点个数，n是总的结点个数，可得公式：n = n0 + n1 + n2**  
**结点数n与边数B满足关系：B = n - 1，而B = n1 + 2 \* n2，所以可得：n0 = n2 + 1**  
**5.根据完全二叉树的性质1可知：具有n个结点的完全二叉树的深度k为（log2 n）+1 取整数**

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0MjU2MjI3_size_16_color_FFFFFF_t_70]: /images/20220212/017b97fd72fe416c808c955edaf04e7c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0MjU2MjI3_size_16_color_FFFFFF_t_70 1]: /images/20220212/cfb94a7c6682421b830b453e537538a8.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0MjU2MjI3_size_16_color_FFFFFF_t_70 2]: /images/20220212/726c8f307f2640d6b70eeae72387e982.png