数据结构----树，二叉树，哈夫曼树相关概念及其实现

树形结构概述

1 分层逻辑结构

所谓的分层逻辑结构，也称为树形逻辑结构关系，是数据结构中的一种逻辑关系结构，在该逻辑结构关系中的数据元素之间满足一对多的逻辑结构关系：

1. 起始数据节点有且仅有一个，没有直接前驱，可以有多个直接后继；

2. 末尾数据节点可以多个，有且仅有一个直接前驱，没有直接后继。

3. 中间节点，有且仅有一个直接前驱，可以多个直接后继。

2 树型结构中的概念

2.1 树的定义

树(Tree)是n(n≥0)节点的有限集合T，它==满足两个条件 ==：

有且仅有一个特定的称为根（Root）的节点；

其余的节点可以分为m(m≥0)个互不相交的有限集合T1、T2、……、Tm，其中每一个集合又是一棵树，并称为其根的子树（Subtree）

2.2 树的表示

树形结构的表示可以使用树形结构表示和目录结构表示

2.3 树的相关术语和基本概念

2.3.1 度数

1. 节点的度数：

   所谓节点的度数，指的是当前节点的直接后继节点(子节点)的个数，称为当前节点的度数。

   实例：

   A节点度数：3；B节点度数：2；C节点度数：1；D节点度数：3；E节点度数2；H节点度数1；

   其余节点（F、G、I、J、K、L、M）度数：0

2. 树的度数：

   树的度数，指的是在树中其所有节点的最大度数，即为当前树的度数。

   树的度数：3

2.3.2 节点分类

1. 树叶

   度数为0的节点称为树叶，也称为终端节点或者叶节点（F、G、I、J、K、L、M）；

2. 分支节点

   度数不为0的节点称为分支节点(A、B、C、D、E、H)；

3. 根节点

   所有节点中的起始节点称为根节点，在一个树中其根节点有且仅有一个(A)，其根节点没有直接前驱。

4. 内部节点

   所谓的内部节点，指的是除根节点之外的所有分支节点称为内部节点(B、C、D、E、H)，其内部节点有且仅有一个直接前驱，至少有一个直接后继。

5. 父节点和子节点

   父节点和子节点是相对的关系，不能单独出现：

   如果某节点存在直接后继节点，此时：

   某节点是所有直接后继节点的父节点；所有的后继节点都是其某结点子节点。

   B节点是A节点的子节点、B节点是E节点(或者F节点)的父节点。

6. 兄弟节点

   兄弟节点是相对关系，不能单独出现：

   如果某多个节点的直接前驱节点是同一个节点，此时的多个节点互为兄弟节点；

   EF节点互为兄弟节点

7. 堂兄弟节点

   位于同一层的多个除掉兄弟节点之外的所有结点称为堂兄弟节点。

2.3.3 路径和边

实例：ABEK是树形结构中的一条路径

相邻的节点之间满足，前者是后者的父节点，后者是前者的子节点；

边数 = 节点数 - 1；

2.3.4 树的高度和深度

树形结构是分层结构，根节点的层数定义为1，其余的节点所在的层数等于父节点层数加一；树的所有节点所在层数最大值即为树的高度，也称为树的深度。

2.3.5 有序树

若树中每个节点及各个子节点的排列为从上到下、从左到右有序，不能交换，即兄弟之间是有序的，则该树称为有序树。一般的树是有序树。

一般的树都是有序。

2.3.6 森林

m（m≥0）棵互不相交的树的集合称为森林。树去掉根节点就成为森林，森林加上一个新的根节点就成为树。

二叉树

1 二叉树的定义

二叉树（Binary Tree）是n（n≥0）个节点的有限集合，它或者是空集（n＝0），或者是由一个根节点以及两棵互不相交的、分别称为左子树和右子树的二叉树组成。二叉树与普通有序树不同，二叉树严格区分左孩子和右孩子，即使只有一个子节点也要区分左右。

2 二叉树的性质

1. 层节点数

2. 总节点数

3. 满二叉树

也可以理解为除了最后一层的其余所有节点的度数均为2的二叉树，称为满二叉树

4. 完全二叉树

只有最下面两层有度数小于2的节点，且最下面一层的叶节点集中在最左边的若干位置上的二叉树，称为完全二叉树。

对于满二叉树是特殊的完全二叉树。

具有n个节点的完全二叉树深度为：

3 完全二叉树的节点逻辑关系

1. 将所构建完全二叉树所有节点从上到下，从左到右依次顺序编号，其根节点编号为1

2. 得到节点之间的逻辑关系

   i为当前节点编号，n为总节点数

   a) 当 i > 1 (根节点之外的其余节点)的节点有父节点，其父节点的编号为i/2；

   b) 当 2i ≤ n 成立，说明编号为i的节点有左孩子，其左孩子节点编号为 2i；

   c) 当 2i+1 ≤ n 成立，说明编号为i的节点有右孩子，其右孩子节点编号为 2i+1；

   d) 当i为奇数且不为1，说明编号为i的节点有左兄弟，其左兄弟节点编号为i-1；

   e) 当i为偶数且<n,说明编号为i的节点有右兄弟，其右兄弟节点编号为i+1.

二叉树的存储

二叉树的存储可以采用顺序存储和链式存储两种方式实现。

1 顺序存储

所谓的顺序存储，指的是在连续存储空间中实现树的所有节点数据的存储，利用顺序存储空间的位置关系表示数据节点之间的逻辑关系。

1.1 顺序存储的思路

1. 将所有存储的二叉树通过添加虚节点的形式构建为完全二叉树。

2. 完全二叉树中的结点从上到下，从左到右依次顺序编号，起始节点(根节点)编号设置为1。

3. 开辟顺序存储空间(可存储数据元素个数 = 最大节点编号 + 1，数据元素数据类型为节点数据类型)；

4. 存储节点数据：将数据元素数据存储在一维数组序号为节点编号位置（第i个节点数据存储在数组的第i个元素位置）。

1.2 具体实例

对于一个有n个节点的完全二叉树，开辟有n+1个元素的一维数组顺序存储，节点号和数组下标一一对应，下标为零的元素不用。

利用以上特性，可以从下标获得节点的逻辑关系。不完全二叉树通过添加虚节点构成完全二叉树，然后用数组存储，这要浪费一些存储空间。

1.3 顺序存储数据类型定义

/* 定义数据节点数据类型 */
typedef unsigned char data_t;

/* 定义树形结构存储空间 */
#if 0
/* 固定数组存储空间存储 */
#define NMEMB 10        /* NMEMB 为节点序号最大值+1 */
data_t data[NMEMB];
#else 
/* 动态数组存储空间存储 */
typedef struct tree {
     data_t *data;      /* 树形结构的数据元素存储空间的起始地址，空间的大小可以按照实际数据元素记录条数动态开辟 */ 
     int nmemb;         /* 动态存储空间的最大数据元素存储个数，由使用者根据实际存储数据编号+1 */
} tree_t;
#endif

typedef unsigned char data_t;

/* 定义树形结构存储空间 */

#if 0

/* 固定数组存储空间存储 */

#define NMEMB 10 /* NMEMB 为节点序号最大值+1 */

data_t data[NMEMB];

#else

/* 动态数组存储空间存储 */

typedef struct tree {

data_t data; / 树形结构的数据元素存储空间的起始地址，空间的大小可以按照实际数据元素记录条数动态开辟 */

int nmemb; /* 动态存储空间的最大数据元素存储个数，由使用者根据实际存储数据编号+1 */

} tree_t;

#endif

2 链式存储

所谓的二叉树的链式存储结构，指的是节点存储数据元素本身同时存储左孩子和右孩子节点存储空间的地址。

2.1 数据类型定义

/* 节点所存储数据元素的数据类型 */
typedef int data_t;

/* 节点数据类型 */
typedef struct btree {
    data_t data;            /* 数据域：存储当前节点数据元素 */
    struct btree *lchild;    /* 左孩子指针域：存储左孩子存储空间地址 */
    struct btree *rchild;    /* 右孩子指针域：存储右孩子存储空间地址 */
} btree_t;

2.2 创建二叉树

创建节点个数为nmemb的完全二叉树

btree_t *CreatebTree(int num, int nmemb)
{
    btree_t *tree;
    
    /* 创建根节点 */
    tree = malloc(sizeof(btree_t));
    if (tree == NULL)
        return NULL;
    memset(tree, 0, sizeof(btree_t));
    
    tree->data = num; /* 设置根节点数据域：当前设置节点编号即为数据值 */
    /* 分别使用递归思路实现左右子树的创建 */
    if ( num*2 <= nmemb ) {
        /* 左孩子存在，左孩子节点编号为 num*2 */
        tree->lchild = CreatebTree(num*2, nmemb);
    } else {
        tree->lchild = NULL;    /* 左孩子不存在 */
    }
    
    if ( num*2+1 <= nmemb ) {
        /* 右孩子存在，右孩子节点编号为 num*2+1 */
        tree->rchild = CreatebTree(num*2+1, nmemb);
    } else {
        tree->rchild = NULL;    /* 右孩子不存在 */
    }
    
    return tree;
}

二叉树的遍历

所谓的二叉树的遍历，指的是沿着某条搜索路径周游二叉树，实现将二叉树中的每一个节点访问且仅访问一次。

对于二叉树的遍历，主要分为递归遍历算法实现和分层遍历算法实现。

1 前中后序列遍历二叉树

在对于二叉树的遍历过程中，如果去掉根节点，左子树和右子树依然是二叉树，可以采用相同的遍历思路实现对左子树和右子树遍历。所以在对于二叉树的遍历可以采用递归遍历算法实现。

1.1 前中后遍历序列

在整个递归遍历序列中，可以根据根节点访问的先后顺序可以将递归遍历分三种序列：

1. 前序遍历

   所谓的前序遍历，也称为先序遍历或者先根遍历。

   具体访问顺序：先访问根节点，在访问左子树、最后访问右子树；

2. 中序遍历

   具体访问顺序：先访问左子树，在访问根节点，最后访问右子树；

3. 后序遍历具体访问顺序：先访问左子树，在访问右子树，最后访问根节点；

​ PS：

1. 序列访问顺序只与根节点访问先后顺序有关，与左右子树访问顺序无关，左右子树的访问一定是先访问左子树，在访问右子树；

2. 在访问序列中：前序和后序可以定根(节点)，中序定左右(节点)；

3. 前序和中序(或者后序和中序)可以得到唯一确定的二叉树，从而推导后序(或者前序)

1.2 递归遍历算法实现

/* 先序遍历 */
void pre_order(btree_t *tree)
{
    if (tree == NULL)
        return;
    printf("%d ", tree->data);    /* 访问根节点数据 */
    pre_order(tree->lchild);    /* 先序访问左子树 */
    pre_order(tree->rchild);    /* 先序访问右子树 */
}

/* 中序遍历 */
void mid_order(btree_t *tree)
{
    if (tree == NULL)
        return;
    mid_order(tree->lchild);        /* 中序访问左子树 */
    printf("%d ", tree->data);    /* 访问根节点数据 */
    mid_order(tree->rchild);        /* 中序访问左子树 */
}

/* 后序遍历 */
void after_order(btree_t *tree)
{
    if (tree == NULL)
        return;
    after_order(tree->lchild);    /* 后序访问左子树 */
    after_order(tree->rchild);    /* 后序访问右子树 */
    printf("%d ", tree->data);    /* 访问根节点数据 */
}

1.3 非递归算法遍历二叉树

可以利用堆栈的思想，实现二叉树的遍历实现，根据根节点访问先后顺序访问。

void PreOrder(btree_t *tree)
{
    /* 根节点类型指针遍历二叉树 */
    btree_t *p;
    
    /* 定义数组作为栈元素存储 */
    btree_t *stack[10];
    int top = -1;    /* 栈顶游标 */

    if (tree == NULL)    /* 根节点不存在，则遍历结束 */
        return;
        
    /* 将根节点入栈 */
    stack[++top] = tree;
    
    /* 判断是栈是否为空 */
    while(top > -1) {
        /* 访问栈中的节点：将栈顶元素出栈 */
        p = stack[top--];
        printf("%d ", p->data);
        
        /* 由于栈的特点是先进后出的特点，访问序列中左子树先于右子树访问，出栈时访问，所有先访问的左子树需要后入栈，后访问的右子树需要先入栈 */
        /* 判断当前访问节点是否存在右孩子，如果存在则将右孩子入栈 */
        if (p->rchild != NULL) {
            stack[++top] = p->rchild;
        }
        
        /* 判断当前访问节点是否存在左孩子，如果存在则将左孩子入栈 */
        if (p->lchild != NULL) {
            stack[++top] = p->lchild;
        }
    }
}

void MidOrder(btree_t *tree)
{
    /* 根节点类型指针遍历二叉树 */
    btree_t *p;
    
    /* 定义数组作为栈元素存储 */
    btree_t *stack[10];
    int top = -1;    /* 栈顶游标 */

    if (tree == NULL)    /* 根节点不存在，则遍历结束 */
        return;
        
    p = tree;    /* 将所访问二叉树的根节点赋值给指针遍历p， */
    
    /* 如果栈不为空说明有节点未访问，或者根节点不为空说明当前节点未访问 */
    while(top > -1 ||  p != NULL) {
        /* 如果是当前节点不为空，则左孩子入栈，直到遇到无左孩子节点 */
        while(p != NULL) {
            stack[++top] = p;    
            p = p->lchild;
        }
        
        /* 栈为非空，取栈顶元素访问 */
        if (top > -1) {
            p = stack[top--];
            printf("%d ", p->data);
            p = p->rchild;        /* 取访问节点的右孩子节点指针 */
        }
    }
}

void AfterOrder(btree_t *tree)
{
    /* 根节点类型指针遍历二叉树 */
    btree_t *p;
    
    /* 定义数组作为栈元素存储 */
    btree_t *stack[10];
    int top = -1;    /* 栈顶游标 */
    
    int flag;

    if (tree == NULL)    /* 根节点不存在，则遍历结束 */
        return;
    
    do {
        /* 将根节点的所有左孩子节点入栈 */
        while(tree != NULL) {
            /* 所有遍历二叉树根节点存在 */
            stack[++top] = tree;
            tree = tree->lchild;        /* 入栈节点的左子树根节点 */
        }
          
        
        p = NULL;
        flag = 1;        /* 表示左子树已经访问或者为空 */
        while(top != -1 && flag == 1) {
            tree = stack[top];
            if (tree->rchild == p) {
                /* 说明右孩子不存在或者右孩子节点已访问,访问子树的根节点 */
                printf("%d ", tree->data);
                top--;
                p = tree;
            } else {
                tree = tree->rchild;
                flag = 0;
            }
        }
    } while(top != -1);
}

2 分层遍历

void COrder(btree_t *tree)
{
    /* 根节点类型指针遍历二叉树 */
    btree_t *p;
    
    if (tree == NULL)
        return;
    
    /* 定义数组作为队列元素存储 */
    btree_t *queue[20];
    int rear = 0;    /* 队尾游标 */
    int front = 0;    /* 队头游标 */
    
    queue[rear++] = tree;        
    
    while(rear != front) {
        p = queue[front++];
        printf("%d ", p->data);
        if (p->lchild != NULL) 
            queue[rear++] = p->lchild;
        if (p->rchild != NULL)
            queue[rear++] = p->rchild;
    }    
}

哈夫曼树

1 哈夫曼树相关概念

1. 权

   在实际的应用过程中，树中的**节点**常常被赋予一个表示某种意义的数值；数值表示为该节点的权值，也称为权。

2. 带权路径长度

   a) 节点的带权路径长度

   ​ 从树的根节点到其它任意叶节点的路径长度(经过的边数) 与 该节点上的权 的乘积，该节点的带权路径长度。

   ​ b) 树的带权路径长度

   ​ 树中所有叶节点的带权路径长度之和 称为 该树的带权路径长度。

3. 哈夫曼树

   在含有n个带权叶节点的二叉树中，其中树的带权路径长度(WPL)最小的二叉树称为哈夫曼树，也称为最优二叉树。

2 哈夫曼树的构建

具体的思路

1. 将所有带权值的节点作为叶节点，并将所有的叶节点按照从小到大(或者从大到下)的顺序构成有序序列；

2. 取权值最小的两个叶节点，创建新节点作为所取的叶节点的父节点，叶节点左孩子权值小于等于右孩子权值。此时的父节点作为新的叶节点，权值等于子节点权值之和。并将新的叶节点顺序插入到有序序列中。

3. 重复步骤2，直到有序序列中的节点数为1，此时的节点即为哈夫曼树的根节点。

注意：最优二叉树可能不唯一，WPL一定是最小。