数据结构--树

前言

​ 树其实这个数据结构在生活种比比皆是，比如家族的族谱，比赛的对战顺序或者自然界当中的看的见的花草树木的根茎。在计算机中，树由称为结点的元素按照层次结构的方式组织而成，层次最顶端称之为根，与根直连接称之为根的子节点，通常子结点的本身也有属于它们自己的子节点，除了根结点外，这个体系结构每一个结点都有唯一的父结点，也就是说只有唯一的与之相连接的上级结点，一个结点拥有多少个子节点取决树的类型，这个量值我们称树的分支因子，它决定了当插入结点时树的分支的扩展的速度。

​ 本文章讨论二叉树，这是一种简单且功能强大的树，树的分支因子值为2。并且在讨论二叉树本文章也会讨论二叉搜索树，这一种专门用于查找操作的二叉树。

二叉树的介绍

​ 二叉树是一种将结点按照树型的层次结构组织起来的数据结构，每一个结点最多只有两个与它相连接的子节点。直接连接在结点下方的结点我们称之为子结点，而直接连接的上级结点我们称之为父结点。结点也可以拥有兄弟，祖先和子孙。类似我们族谱的关系，一个结点的兄弟结点时其父结点的其他子节点，一个结点的子孙结点是其下级的所有结点。而祖先结点是其和根结点路径上的所有结点。为了方便理解我们可以使用下图进行理解。

​ 从上图我们可以总结出一个结点的特征，每个结点都用三个部分组成，一个数据成员和两个左右指针。通过这三个成员的结构体，将每一个结点的左右指针分别指向该结点的子节点，通过这种方式便可以构建一颗二叉树，如果某个结点没有子结点，就将相应的指针设置为NULL。这就可以表示当前结点为叶接点是一个分支的结束、叶子结点是一棵树的边缘，且没有子节点。当有时候我们一次要处理多颗树时，把这些树组成的集合称之为森林。我们把上图树的模型转变为C语言的树模型如下图所示。

树的周游算法

​ 周游一颗二叉树表示按照某种规定的是顺序来依次访问树的每一个结点。同其他链式的数据结构相比较(比如链表)，如何遍历一颗二叉树的结点的方式可能不是很明显，事实上，我们可以采用多种方式来进行树的周游。一般而言，我们会采用四种树的周游算法：先序遍历、中序遍历、后序遍历以及层级遍历。

​ 如果我们引入递归的思维，将一颗树想象为许多更小的树的子集合，那么遍历一颗树就变得相当的简单。

先序遍历

​ 对于一颗树，按照先序遍历的方式，我们首先先访问它的根结点、然后是左子节点，最后是右子节点。由于先序遍历是从左到右遍历各个子树，因此以相同的方式将左子节点和右子节点当做新的子树的根节点就可以通过递归的思维完成先序遍历。

中序遍历

​ 对于一颗树，按照中序遍历的方式，首先先访问左子节点，然后是根结点，最后才是右子节点，由于按照是顺序是从左到右的方式来遍历各个子树，因此以相同的方式将左子节点和右子节点当做新的子树的根。

后序遍历

​ 对于一颗树，按照后序遍历的方式，首先先访问左子节点然后是右子节点，最后才是根结点，由于按照是顺序是从左到右的方式来遍历各个子树，因此以相同的方式将左子节点和右子节点当做新的子树的根。

层级遍历

​ 采用层级遍历的方式来周游一棵树，首先访问树的根，然后向下层处理，按照从左到右的顺序访问每层的结点。层级遍历运用广度优先的策略。后续会开一个章节专门说明广度优先和深度优先的思维。

​ 假设存在一颗树的结构如下：

​ 那么对与这棵树使用不同周游算法访问的顺序是不一样，如下图所示

树的平衡

​ 树的平衡，树的平衡是指在给定结点的数量时，要保证树的高度尽可能的短。这就意味了结点在加入下一层之前必须保证本层的结点是足够满的。换句话说就是树的叶子结点都是在同一层或者叶子结点在最后两层，且倒数第二层是满的。那么可以称这颗树是平衡的。对与平衡树的应用，在后续我会开一章节来进行说明，目前只要知道平衡树这个概念。

例如以下就是一个平衡树

二叉树的接口定义

​

#ifndef __BITREE_H__
#define __BITREE_H__
#include <stdio.h>

/*************************************************************
 * 二叉树结点结构体
*************************************************************/
typedef struct __bitree_node
{
    void *data;            
    struct __bitree_node  *left;
    struct __bitree_node  *right;
}bitree_node_t;

/*************************************************************
 * 二叉树结构体
*************************************************************/
typedef struct __bitree
{
    int  size;
    int  (*compare)(const void *key1, const void *key2);
    void (*destroy)(void *data);
    bitree_node_t *root;
}bitree_t;

/*************************************************************
 * 二叉树函数接口
*************************************************************/
/* 二叉树初始化 */
void bitree_init(bitree_t* tree,  void (*destroy)(void *data));
/* 二叉树析构 */
void bitree_destroy(bitree_t* tree);
/* 二叉树左插 */
int bitree_ins_left(bitree_t* tree, bitree_node_t* node, const void *data);
/* 二叉树右插 */
int bitree_ins_right(bitree_t* tree, bitree_node_t* node, const void *data);
/* 二叉树左结点去除 */
void bitree_rem_left(bitree_t* tree, bitree_node_t* node);
/* 二叉树右结点去除 */
void bitree_rem_right(bitree_t* tree, bitree_node_t* node);
/* 二叉树合并 */
int bitree_rem_merge(bitree_t* merge, bitree_t* left, bitree_t *right, const void *data);

/*************************************************************
 * 宏定义
*************************************************************/
#define BITREE_SIZE(__tree)              ((__tree->size))
#define BITREE_ROOT(__tree)              ((__tree->root))
#define BITREE_IS_ENB(__node)            ((__node == NULL))
#define BITREE_IS_LEAF(__node)           ((__node->left == NULL) && (__node->right == NULL))
#define BITREE_DATA(__node)              ((__node->data))
#define BITREE_LEFT(__node)              ((__node->left))
#define BITREE_RIGHT(__node)             ((__node->right))

#endif /* bitree.h */

二叉树的接口实现

#include "bitree.h"
#include <stdlib.h>
#include <string.h>

void bitree_init(bitree_t* tree,  void (*destroy)(void *data))
{
    /*1 对二叉树进行初始化 */
    tree->size = 0;
    tree->destroy = destroy;
    tree->root = NULL;

    return;
}

void bitree_destroy(bitree_t* tree)
{
    /* 将所有结点移除 */
    bitree_rem_left(tree, NULL);
    memset(tree, 0x00, sizeof(bitree_t));
    return;
}

int bitree_ins_left(bitree_t* tree, bitree_node_t* node, const void *data)
{
    bitree_node_t *new_node;
    bitree_node_t **position;
    /* 如果node == NULL,则插入根节点，在插入根节点前要保证树是空的 */
    if(node == NULL)
    {
        if(BITREE_SIZE(tree) > 0)
        {
            return -1;
        }
        position = &tree->root;
    }
    else
    {
        if(BITREE_LEFT(node) != NULL)
        {
            return -1;
        }
        position = &node->left;
    }
    if((new_node = (bitree_node_t*)malloc(sizeof(bitree_node_t))) == NULL)
    {
        return -1;
    }
    new_node->data = (void*)data;
    new_node->left = NULL;
    new_node->right = NULL;
    *position = new_node;

    tree->size++;
    
    return 0;
}

/* 二叉树右插 */
int bitree_ins_right(bitree_t* tree, bitree_node_t* node, const void *data)
{
    bitree_node_t* new_node;
    bitree_node_t** position;
    /* 如果node == NULL,则插入根节点，在插入根节点前要保证树是空的 */
    if (node == NULL)
    {
        if (BITREE_SIZE(tree) > 0)
        {
            return -1;
        }
        position = &tree->root;
    }
    else
    {
        if (BITREE_LEFT(node) != NULL)
        {
            return -1;
        }
        position = &node->right;
    }
    if ((new_node = (bitree_node_t*)malloc(sizeof(bitree_node_t))) == NULL)
    {
        return -1;
    }
    new_node->data = (void*)data;
    new_node->left = NULL;
    new_node->right = NULL;
    *position = new_node;

    tree->size++;

    return 0;
}

/* 二叉树左结点去除 */
void bitree_rem_left(bitree_t* tree, bitree_node_t* node)
{
    bitree_node_t **position;

    if(BITREE_SIZE(tree) == 0)
    {
        return;
    }

    if(node == NULL)
    {
        position = &tree->root;
    }
    else
    {
        position = &node->left;
    }

    if(*position != NULL)
    {
        bitree_rem_left(tree, *position);
        bitree_rem_right(tree, *position);

        if(tree->destroy != NULL)
        {
            tree->destroy((*position)->data);
        }
        free(*position);
        *position = NULL;
        tree->size--;
    }
}
// /* 二叉树右结点去除 */
void bitree_rem_right(bitree_t* tree, bitree_node_t* node)
{
    bitree_node_t **position;

    if(BITREE_SIZE(tree) == 0)
    {
        return;
    }

    if(node == NULL)
    {
        position = &tree->root;
    }
    else
    {
        position = &node->right;
    }

    if(*position != NULL)
    {
        bitree_rem_left(tree, *position);
        bitree_rem_right(tree, *position);

        if(tree->destroy != NULL)
        {
            tree->destroy((*position)->data);
        }
        free(*position);
        *position = NULL;
        tree->size--;
    }
}
// /* 二叉树合并 */
int bitree_rem_merge(bitree_t* merge, bitree_t* left, bitree_t *right, const void *data)
{
    bitree_init(merge, left->destroy);

    if(bitree_ins_left(merge, NULL, data) != 0)
    {
        bitree_destroy(merge);
        return -1;
    }

    BITREE_ROOT(merge)->left = BITREE_ROOT(left);
    BITREE_ROOT(merge)->right = BITREE_ROOT(right);

    merge->size = merge->size + BITREE_SIZE(left) + BITREE_SIZE(right);

    left->root = NULL;
    left->size = 0;
    right->root = NULL;
    right->size = 0;
    return 0;
}

代码实现分析
待续

本栏目推荐文章
• Jmeter 如何连接mysql数据库？
• SQL Server 检测是不是数字型数据的两种方法
• 如何通过Navicat把MySQL远程数据库导入到本地数据库
• 和利时MACS6通过dat文件实现任意时间范围与测点的历史数据提取与科研分析
• 深入理解spring框架：剖析多线程模式下数据库连接
• 数据可视化是如何帮助大型企业提高效率的？
• redis 数据库
• openpyxl模块--------------------------------重复数据
• Django客户端应用1向服务端应用2发送POST请求并接收解析数据
• 数据可视化是如何帮助我们高效了解数据的？

数据结构 结构 数据数据结构 数据结构 结构 数据 数据结构 算法 结构 数据 数据结构 结构 笔记 数据 数据结构 结构 数据 大学 数据结构 队列 结构 数据 数据结构 结构 代码 数据 数据结构 索引 结构 数据 数据结构 线性 结构 数据 结构 数据结构 数据