《数据结构》—— 二叉树的定义、种类、性质与存储结构

谁借莪１个温暖的怀抱￠ 2022-09-12 06:45 282阅读 0赞

### 二叉树 ###

*   *  一、二叉树的定义
     *  二、特殊的二叉树
     *   *  2.1 满二叉树
         *  2.2 完全二叉树
         *  2.3 二叉排序树
         *  2.4 平衡二叉树
     *  三、二叉树的性质
     *  四、二叉树的存储结构
     *   *  4.1 顺序存储结构

## 一、二叉树的定义 ##

**二叉树是n（n≥0）个结点的有限集合：**

*  ① 或者为空二叉树，即n = 0。
 *  ② 或者由一个根结点和两个互不相交的被称为根的左子树和右子树组成。左子树和右子树又分别是一棵二叉树。

**特点**：

*  ① 每个结点至多只有两棵子树；
 *  ② 左右子树不能颠倒（二叉树是有序树）。

**二叉树有五种状态：** 空二叉树、只有根节点、只有左子树、只有右子树、左右子树都有。

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

## 二、特殊的二叉树 ##

### 2.1 满二叉树 ###

简单来说就是树的任意结点，左右孩子都是有的（最底层是满的）。满足一棵高度为h，且含有 (2的n次方-1)个结点。对于编号为 i 的结点，双亲为\[i/2\]；左孩子为2i，右孩子为2i+ 1。

### 2.2 完全二叉树 ###

高度为h、有n个结点的二叉树，当且仅当其每个结点都与高度为h的满二叉树中编号为1~n的结点一一对应时，称为完全二叉树。

*  若树的度为1，这个结点只有左孩子，不可能有右孩子；
 *  叶子结点只有在底下最后两层出现；
 *  若n为奇数则每个分支结点都有左孩子和右孩子；
 *  若n为偶数，则编号最大的分支结点(编号为n/2 )只有左孩子，没有右孩子，其余分支结点左、右孩子都有。

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

### 2.3 二叉排序树 ###

二叉排序树。一棵二叉树或者是空二叉树，或者是具有如下性质的二叉树：

*  左子树上所有结点的关键字均小于根结点的关键字；
 *  右子树上所有结点的关键字均大于根结点的关键字；
 *  左子树和右子树又各是一棵二叉排序树；
 *  **二叉排序树可用于元素的排序、搜索。**

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

### 2.4 平衡二叉树 ###

平衡二叉树。树上任一结点的左子树和右子树的深度之差不超过1。**平衡二叉树能有更高的搜索效率。**

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

## 三、二叉树的性质 ##

*  非空二叉树上的叶子结点数等于度为2的结点数加1， 即N0 = N2 + 1；
 *  非空二叉树上第k层上至多有2的(k-1)次方个结点 (k≥1)；
 *  高度为h的二叉树至多有2的(k-1)次方个结点；
 *

**对完全二叉树按从上到下、从左到右的顺序依次编号1, 2, … ,n, 则有以下关系:**

*  ① 当i>1时，结点i的双亲的编号为\[i/2\], 即当i为偶数时，其双亲的编号为i/2， 它是双亲的左孩子；当i为奇数时，其双亲的编号为(i - 1)/2，它是双亲的右孩子。
 *  ② 当 2i ≤ n 时，结点 i 的左孩子编号为 2i，否则无左孩子。
 *  ③ 当 2i+1≤n 时，结点 i 的右孩子编号为 2i+1， 否则无右孩子。
 *  ④ 结点i所在层次(深度)为【log2(n+ 1)】
 *  ⑤ 具有n个(n> 0)结点的完全二叉树的高度为【log2(n+ 1)】或【log2n +1】。

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

## 四、二叉树的存储结构 ##

### 4.1 顺序存储结构 ###

*  用一组地址连续的存储单元依次自上而下、自左至右存储完全二叉树上的结点元素，即将完全二叉树上编号为 i 的结点元素存储在一维数组下标为 i-1 的分量中；
 *  完全二叉树和满叉树采用顺序存储比较合适；
 *  一般的二叉树，为了能反映二叉树中结点之间的逻辑关系，只能添加并不存在的空结点，让其每个结点与完全二叉树上的结点相对照，再存储到一维数组的相应分量中；
 *  由于顺序存储的空间利用率较低，因此二叉树一般都采用链式存储结构，用链表结点来存储二叉树中的每个结点。

//二叉树的链式存储结构:
    struct ElemType{
        
    	int value;
    };
    
    typedef struct BiTNode {
        
    	ElemType data;	//数据域
    	struct BiTNode *lchild, *rchild;  //左，右孩子指针
    } BiTNode; *BiTree;
    
    //定义一棵空树
    BiTree root = NULL;
    //插入根节点
    root = (BiTree)malloc(sizeof(BiTNode));
    root->data = {
        1};
    root->lchild = NULL; .
    root->rchild = NULL; .
    
    //插入新节点
    BiTNode *p = (BiTree)malloc(sizeof(BiTNode));
    p->data = {
        2};
    p->lchild = NULL;
    p->rchild = NULL;
    root->lchild = p;
    
    //插入新节点
    BiTNode *q = (BiTree)malloc(sizeof(BiTNode));
    q->data = {
        3};
    q->lchild = NULL;
    q->rchild = NULL;
    root->rchild = q;

n个结点的二叉链表共有 n+1 个空链域。

找到指定结点p的左/右孩子不难；找到指定结点p的父结点，只能从根开始遍历寻找。  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5ZSQ5qi9_size_18_color_FFFFFF_t_70_g_se_x_16]

[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5ZSQ5qi9_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/d3ee579724b744cc8768350ea63b6b58.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5ZSQ5qi9_size_20_color_FFFFFF_t_70_g_se_x_16 1]: /images/20220828/71823666891a4f529f4f2861bbf5583d.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5ZSQ5qi9_size_20_color_FFFFFF_t_70_g_se_x_16 2]: /images/20220828/0852087ac41d42bc891801e8d12646d2.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5ZSQ5qi9_size_18_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/77fcf82ed0ce415cb396c24a1afb4812.png