c-数据结构（二叉搜索树）

树

• 概念

一组数据中除第一个节点（第一个节点称为根节 点，没有直接前驱节点）之外，其余任意节点有且仅有一个直接前驱，有零个或多个直接后继，这样的一组数据形成一棵树。即用于描述具有层次关系，类似组织架 构关系的一种数据结构。

树的组成：根、分支、叶子

• 基本术语

  1. 节点：树中的元素及其子树

  2. 根：树的第一个节点，没有前驱

  3. 父节点（parent）：某节点的直接前驱就是该节点的父节点

  4. 子节点（child）：某节点的直接后继就是该节点的子节点

  5. 节点的层次（level）：根节点所在层次规定为1层，依次后推

  6. 节点的度（degree）：一个结点拥有的子节点个数

  7. 叶子（leaf）：树中度为0的节点

  8. 树的高度（height）：树中节点的最大层次

  9. 有序树和无序树：若某个节点的子节点是有次序的，则是有序树，否则反之

二叉树

• 特性

  1. 第i层上，最多有2^(i-1)个节点

  2. 高度为k的二叉树，最多有2^k-1个节点

  3. 叶子数为n0，度为2的节点数为n2，则满足：n0 = n2 + 1

• 分类

  1. 满二叉树：高度为k的二叉树，且有2^k-1个节点

• 

  1. 完全二叉树：从根节点到倒数第二层满足满二叉树，最后一层可以不完全填充，其叶子节点都靠左对齐。

• 

  1. 完满二叉树：所有非叶子节点的度都是2。（只要你有孩子，你就必然是有两个孩子。）

• 

二叉搜索树（BST）

• 组成

  1. 根指针：指向根节点的指针变量

  2. 节点：

     • 数据域（存放数据）

     • 指针域（存放左右指针）

二叉搜索树数据操作代码
//math7文件
--------------------------------------------------------------------------------------------------
btree.h
--------------------------------------------------------------------------------------------------
#ifndef __BTREE_H
#define __BTREE_H#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>//定义数据域数据类型
typedef int DATA;//定义树的节点
typedef struct _node
{DATA data;			//节点上的数据struct _node *left;	//该节点左侧子节点地址struct _node *right;//该节点右侧子节点地址
}NODE;//创建搜索二叉树（BST）
int btree_create(NODE**, DATA);//二叉树数据添加
int btree_add(NODE**, DATA);//二叉树数据删除
int btree_delete(NODE**, DATA);//二叉树先序遍历
void Preorder(const NODE*);//二叉树中序遍历
void Midorder(const NODE*);//二叉树后序遍历
void Postorder(const NODE*);//二叉树层序遍历
void Levelorder(const NODE*);//二叉树数据查询
NODE* btree_find(const NODE*, DATA);//二叉树数据更新
int btree_update(const NODE*, DATA, DATA);//二叉树回收
void btree_destroy(NODE**);#endif
--------------------------------------------------------------------------------------------------
btree.c
--------------------------------------------------------------------------------------------------
#include "btree.h"/*
@function:     int btree_create(NODE** root,data_t data)
@brief:       创建搜索二叉树
@argument:     root: 根指针地址
@argument:     data: 存储的数据
@return:       0 成功-1 失败
*/
//创建搜索二叉树（BST）
int btree_create(NODE** root, DATA data)
{//查看根节点是否存在if(*root){return -1;}//创建节点并申请内存NODE* p = (NODE*)malloc(sizeof(NODE));if(!p){return -1;}//给节点赋初值p->data = data;p->left = NULL;p->right = NULL;//将新节点作为根节点*root = p;return 0;
}/*
@function:     int btree_add(NODE** root,data_t data)
@brief:       二叉树数据添加
@argument:     root: 根指针地址
@argument:     data: 添加的数据
@return:       0 成功-1 失败
*/
//二叉树数据添加
int btree_add(NODE** root, DATA data)
{NODE* pNew = (NODE*)malloc(sizeof(NODE));if(!pNew){return -1;}pNew->data = data;pNew->left = NULL;pNew->right = NULL;NODE* p = *root, *q = NULL;//第一种情况，树为空if(!p){*root = pNew;return 0;}//第二种情况，树不为空while(p)	//一直寻找到叶子节点（相当于链表尾插法先寻找尾巴）{q = p;//这里特别注意 data 与 p->data 的位置  是将前（data）与后（p->data）做对比//可以调换，但会影响后续结果if(memcmp(&data,&(p->data),sizeof(DATA)) < 0){p = p->left;}else	//数值相等的划分给右子树{p = p->right;	}}//找到后与叶子节点数据比大小，小的为左侧节点，大的为右侧节点if(memcmp(&data,&(q->data),sizeof(DATA)) < 0){q->left = pNew;}else{q->right = pNew;}return 0;
}/*
@function:     int btree_delete(NODE** root,data_t data)
@brief:       二叉树数据删除
@argument:     root: 根指针地址
@argument:     data: 待删除的节点数据
@return:       0 成功-1 失败
*/
//二叉树数据删除
int btree_delete(NODE** root, DATA data)
{/*原则：将待删除的节点尽量转换为删除叶子节点，因为删除叶子节点对BST树影响是最小的；宗旨：就是尽可能将和删除数据差值最小的数值进行替换思路： 1. 从根节点开始遍历BST找到待删除的节点；2. 对待删除的节点进行判断，如果节点有左子树，找到左子树中最大的节点，然后利用左子树中最大的节点数据替换待删除的节点数据，删除左子树中最大的节点；左子树中最大的节点大概率是叶子节点3. 如果节点有右子树，找到右子树中最小的节点，然后 利用右子树中最小的节点数据替换待删除的节点数据，删除右子树中最小的节点；右子树中最小的节点大概率是叶子节点4. 如果待删除节点是叶子节点，直接删除。*/NODE* del = *root;		//指向待删除的节点NODE* parent = NULL;	//指向实际删除的节点的父节点NODE* replace = NULL;	//指向实际删除的节点while(del){//将待删除节点数据与二叉树节点数据做对比，大的找右子节点，小的找左子节点if(memcmp(&data,&(del->data),sizeof(DATA)) > 0){parent = del;del = del->right;}else if(memcmp(&data,&(del->data),sizeof(DATA)) < 0){parent = del;del = del->left;}else	//找到待删除节点{//接下来按情况寻找待删除结点的“背锅侠”-replaceif(del->left)	//情况一：待删除结点存在左子树{/*类似于 NODE* p = *head, *q = NULL;	while(p){q = p; p = p->next;}*///创造指针尾随，直接找到左子树叶子节点，也就是左子树最大值。参考如上parent = del;			//此时 parent 是实际要删除节点replace = del->left;	//replace 用来进入左子树while(replace->right)	//通过循环来寻找左子树的最大值{parent = replace;replace = replace->right;}del->data = replace->data;	//左子树最大值替换要删除节点//如果找到的最大值（replace）并不是叶子节点，还有自己的左子节点（绝对不可能出现右子节点）//如果是叶子节点，赋值为NULL；如果不是，则改变节点引用关系----------------------------------------------------------if(parent->right == replace)	//实际删除的结点在右子树上{parent->right = replace->left;}else{parent->left = replace->left;}----------------------------------------------------------free(replace);}else if(del->right)	//情况二：待删除结点仅存在右子树{parent = del;replace = del->right;while(replace->right){parent = replace;replace = replace->right;}del->data = replace->data;if(parent->right == replace){parent->right = replace->right;}else{parent->left = replace->right;}free(replace);}else	//情况三：待删除的节点没有子节点{if(!parent){free(del);*root = NULL;return 0;}if(parent->left == del){parent->left = NULL;}else{parent->right = NULL;}free(del);}return 0;}}return -1;
}/*
@function:     void Preorder(const NODE* root)
@brief:       二叉树前序遍历
@argument:     root: 根指针
@ret     :     无
*/
//二叉树先序遍历	根左右
void Preorder(const NODE* root)
{if(!root)	//递归结束{return;}//根左右printf("%4d", root->data);Preorder(root->left);Preorder(root->right);
}/*
@function:     void Midorder(const NODE* root)
@brief:       二叉树中序遍历
@argument:     root: 根指针
@ret     :     无
*/
//二叉树中序遍历	左根右
void Midorder(const NODE* root)
{if(!root){return;}//左根右Midorder(root->left);printf("4d", root->data);Midorder(root->right);
}/*
@function:     void Postorder(const NODE* root)
@brief:       二叉树后序遍历
@argument:     root: 根指针
@ret     :     无
*/
//二叉树后序遍历	左右根
void Postorder(const NODE* root)
{if(!root){return;}//左右根Postorder(root->left);Postorder(root->right);printf("4d", root->data);
}/*
@function:     NODE* btree_find(const NODE* root,data_t data)
@brief:       二叉树数据查询
@argument:     root: 根指针
@argument:     data: 待查询的数据
@ret     :     成功：返回查询到的节点地址失败: NULL
*/
//二叉树数据查询
NODE* btree_find(const NODE* root, DATA data)
{const NODE* p = root;while(p){if(memcmp(&data,&(p->data),sizeof(DATA)) < 0){p = p->left;}else if(memcmp(&data,&(p->data),sizeof(DATA)) > 0){p = p->right;}else{return (NODE*)p;}}return NULL;
}/*
@function:     int btree_update(const NODE* root,data_t old,data_t newdata)
@brief:       更新二叉树数据old 为 newdata
@argument:     root: 根指针
@argument:     old: 待更新的数据
@argument:     newdata: 更新后的数据
@ret     :     成功：0失败: -1
*/
//二叉树数据更新
int btree_update(const NODE* root, DATA old_data, DATA new_data)
{NODE* p = btree_find(root, old_data);if(!p){return -1;}p->data = new_data;return 0;
}/*
@function:     void btree_destroy(NODE** root)
@brief:       二叉树回收
@argument:     root: 根指针地址
@ret     :     无
*/
//二叉树回收static void btree_free(NODE* root)
{if(!root){return;}btree_free(root->left);btree_free(root->right);free(root);
}void btree_destroy(NODE** root)
{btree_free(*root);*root = NULL;
}
--------------------------------------------------------------------------------------------------
btree_mian.c
--------------------------------------------------------------------------------------------------
#include "btree.h"
#define N 10int main(void)
{NODE *root = NULL;register int i = 0;data_t  a[] = {20,15,25,10,19,28,6,13,26,30,11,27};int n  = sizeof a / sizeof a[0];srand(time(NULL));for(; i < n ; i++){//   int data = rand() % 99 + 1;//   printf("%4d",data);//   btree_add(&root,data);btree_add(&root,a[i]);}printf("\n");puts("====先序遍历====");Preorder(root);printf("\n");puts("====中序遍历====");Midorder(root);printf("\n");puts("====后序遍历====");Postorder(root);printf("\n");puts("====层序遍历====");Levelorder(root);printf("\n");data_t  deldata = 0;while(1){printf("请输入要删除的数据(-1退出):");scanf("%d",&deldata);if(deldata == -1)break;if(btree_delete(&root,deldata) == -1){puts("删除失败请重试...");continue;}puts("====先序遍历====");Preorder(root);printf("\n");}btree_destroy(&root);return 0;
}