二叉排序樹實現(xiàn)

1、二叉排序樹，也叫二叉搜索樹，中序遍歷為有序序列。這是一種特殊的二叉樹，每個節(jié)點(diǎn)的左孩子都比其要小，右孩子都比其要大，二叉樹的所有子樹也都是二叉搜索樹。

2、二叉排序樹主要功能實現(xiàn)：構(gòu)造二叉樹、插入節(jié)點(diǎn)、刪除節(jié)點(diǎn)。

2.1、插入節(jié)點(diǎn)：二叉排序樹是一個有序序列，插入節(jié)點(diǎn)時只需要從根節(jié)點(diǎn)開始查詢，如果要插入的節(jié)點(diǎn)數(shù)據(jù)比該節(jié)點(diǎn)小，則進(jìn)入其左孩子位置，如比其大，則進(jìn)入其右孩子位置，一直找到空閑位置為止。

2.2、刪除節(jié)點(diǎn)：這里有三種情況，一種是刪除葉子節(jié)點(diǎn)，一種是刪除根節(jié)點(diǎn)，一種是刪除中間節(jié)點(diǎn)。
刪除葉子節(jié)點(diǎn)時只需要將葉子節(jié)點(diǎn)置NULL即可；刪除根節(jié)點(diǎn)需要將其左孩子設(shè)為新的根節(jié)點(diǎn)，如果左孩子不存在則將右孩子設(shè)為新的根節(jié)點(diǎn)；刪除中間節(jié)點(diǎn)需要將其父節(jié)點(diǎn)和其子節(jié)點(diǎn)先連接起來，具體實現(xiàn)可查看下文。

C語言實現(xiàn)常用數(shù)據(jù)結(jié)構(gòu)（一）

樹節(jié)點(diǎn)定義
b_tree_node.h

#pragma once
#ifndef BinaryTreeNode

#include <stdlib.h>
typedef struct BinaryTreeNode
{
    void* data;
    struct BinaryTreeNode* left_node;
    struct BinaryTreeNode* right_node;
    struct BinaryTreeNode* parent_node;
}b_tree_node;

b_tree_node* create_tree_node(void* data);

b_tree_node* append_left_node_data(b_tree_node* node, void* data);
b_tree_node* append_left_node(b_tree_node* node, b_tree_node* new_node);

b_tree_node* append_right_node_data(b_tree_node* node, void* data);
b_tree_node* append_right_node(b_tree_node* node, b_tree_node* new_node);

#endif

b_tree_node.c

#include "b_tree_node.h"

b_tree_node * create_tree_node(void * data)
{
    b_tree_node *new_node = malloc(sizeof(b_tree_node));
    new_node->data = data;
    new_node->left_node = NULL;
    new_node->right_node = NULL;
    new_node->parent_node = NULL;

    return new_node;
};

b_tree_node* append_left_node_data(b_tree_node* node, void* data)
{
    b_tree_node *newNode = create_tree_node(data, node);
    node->left_node = newNode;
    newNode->parent_node = node;

    return newNode;
};

b_tree_node * append_left_node(b_tree_node * node, b_tree_node * new_node)
{
    node->left_node = new_node;
    new_node->parent_node = node;

    return new_node;
};

b_tree_node* append_right_node_data(b_tree_node* node, void* data)
{
    b_tree_node *newNode = create_tree_node(data);
    node->right_node = newNode;
    newNode->parent_node = node;

    return newNode;
};

b_tree_node* append_right_node(b_tree_node* node, b_tree_node* new_node)
{
    node->right_node = new_node;
    new_node->parent_node = node;

    return new_node;
}

二叉樹定義
binary_tree.h

#pragma once
#ifndef BinaryTree

#include <stdlib.h>
#include "m_queue.h"
#include "m_stack.h"
#include "b_tree_node.h"
#include <cstdbool>

typedef struct BinaryTree
{
    b_tree_node* root;
}b_tree, b_tree_bst;

b_tree* create_b_tree();
b_tree* create_b_tree_root(void* data);
b_tree* create_b_tree_level(void* list[], int len); //層序創(chuàng)建二叉樹

b_tree_bst* create_bst_tree(void* list[], int len); //創(chuàng)建二叉排序樹，中序遍歷為順序排列
void insert_node_by_bst(b_tree_bst *bst_tree, b_tree_node *node);   //排序樹插入節(jié)點(diǎn)
void insert_node_data_by_bst(b_tree_bst *bst_tree, void *data); //排序樹插入節(jié)點(diǎn)數(shù)據(jù)
b_tree_node* find_node_by_bst(b_tree_bst *bst_tree, void *data);        //從排序樹從找到第一個等于data的節(jié)點(diǎn)
void destroy_node_data_by_bst(b_tree_bst *bst_tree, void* data);        //排序樹刪除節(jié)點(diǎn)

void dispose_b_tree(b_tree ** tree);  //釋放

void PreOrder(b_tree_node * root_node);
void PreOrder2(b_tree* tree);
void Inorder(b_tree_node * root_node);
void Inorder2(b_tree* tree);
void LastOrder(b_tree_node * root_node);
void LevelOrder(b_tree* tree);
#endif

binary_tree.c

#include "binary_tree.h"

b_tree * create_b_tree()
{
    b_tree *tree = malloc(sizeof(b_tree));
    tree->root = NULL;
    return tree;
};

b_tree* create_b_tree_root(void* data)
{
    b_tree* tree = create_b_tree();
    b_tree_node  *node = create_tree_node(data);
    tree->root = node;
    return tree;
};

b_tree * create_b_tree_level(void* list[], int len)
{
    if (len == 0)
    {
        perror("create binary tree by level,len==0");
        return NULL;
    }

    b_tree *tree = create_b_tree_root(list[0]);
    m_queue *queue = init_queue();
    en_queue_data(queue, tree->root);
    int index = 1;  //當(dāng)前未插入數(shù)據(jù)索引

    while (queue->len > 0)
    {
        b_tree_node *tree_node = de_queue_data(queue);

        if (index < len)
        {
            append_left_node_data(tree_node, list[index]);
            index++;
            en_queue_data(queue, tree_node->left_node);
        }
        if (index < len)
        {
            append_right_node_data(tree_node, list[index]);
            index++;
            en_queue_data(queue, tree_node->right_node);
        }
    }

    dispose_que(&queue);
    return tree;
};

b_tree_bst * create_bst_tree(void* list[], int len)
{
    b_tree_bst* tree_bst = create_b_tree_root(list[0]);
    for (int i = 1; i < len; i++)
    {
        insert_node_data_by_bst(tree_bst, list[i]);
    }

    return tree_bst;
};

void insert_node_by_bst(b_tree_bst * bst_tree, b_tree_node * node)
{
    if (bst_tree->root == NULL)
    {
        bst_tree->root = node;
        return;
    }

    b_tree_node *temp = bst_tree->root;
    while (temp != NULL)
    {
        if (node->data <= temp->data)   //插入節(jié)點(diǎn)比對比節(jié)點(diǎn)數(shù)據(jù)小，進(jìn)入左節(jié)點(diǎn)比較
        {
            if (temp->left_node == NULL)    //找到空余位置
            {
                append_left_node(temp, node);
                return;
            }
            else
            {
                temp = temp->left_node;
            }

        }
        else
        {
            if (temp->right_node==NULL)
            {
                append_right_node(temp, node);
                return;
            }
            else
            {
                temp = temp->right_node;
            }

        }
    }
};

void insert_node_data_by_bst(b_tree_bst * bst_tree, void * data)
{
    b_tree_node *tree_node = create_tree_node(data);
    insert_node_by_bst(bst_tree, tree_node);
};

b_tree_node* find_node_by_bst(b_tree_bst *bst_tree, void *data)
{
    if (bst_tree->root == NULL)
    {
        perror("bst tree find node,root is null\n");
        return NULL;
    }

    b_tree_node *temp = bst_tree->root;
    while (temp != NULL)
    {
        if (data == temp->data)
        {
            return temp;
        }
        if (data <= temp->data)
        {
            temp = temp->left_node;
        }
        else
        {
            temp = temp->right_node;
        }
    }

    return NULL;
}

void destroy_node_data_by_bst(b_tree_bst *bst_tree, void* data)
{
    b_tree_node *tree_node = find_node_by_bst(bst_tree, data);
    if (tree_node == NULL)
    {
        return;
    }

    b_tree_node *left_node = tree_node->left_node;
    b_tree_node *right_node = tree_node->right_node;
    b_tree_node *parent_node = tree_node->parent_node;

    if (tree_node == bst_tree->root)    //刪除根節(jié)點(diǎn)
    {
        if (left_node != NULL)
        {
            bst_tree->root = left_node;     //左節(jié)點(diǎn)成為新的根節(jié)點(diǎn)
            bst_tree->root->parent_node = NULL;

            if (right_node != NULL) //右節(jié)點(diǎn)不為null，重新尋找位置
            {
                insert_node_by_bst(bst_tree, right_node);
            }
        }
        else
        {
            bst_tree->root = right_node;
            bst_tree->root->parent_node = NULL;
        }
        free(tree_node);
        return;
    }

    bool tree_node_parent_left = tree_node->parent_node->left_node == tree_node;    //待刪除節(jié)點(diǎn)處于父節(jié)點(diǎn)左子樹？
    if (left_node == NULL && right_node == NULL)    //刪除葉子節(jié)點(diǎn)
    {
        if (tree_node_parent_left)
        {
            tree_node->parent_node->left_node = NULL;
        }
        else
        {
            tree_node->parent_node->right_node = NULL;
        }
    }
    else
    {
        b_tree_node *new_node = left_node ? left_node : right_node;
        new_node->parent_node = parent_node;

        if (tree_node_parent_left)
        {
            parent_node->left_node = new_node;
        }
        else
        {
            parent_node->right_node = new_node;
        }

        if (left_node != NULL && right_node != NULL)    //刪除的節(jié)點(diǎn)右子節(jié)點(diǎn)不為null，需要附加到之前的左節(jié)點(diǎn)右邊
        {
            insert_node_by_bst(bst_tree, right_node);
        }
    }

    free(tree_node);
};

void dispose_b_tree(b_tree ** tree)
{
    if ((*tree)->root==NULL)
    {
        return;
    }

    m_stack *stack = init_stack();
    m_queue *queue = init_queue();
    en_queue_data(queue, (*tree)->root);

    while (queue->len>0)
    {
        b_tree_node *tree_node = de_queue_data(queue);
        if (tree_node->left_node != NULL)
        {
            en_queue_data(queue, tree_node->left_node);
        }
        if (tree_node->right_node!=NULL)
        {
            en_queue_data(queue, tree_node->right_node);
        }

        push_node_data_stack(stack, tree_node);
    }

    while (stack->len > 0)
    {
        b_tree_node *tree_node = pop_data_stack(stack);
        free(tree_node);
    }

    dispose_stack(&stack);
    dispose_que(&queue);

    free(*tree);
    *tree = NULL;
};

void PreOrder(b_tree_node * root_node)
{
    if (root_node == NULL)
    {
        return;
    }

    printf("%d\n", root_node->data);
    PreOrder(root_node->left_node);
    PreOrder(root_node->right_node);
};

void PreOrder2(b_tree* tree)
{
    if (tree->root == NULL)
    {
        return;
    }

    m_stack *stack = init_stack();
    push_node_data_stack(stack, tree->root);

    while (stack->len > 0)
    {
        b_tree_node *tree_node = pop_data_stack(stack);
        printf("%d\n", tree_node->data);

        if (tree_node->right_node != NULL)
        {
            push_node_data_stack(stack, tree_node->right_node);
        }
        if (tree_node->left_node != NULL)
        {
            push_node_data_stack(stack, tree_node->left_node);
        }
    }

    dispose_stack(&stack);
};

void Inorder(b_tree_node * root_node)
{
    if (root_node ==NULL)
    {
        return;
    }

    Inorder(root_node->left_node);
    printf("%d\n", root_node->data);
    Inorder(root_node->right_node);
};

void LastOrder(b_tree_node * root_node)
{
    if (root_node == NULL)
    {
        return;
    }

    LastOrder(root_node->left_node);
    LastOrder(root_node->right_node);
    printf("%d\n", root_node->data);
}

void LevelOrder(b_tree * tree)
{
    if (tree->root == NULL)
    {
        perror("level order, tree root is null");
        return;
    }

    m_queue *queue = init_queue();
    en_queue_data(queue, tree->root);
    
    while (queue->len > 0)
    {
        b_tree_node *tree_node = de_queue_data(queue);
        printf("%d\n", tree_node->data);

        if (tree_node->left_node != NULL)
        {
            en_queue_data(queue, tree_node->left_node);
        }
        if (tree_node->right_node != NULL)
        {
            en_queue_data(queue, tree_node->right_node);
        }
        free(tree_node);
    }

    dispose_que(&queue);
}

測試使用

#include "binary_tree.h"
void TestBinaryTree()
{
    //b_tree* tree = create_b_tree_root(1);
    //b_tree_node *a = append_left_node(tree->root, 2);
    //append_right_node(tree->root, 3);
    ////Inorder(tree->root);
    //LevelOrder(tree);

    int list[] = {9,3,1,2,11,10,12};
    //b_tree *tree = create_b_tree_level(list, array_len(list));    //層序創(chuàng)建二叉樹
    //LevelOrder(tree);

    b_tree_bst *bst_tree = create_bst_tree(list, array_len(list));
    destroy_node_data_by_bst(bst_tree, 11);
    destroy_node_data_by_bst(bst_tree, 12);
    destroy_node_data_by_bst(bst_tree, 10);

    Inorder(bst_tree->root);

    dispose_b_tree(&bst_tree);
}

int main()
{
TestBinaryTree();
return 0;
}

C語言實現(xiàn)常用數(shù)據(jù)結(jié)構(gòu)（一）
二叉排序樹在極端情況下（例如所有數(shù)據(jù)都比根節(jié)點(diǎn)大）會退化成鏈表，為解決這個問題引入了平衡二叉樹。平衡二叉樹的特點(diǎn)是左右兩個子樹的高度差不能大于1，所以在插入和刪除節(jié)點(diǎn)時需要動態(tài)調(diào)整樹結(jié)構(gòu)，平衡二叉樹的重點(diǎn)是旋轉(zhuǎn)算法，常見實現(xiàn)方式有AVL樹，紅黑樹等。