数据结构（十一） -- C语言版 -- 树 - 二叉树基本概念

朴灿烈づ我的快乐病毒、 2023-07-24 12:00 2阅读 0赞

### 内容预览 ###

*  零、读前说明
 *  一、二叉树相关概念
 *   *  1.1、定义
     *  1.2、性质
     *  1.3、满二叉树与完全二叉树
     *   *  1.3.1、满二叉树
         *  1.3.2、完全二叉树
         *  1.3.3、特点延伸
 *  二、二叉树储存结构
 *   *  2.1、顺序结构存储
     *  2.2、链式结构存储
     *   *  2.2.1、二叉链表表示法
         *  2.2.2、三叉链表表示法
         *  2.2.3、双亲表示法
 *  三、二叉树的遍历
 *   *  3.1、遍历的说明
     *  3.2、遍历的实质

# 零、读前说明 #

*  本文中所有设计的代码均通过测试，并且在功能性方面均实现应有的功能。
 *  设计的代码并非全部公开，部分无关紧要代码并没有贴出来。
 *  如果你也对此感兴趣、也想测试源码的话，可以私聊我，非常欢迎一起探讨学习。
 *  由于时间、水平、精力有限，文中难免会出现不准确、甚至错误的地方，也很欢迎大佬看见的话批评指正。
 *   嘻嘻。。。。 。。。。。。。。收！

# 一、二叉树相关概念 #

## 1.1、定义 ##

**二叉树 是 n(n≥0) 个节点的有限集合，由一个根节点**以及**两个互不相交的**、分别称为**左子树**和**右子树**的**二叉树**组成。

**二叉树的基本特征为：**

（1）每个节点最多只有两个子树（不存在度大于2的节点）  
  （2）左子树和右子树的次序不能颠倒，是一种有序树

那么对于下图1.1的几种情况，均为合法的二叉树结构/形态。从左到右依次是：左右子树、左子树、右子树、根、空树。

![在这里插入图片描述][20200420135157436.png_pic_center]

图1.1 二叉树的形态

## 1.2、性质 ##

1、在第 **i** 层的节点数目之多有 **2i - 1 \-1** 个，并且在第 **i** 层上至少有 **1** 个节点（叶子节点）。  
  2、深度为i的二叉树，至多有 **2 k  \-1** （k>0）个节点，并且深度为 **i** 是至少有 **i** 个节点。  
  3、对于一个二叉树，若度数为 **2** 的节点数有 **n2** 个，则叶子树（ **n0** ）必定为 **n0 = n2 \+1**个，比如下图1.2所致这样的树。

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

图1.2 二叉树举例

**度数为2的节点有 5 个（A,B,C,D,E）**  
   **那这个的叶子节点有5+1=6个（F,I,G,K,L,M）。**

## 1.3、满二叉树与完全二叉树 ##

### 1.3.1、满二叉树 ###

一个深度为 **k** 且有 **2k \-1** 个节点的二叉树，也就是除了叶子节点，其他的所有节点均有两个子节点（左边、右边）。

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

图1.3 深度为4的满二叉树

### 1.3.2、完全二叉树 ###

1、深度为 **k** 的有 **n** 个节点的**二叉树**，当且仅当其每一个节点斗鱼深度为 **k** 的**满二叉树**中编号**从1到n**的节点一一对应。  
  2、第 **k-1** 层和**满二叉树**一样，最后一层叶子节点尽量靠左，并且左边所有的节点都是**2**。  
  3、**完全二叉树的特点就是，只有最后一层叶子不满，并且集中在左边。**

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

图1.4 完全二叉树、不是完全二叉树

### 1.3.3、特点延伸 ###

对于满二叉树和完全二叉树，还具下面的两个特点。

*  有 **n** 个节点的完全二叉树的深度为 **m = \[ log2n \] + 1**。

比如下面的这个（满）完全二叉树：

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

图1.5 根据节点求深度举例

上图中，其中节点个数为 11，那么根据上面的公式转换为 2x=11, 那么 x 的取值范围大概为 3.3 到 3.4 之间，那么向下取整数的话也就是 **X** 的值为3，所以此完全二叉树的深度为 3 + 1 = 4，与实际也是符合的。

*  **对于完全二叉树**，若从上到下，从左到右的依次编号（从1开始），则编号为 **i** 的节点。其左孩子编号必定为**2i**，其右孩子的编号必定为 **2i+1**，其双亲的编号必定为 **i/2**（如果i=1，则为树根，除外）。

比如下面的这个完全二叉树：

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

图1.6 二叉树编号示意

# 二、二叉树储存结构 #

## 2.1、顺序结构存储 ##

像前面所言，按照二叉树节点的“**从上到下、从左到右**”进行编号，用一组连续的存储单元（数组）进行存储。

**那么对于顺序存储后能否复原成唯一对应的二叉树形状呢？**

1、如果是完全二叉树/满二叉树，根据完全/满二叉树的性质，下标值为**i**的双亲，其左孩子的下标值必定为**2i**，其右孩子的下标值必定为**2i+1**，所以则可以做到唯一的复原。  
  2、如果不是完全二叉树，那么如果要复原将难上加难，那么想要正确、唯一复原的话，那么可以将这个树转换为完全二叉树，将各层空缺处统统补上 **“虚节点” ，内容为空**。

具体效果如图2.1所示。

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

图2.1 补"虚节点“示意图

就像咱们看到的一样，这种情况下存在很多的不足。

（1）空间浪费严重  
    （2）插入、删除等费时费力

## 2.2、链式结构存储 ##

对于链式结构存储，设计不同的节点结构可以构成不同形式的链式存储结构。

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

图2.2 二叉树及存储结构（二叉链、三叉链）

### 2.2.1、二叉链表表示法 ###

一般从根节点开始存储，所以访问树种的节点也只能从根节点开始。

二叉链表表示法的图例如下图2.3所示。

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

图2.3 二叉链表表示法

二叉链表表示法的结构模型如下面的示例代码。

/* 定义二叉树的节点类型 */
    typedef int TElemType;
    
    /* 二叉链表表示法的结构模型 */
    typedef struct BiTNode
    { 
        TElemType data;         /* 节点数据 */
        struct BiTNode *lchild; /* 左孩子 */
        struct BiTNode *rchild; /* 右孩子 */
    } BiTNode, *BiTree;

用下面的简单的代码实现二叉树的创建、初始化等操作，代码示例如下。

1、普通变量表示

/** * 功 能： * 创建并且初始二叉树 - 直接定义 * 参 数： * 无 * 返回值： * 无 **/
    void BiTree_Create_v(void)
    { 
        // 二叉树的节点定义
        BiTNode t1, t2, t3, t4, t5, t6;
        /* 内存初始化为0，这样用"^"表示的区域直接略过不写，就是NULL */
        memset(&t1, 0, sizeof(BiTNode));
        memset(&t2, 0, sizeof(BiTNode));
        memset(&t3, 0, sizeof(BiTNode));
        memset(&t4, 0, sizeof(BiTNode));
        memset(&t5, 0, sizeof(BiTNode));
        memset(&t6, 0, sizeof(BiTNode));
        /* 二叉树的数据初始化 */
        t1.data = 'A';
        t2.data = 'B';
        t3.data = 'C';
        t4.data = 'D';
        t5.data = 'E';
        t6.data = 'F';
        /* 二叉树的关系式的创建 */
        t1.lchild = &t2;
        t1.rchild = &t3;
        t2.lchild = &t4;
        t2.rchild = &t5;
        t3.lchild = &t6;
    
    	printf("%s Finished!\n", __func__);
    }

2、指针表示

/** * 功 能： * 创建并且初始二叉树 - 指针定义 * 参 数： * 无 * 返回值： * 无 **/
    void BiTree_Create_p(void)
    { 
        /* 通过指针的形式创建，下面的两种创建方式一样的 */
    #if 0 
        BiTNode *p1, *p2, *p3, *p4, *p5, *p6;
    #else
        BiTree p1, p2, p3, p4, p5, p6;
    #endif
        p1 = (BiTNode *)malloc(sizeof(BiTNode));
        p2 = (BiTNode *)malloc(sizeof(BiTNode));
        p3 = (BiTNode *)malloc(sizeof(BiTNode));
        p4 = (BiTNode *)malloc(sizeof(BiTNode));
        p5 = (BiTNode *)malloc(sizeof(BiTNode));
        p6 = (BiTNode *)malloc(sizeof(BiTNode));
        memset(p1, 0, sizeof(BiTNode));
        memset(p2, 0, sizeof(BiTNode));
        memset(p3, 0, sizeof(BiTNode));
        memset(p4, 0, sizeof(BiTNode));
        memset(p5, 0, sizeof(BiTNode));
        memset(p6, 0, sizeof(BiTNode));
    
        p1->data = 'A';
        p2->data = 'B';
        p3->data = 'C';
        p4->data = 'D';
        p5->data = 'E';
        p6->data = 'F';
        /* 二叉树的关系式的创建 */
        p1->lchild = p2;
        p1->rchild = p3;
        p2->lchild = p4;
        p2->rchild = p5;
        p3->lchild = p6;
        
    	printf("%s Finished!\n", __func__);
    }

### 2.2.2、三叉链表表示法 ###

在**二叉链表**的基础上，增加一个**双亲域**（直接前驱）指针，那么就可倒查某节点的双亲。  
  三叉链表表示法的图例如下图2.4所示。

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

图2.4 三叉链表表示

三叉链表表示法的结构模型如下面的示例代码。

/* 定义节点的类型 */
    typedef int TElemType;
    
    /* 三叉链表表示法的结构模型 */
    typedef struct TriTNode
    { 
        TElemType data;          /* 节点数据 */
        struct TriTNode *lchild; /* 左孩子 */
        struct TriTNode *rchild; /* 右孩子 */
        struct TriTNode *parent; /* 双亲节点 */
    } TriTNode, *TriTree;

用下面的简单的代码实现三叉链表创建、初始化等操作，代码示例如下。

/** * 功 能： * 创建并且初始三叉树 - 三叉连表示法 * 参 数： * 无 * 返回值： * 无 **/
    void TriTree_Create(void)
    { 
        TriTNode tr1, tr2, tr3, tr4, tr5, tr6;
        /* 内容村初始化为0 */
        memset(&tr1, 0, sizeof(TriTNode));
        memset(&tr2, 0, sizeof(TriTNode));
        memset(&tr3, 0, sizeof(TriTNode));
        memset(&tr4, 0, sizeof(TriTNode));
        memset(&tr5, 0, sizeof(TriTNode));
        memset(&tr6, 0, sizeof(TriTNode));
        tr1.data = 1;
        tr2.data = 2;
        tr3.data = 3;
        tr4.data = 4;
        tr5.data = 5;
        /* 三叉树的关系式的创建 */
        tr1.lchild = &tr2;
        tr1.rchild = &tr3;
        tr2.lchild = &tr4;
        tr2.rchild = &tr5;
        tr2.parent = &tr1;
        tr3.lchild = &tr6;
        tr3.parent = &tr1;
        tr4.parent = &tr2;
        tr5.parent = &tr2;
        tr6.parent = &tr3;
    
        printf("%s Finished!\n", __func__);
    }

### 2.2.3、双亲表示法 ###

在**子节点**中保存了**双亲的位置信息**。由两个表用来表示，分别为**节点表、节点关系表**。双亲表示法的图例如下图2.5所示。

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

图2.5 双亲表示法

双亲表示法的结构模型如下面的示例代码。

/* 定义节点的类型 */
    typedef int TElemType;
    
    /* 双亲表示法的结构模型 */
    #define TREE_SIZE_MAX 20 /* 树的最大容量 */
    
    typedef struct BPTNode
    { 
        TElemType data;    /* 节点数据 */
        int parentPostion; /* 指向双亲的指针 -- 数组的下标 */
        char LRFlag;       /* 左孩子-右孩子 的标志 */
    } BPTNode;
    
    typedef struct BPTree
    { 
        BPTNode nodes[TREE_SIZE_MAX]; /* 保存节点 */
        int nodeCnt;                  /* 节点的数量 */
        int root;                     /* 根节点的位置，保存双亲结点的数组下标 */
    } BPTree;

用下面的简单的代码实现双亲创建、初始化等操作，代码示例如下。

/** * 功 能： * 创建并且初始二叉树 - 双亲表示法 * 参 数： * 无 * 返回值： * 无 * 说 明： * 为了方便标识根节点，parentPostion、LRFlag两个元素全部为0标识根节点，当然您可以随意定义的 **/
    void BPTree_Create(void)
    { 
        BPTree tree;
    
        /* 根节点,使用特殊标识来表示根节点 */
        tree.nodes[0].parentPostion = 0;
        tree.nodes[0].data = 'A';
        tree.nodes[0].LRFlag = 0;
        /* B节点，LRFlag = 1 表示为左孩子节点 */
        tree.nodes[1].parentPostion = 0;
        tree.nodes[1].data = 'B';
        tree.nodes[1].LRFlag = 1;
        /* C节点，LRFlag = 2 表示为右孩子节点 */
        tree.nodes[2].parentPostion = 0;
        tree.nodes[2].data = 'C';
        tree.nodes[2].LRFlag = 2;
        /* D节点 */
        tree.nodes[3].parentPostion = 1;
        tree.nodes[3].data = 'D';
        tree.nodes[3].LRFlag = 1;
        /* E节点 */
        tree.nodes[4].parentPostion = 1;
        tree.nodes[4].data = 'E';
        tree.nodes[4].LRFlag = 2;
        /* F节点 */
        tree.nodes[5].parentPostion = 2;
        tree.nodes[5].data = 'F';
        tree.nodes[5].LRFlag = 1;
    	
    	printf("%s Finished!\n", __func__);
    }

# 三、二叉树的遍历 #

## 3.1、遍历的说明 ##

遍历指的是：从**根节点**出发，按照**某种次序依次访问**二叉树中的**所有节点**，使每个节点**被访问且仅被访问**一次。  
  那么二叉树由根、左子树、右子树组成，定义为D、L、R，那根据排列组合的将会有六种遍历的方法。

**LDR、LRD、DLR、DRL、RDL、RLD**

如果限定先左后右，那就有三种方法：

**DLR** – 先序遍历 ：即先遍历根节点、再遍历左子树、再遍历右子树  
   **LDR** – 中序遍历 ：即遍历先左子树、再遍历根节点、再遍历右子树  
   **LRD** – 后序遍历 ：即遍历先左子树、再遍历右子树、再遍历根节点  
  还有另外一种常用的遍历的方法，  
       层序遍历 ： 即先从上到下，从左到右一层一层进行遍历

注意：  
    1、先中后都是基于根来说的  
    2、先中后的概念是指访问的节点是先于组数出现还是后于子树出现。  
    3、深度遍历的运行过程是先进后出的，自然的方法是栈和递归，包含先序遍历，中序遍历，后续遍历  
    4、广度遍历的运行过程是先进先出的，自然的方法是队列，包含层序遍历

对于同一个树不同遍历的输出不同，下图用一个简单的示例说明。

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

图3.1 二叉树的遍历

## 3.2、遍历的实质 ##

对于树的遍历，如果去掉上面点中的 **printf** 打印语句，那么**先序、中序、后序**遍历逻辑是一样的，只是打印数据的时机不同，**也就是经过的路径是一样的，但是访问的时机不同而已**。

下图用虚线表示出来遍历树的时候的路劲，可以看到树中的每一个节点都会被访问到三次（对于叶子节点的第二次和三次访问可以想象成小乔的一技能。。。）。

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

图3.2 树的遍历的路径表示

好了，关于**二叉树**的基础知识就暂时先写到这儿，那既然你都看到了这儿呢，说明你还是一个**热爱学习的最靓的崽**啦，看在作者我呢写作总结不容易，动动你发财的小手手给**点个赞**啦，要是能**关注一波**那就更好啦！（疯狂暗示的眼神ing…）  
  ![在这里插入图片描述][20200420212952717.jpg_pic_center]

![在这里插入图片描述][20200413132230858.png_pic_center]

啦啦啦，撒花完结！

上一篇：[数据结构（  十  ） – C语言版 – 树 - 基础知识][_ _ _ C_ _ _ -]  
下一篇：[数据结构（十二） – C语言版 – 树 - 二叉树的创建与销毁][_ C_ _ _ -]

[20200420135157436.png_pic_center]: /images/20230528/79c59a1617964dc39514bce87c598656.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poZW1pbmdidWhhbw_size_16_color_FFFFFF_t_70_pic_center]: /images/20230528/5972a2c8f6fb4ff6b9406113da736475.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poZW1pbmdidWhhbw_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20230528/40eb7deff1004dc29295ba43337e7e03.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poZW1pbmdidWhhbw_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20230528/87aba31930684a46b6cef1958ad98620.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poZW1pbmdidWhhbw_size_16_color_FFFFFF_t_70_pic_center 3]: /images/20230528/48211e6ff0ab41959aca181e646b666b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poZW1pbmdidWhhbw_size_16_color_FFFFFF_t_70_pic_center 4]: /images/20230528/75b8115da19241358616496e73d1b1de.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poZW1pbmdidWhhbw_size_16_color_FFFFFF_t_70_pic_center 5]: /images/20230528/7b03fb6ae6274cada915866d0b1b6cef.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poZW1pbmdidWhhbw_size_16_color_FFFFFF_t_70_pic_center 6]: /images/20230528/fc475efd7362469c9ed60d49275b0342.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poZW1pbmdidWhhbw_size_16_color_FFFFFF_t_70_pic_center 7]: /images/20230528/57f52e92f66647e1b2a5bf7b22502613.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poZW1pbmdidWhhbw_size_16_color_FFFFFF_t_70_pic_center 8]: /images/20230528/ebe501aa1f7c4d59a0d0b9dabbffd081.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poZW1pbmdidWhhbw_size_16_color_FFFFFF_t_70_pic_center 9]: /images/20230528/f718f7cd470a4ceb80d275b74a4a8f52.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poZW1pbmdidWhhbw_size_16_color_FFFFFF_t_70_pic_center 10]: /images/20230528/d9c66e74a9184cdf8f8b62a99661788c.png
[20200420212952717.jpg_pic_center]: /images/20230528/f7173747bf8541578e52bdde90ed249f.png
[20200413132230858.png_pic_center]: /images/20230528/69e24e965b1f4065a08a06d4780e139a.png
[_ _ _ C_ _ _ -]: https://blog.csdn.net/zhemingbuhao/article/details/104888752
[_ C_ _ _ -]: https://blog.csdn.net/zhemingbuhao/article/details/105909016