二叉排序树实现
1、二叉排序树，也叫二叉搜索树，中序遍历为有序序列。这是一种特殊的二叉树，每个节点的左孩子都比其要小，右孩子都比其要大，二叉树的所有子树也都是二叉搜索树。
2、二叉排序树主要功能实现：构造二叉树、插入节点、删除节点。
2.1、插入节点：二叉排序树是一个有序序列，插入节点时只需要从根节点开始查询，如果要插入的节点数据比该节点小，则进入其左孩子位置，如比其大，则进入其右孩子位置，一直找到空闲位置为止。
2.2、删除节点：这里有三种情况，一种是删除叶子节点，一种是删除根节点，一种是删除中间节点。
删除叶子节点时只需要将叶子节点置NULL即可；删除根节点需要将其左孩子设为新的根节点，如果左孩子不存在则将右孩子设为新的根节点；删除中间节点需要将其父节点和其子节点先连接起来，具体实现可查看下文。
树节点定义
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); //层序创建二叉树
b_tree_bst* create_bst_tree(void* list[], int len); //创建二叉排序树，中序遍历为顺序排列
void insert_node_by_bst(b_tree_bst *bst_tree, b_tree_node *node); //排序树插入节点
void insert_node_data_by_bst(b_tree_bst *bst_tree, void *data); //排序树插入节点数据
b_tree_node* find_node_by_bst(b_tree_bst *bst_tree, void *data); //从排序树从找到第一个等于data的节点
void destroy_node_data_by_bst(b_tree_bst *bst_tree, void* data); //排序树删除节点
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; //当前未插入数据索引
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) //插入节点比对比节点数据小，进入左节点比较
{
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) //删除根节点
{
if (left_node != NULL)
{
bst_tree->root = left_node; //左节点成为新的根节点
bst_tree->root->parent_node = NULL;
if (right_node != NULL) //右节点不为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; //待删除节点处于父节点左子树？
if (left_node == NULL && right_node == NULL) //删除叶子节点
{
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) //删除的节点右子节点不为null，需要附加到之前的左节点右边
{
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)); //层序创建二叉树
//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语言实现常用数据结构（一）
二叉排序树在极端情况下（例如所有数据都比根节点大）会退化成链表，为解决这个问题引入了平衡二叉树。平衡二叉树的特点是左右两个子树的高度差不能大于1，所以在插入和删除节点时需要动态调整树结构，平衡二叉树的重点是旋转算法，常见实现方式有AVL树，红黑树等。
