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

2024-09-02 09:36
文章标签 数据结构 搜索 二叉

本文主要是介绍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;
}

这篇关于c-数据结构（二叉搜索树）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/1129603。

相关文章

认识、理解、分类——acm之搜索

认识、理解、分类——acm之搜索

普通搜索方法有两种：1、广度优先搜索；2、深度优先搜索； 更多搜索方法： 3、双向广度优先搜索； 4、启发式搜索（包括A*算法等）； 搜索通常会用到的知识点：状态压缩（位压缩，利用hash思想压缩）。
阅读更多...
hdu1240、hdu1253（三维搜索题）

hdu1240、hdu1253（三维搜索题）

1、从后往前输入，（x，y，z）; 2、从下往上输入，（y , z, x）; 3、从左往右输入，（z，x，y）； hdu1240代码如下： #include<iostream>#include<algorithm>#include<string>#include<stack>#include<queue>#include<map>#include<stdio.h>#inc
阅读更多...
【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

前言：快速排序的实现最重要的是找基准值，下面让我们来了解如何实现找基准值 基准值的注释：在快排的过程中，每一次我们要取一个元素作为枢纽值，以这个数字来将序列划分为两部分。 在此我们采用三数取中法，也就是取左端、中间、右端三个数，然后进行排序，将中间数作为枢纽值。 快速排序实现主框架： //快速排序 void QuickSort(int* arr, int left, int rig
阅读更多...
6.1.数据结构-c/c++堆详解下篇（堆排序，TopK问题）

6.1.数据结构-c/c++堆详解下篇（堆排序，TopK问题）

上篇：6.1.数据结构-c/c++模拟实现堆上篇（向下，上调整算法，建堆，增删数据）-CSDN博客 本章重点 1.使用堆来完成堆排序 2.使用堆解决TopK问题 目录 一.堆排序 1.1 思路 1.2 代码 1.3 简单测试 二.TopK问题 2.1 思路(求最小)： 2.2 C语言代码（手写堆） 2.3 C++代码（使用优先级队列 priority_queue）
阅读更多...
hdu 4517 floyd+记忆化搜索

hdu 4517 floyd+记忆化搜索

题意： 有n（100）个景点，m（1000）条路，时间限制为t（300），起点s，终点e。 访问每个景点需要时间cost_i，每个景点的访问价值为value_i。 点与点之间行走需要花费的时间为g[ i ] [ j ] 。注意点间可能有多条边。 走到一个点时可以选择访问或者不访问，并且当前点的访问价值应该严格大于前一个访问的点。 现在求，从起点出发，到达终点，在时间限制内，能得到的最大
阅读更多...
AI基础 L9 Local Search II 局部搜索

AI基础 L9 Local Search II 局部搜索

Local Beam search 对于当前的所有k个状态，生成它们的所有可能后继状态。 检查生成的后继状态中是否有任何状态是解决方案。 如果所有后继状态都不是解决方案，则从所有后继状态中选择k个最佳状态。 当达到预设的迭代次数或满足某个终止条件时，算法停止。 — Choose k successors randomly, biased towards good ones — Close
阅读更多...
hdu4277搜索

hdu4277搜索

给你n个有长度的线段，问如果用上所有的线段来拼1个三角形，最多能拼出多少种不同的？ import java.io.BufferedInputStream;import java.io.BufferedReader;import java.io.IOException;import java.io.InputStream;import java.io.InputStreamReader;
阅读更多...
《数据结构（C语言版）第二版》第八章-排序（8.3-交换排序、8.4-选择排序）

《数据结构（C语言版）第二版》第八章-排序（8.3-交换排序、8.4-选择排序）

8.3 交换排序 8.3.1 冒泡排序 【算法特点】 (1) 稳定排序。 (2) 可用于链式存储结构。 (3) 移动记录次数较多，算法平均时间性能比直接插入排序差。当初始记录无序，n较大时， 此算法不宜采用。 #include <stdio.h>#include <stdlib.h>#define MAXSIZE 26typedef int KeyType;typedef char In
阅读更多...
【408数据结构】散列 （哈希）知识点集合复习考点题目

【408数据结构】散列 （哈希）知识点集合复习考点题目

苏泽  “弃工从研”的路上很孤独，于是我记下了些许笔记相伴，希望能够帮助到大家    知识点 1. 散列查找 散列查找是一种高效的查找方法，它通过散列函数将关键字映射到数组的一个位置，从而实现快速查找。这种方法的时间复杂度平均为(
阅读更多...
浙大数据结构：树的定义与操作

浙大数据结构：树的定义与操作

四种遍历 #include<iostream>#include<queue>using namespace std;typedef struct treenode *BinTree;typedef BinTree position;typedef int ElementType;struct treenode{ElementType data;BinTree left;BinTre
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2