树的原理与应用

1.树的定义

        在日常生活中，很多数据的组织形式本质上是一颗数，树是一种非线性结构，其数学定义为：
        如果一组数据中除了根节点以外，其余的任意节点有且仅有一个前驱节点，有零个或若干个后继节点，这样的数据结构被称作数，数中的节点的逻辑关系是一对多的。

        数也是数据结构的一种，数的本质是多个节点的有限集，当n = 0时，树被称为空树，任何一个n不等于0的非空树中均有且只有一个特殊的节点，这个节点称为根结点，当n大于1时，其余结构也可以被划分为m(m大于1）个有限集，每个集合也被称为一颗树，也叫子树。

        一般把一个节点拥有的子树的数量称为结点的度，把度为0的结点称为叶子节点，不为0的为分支结点。也就是说，除了叶子结点外，其他的节点都是分支结点。同时，一般把树的最大层数被称为树的深度，也叫做树的高度。

2.二叉树

        二叉树是一种特殊的树状结构，其每个节点最多有两个子节点（每个节点的度不会超过2），并且二叉树的子节点有左右之分，分别叫做左节点和右节点，并且二叉树的子树是有次序的，不能随意更改，所以二叉树也属于有序树。

        一般只有左子树的二叉树被称为左斜树，只有右斜树的二叉树叫做右斜树。但是斜树被退化成了链式结构，没有体现二叉树的性能。

        一颗高度为h的二叉树，如果它的结点数为2^h-1，那么这个树被称为满二叉树。满二叉树的所有结点的度都是2，也就是每个结点都有左子树和右子树，满二叉树的子节点数量是最多的，另外，叶子结点都集中在最下面一层。

        除了最下面一层，其他的所有层的度都为2，并且叶子结点全部靠左连续分布，不能出现间断，这种树被称为完全二叉树。

        上图所示的二叉树的叶结点是间断的而非连续的，故其不是完全二叉树。

3.二叉树的遍历

        二叉树的遍历有三种遍历方式，分别是前序遍历前序遍历、中序遍历以及后序遍历，分别对应根节点第一个遍历、第二个遍历以及第三个遍历，左右结点都是先左结点后右结点

        前序遍历：根节点→左子树→右子树（根左右）
        中序遍历：左子树→根节点→右子树（左根右）
        后序遍历：左子树→右子树→根节点（左右根）

4.二叉搜索树

        二叉搜索树也是二叉树的一种，其特征是左节点的序号比父结点小，右结点比父节点大。根据这个特性，如果需要在搜索二叉树中找到某个key的数据，假设搜索二叉树的高度为h，二叉树最大存储数据n = 2^h-1，如果需要检索一个数据，最大检索次数为h次，故在理想状态下，二叉搜索树检索数据、插入数据、删除数据的时间复杂度为O(logn)

         但是，如果写入二叉树的数据的键值是顺序的，例如依次写入1、2、3、4、5、6，那么二叉树将退化为链表，此时最坏搜索次数的时间复杂度为O(n)。

        采用C实现二叉搜索树，对于二叉搜索树，单个结点需要保存的数据包括左子树结点、右子树结点地址，通常情况下不需要父结点地址，但是如果需要进行优化，可以考虑引入父结点来实现红黑树（二叉搜索树的优化的一种，通过自动调整机制防止二叉搜索树退化，具体见后文）

typedef struct _bstree{
    struct _bstree* parent;
    struct _bstree* left_son;
    struct _bstree* right_son;
    void* data;
    int key;
} bstree;

        parent存储父结点地址，left_son和right_son分别存储左右子树地址，data存储数据地址，key存储键值。通过各个结点的组合，形成二叉搜索树。

        定义二叉搜索树的创建函数create_bst(int root_key, void* data)，传入参数为根结点的键值对，具体实现如下：

static bstree* _create_node(){
    bstree* new = calloc(1, sizeof(bstree));
    if(!new){
        printf("创建结点失败！返回NULL\n");
        return NULL;
    }
    return new;
}
//创建一个新的二叉搜索树
bstree* create_bst(int root_key, void* data){
    bstree* new = _create_node();
    if(!new){
        printf("创建二叉树失败，返回NULL！\n");
        return NULL;
    }
    new->key = root_key;
    new->data = data;
    return new;
};

        此外，一个完整的二叉树还需包含数据的插入、修改、删除、读取功能，关于数据插入，设计接口bool insert_bst(bstree* tree, int key, void* data)，当插入成功的时候返回true，否则返回false。具体实现时，需要逐步比较插入结点的键，以此确定插入位置，具体实现如下：

bool insert_bst(bstree* tree, int key, void* data){
    if(!tree){
        printf("目标操作的树不存在！\n");
        return false;
    }
    bstree* tmp = tree;
    bstree* new = _create_node();
    if(!new){
        printf("结点插入失败，返回false\n");
        return false;
    }
    new->key = key;
    new->data = data;

    while (1) {
        if(key < tmp->key) {
            if(tmp->left_son) tmp = tmp->left_son;
            else {
                tmp->left_son = new;
                return true;
            }
        }
        if(key > tmp->key) {
            if(tmp->right_son) tmp = tmp->right_son;
            else {
                tmp->right_son = new;
                return true;
            }
        }
        else{
            printf("目标插入的键已经存在，无法继续插入！\n");
            return false;
        }
    }
};

此外，如果需要修改二叉树的数据，还需要额外设计数据修改接口，定义数据修改接口bool change_bst(bstree* tree, int key, void* data)，具体实现如下，在使用时，传入create_bst函数生成的树根结点、想要修改的结点的键以及新值即可：

bool change_bst(bstree* tree, int key, void* data){
    if(!tree){
        printf("目标操作的树不存在！\n");
        return false;
    }
    bstree* tmp = tree;
    while (1) {
        if(key < tmp->key) {
            if(tmp->left_son) tmp = tmp->left_son;
            else {
                printf("目标操作的结点不存在！\n");
                return false;
            }
        }
        if(key > tmp->key) {
            if(tmp->right_son) tmp = tmp->right_son;
            else {
                printf("目标操作的结点不存在！\n");
                return false;
            }
        }
        else{
            tmp->data = data;
            return true;
        }
    }
};

关于二叉树的删除，为了防止内存泄漏，需要采用遍历的方法进行删除，采用递归的方法进行遍历，设计静态递归遍历释放方法如下：

void __free_tree(bstree** tree){
//递归出口，当前的树为空的时候，返回
    if(*tree == NULL) return;
//分别清理左右子树
    __free_tree(&((*tree)->left_son));
    __free_tree(&((*tree)->right_son));
//清理自己
    free(*tree);
//悬空指针，防止错误使用
    *tree = NULL;
}

调用设计好的静态方法释放二叉树，设计二叉树释放接口bool destory_bst(bstree* tree, int key)，表示从key开始释放后续的结点，

//从树的结点n开始删除结点，请注意，如果key是根节点，则将连带其自身一起清除。
bool destory_bst(bstree** tree, int key){
    if(!*tree){
        printf("目标调用的树为空树，无法对其进行访问！\n");
        return false;
    }
    //先找到目标结点
    bstree* tmp = *tree; //对二级指针进行解引用，直接指向了tree指针本体
    while (tmp->key != key) {
        if(key < tmp->key) {
            if(tmp->left_son) tmp = tmp->left_son;
            else {
                printf("目标操作的结点不存在！\n");
                return false;
            }
        }
        else if(key > tmp->key) {
            if(tmp->right_son) tmp = tmp->right_son;
            else {
                printf("目标操作的结点不存在！\n");
                return false;
            }
        }
    }
    //此时tmp为目标要删除的结点，从这儿开始往下删除结点
    //先解除父结点的指向关系
    if(key == (*tree)->key) __free_tree(tree);
    else if(key < tmp->parent->key) __free_tree(&(tmp->parent->left_son));
    else if(key > tmp->parent->key) __free_tree(&(tmp->parent->right_son));
    return true;
}