当前位置: 首页> 教育> 幼教 > 网页设计top_托管服务器是什么意思_网络营销与直播电商_软文如何推广

网页设计top_托管服务器是什么意思_网络营销与直播电商_软文如何推广

时间:2025/7/11 23:17:30来源:https://blog.csdn.net/weixin_74085818/article/details/145084280 浏览次数:0次
网页设计top_托管服务器是什么意思_网络营销与直播电商_软文如何推广

前言

  • 这个专栏将会用纯C实现常用的数据结构和简单的算法;
  • 有C基础即可跟着学习,代码均可运行;
  • 准备考研的也可跟着写,个人感觉,如果时间充裕,手写一遍比看书、刷题管用很多,这也是本人采用纯C语言实现的原因之一;
  • 欢迎收藏 + 关注,本人将会持续更新。

文章目录

    • 什么是二叉搜索树
    • 代码实现
      • 节点封装
      • 插入节点
      • 删除节点
      • 输出(中序遍历有序)
      • 总代码

什么是二叉搜索树

二叉搜索树(Binary Search Tree,BST)是一种特殊的二叉树数据结构,其中每个节点的值都大于其左子树中的任何节点的值,且小于其右子树中的任何节点的值

它的特点使得在搜索、插入和删除操作上具有高效性。

以下是一些关于二叉搜索树的重要特性

  • 左子树中的所有节点的值都小于根节点的值。
  • 右子树中的所有节点的值都大于根节点的值。
  • 左右子树本身也是二叉搜索树。
  • 中序遍历有序。

由于这些特性,二叉搜索树可以用于高效地实现插入、搜索和删除操作。

  • 搜索操作可以在平均情况下以O(log n)的时间复杂度完成,其中n是树中节点的数量。
  • 然而,最坏情况下,树可能退化为链表,搜索操作的时间复杂度将变为O(n)
  • 插入操作的时间复杂度与搜索操作类似,平均情况下为O(log n),最坏情况下为O(n)
  • 删除操作的时间复杂度也是O(log n),最坏情况下为O(n)

BST书图示为:

在这里插入图片描述

代码实现

节点封装

节点封装,采用KV存储方式,数据在BST树中是存储K值这里规定K值不重复

typedef struct Data {int key;char data[DATAMAX];
}Data;typedef struct Node {Data* data;struct Node* lChild;struct Node* rChild;
}Node;Data* creata_data(Data data)
{Data* new_data = (Data*)calloc(1, sizeof(Data));assert(new_data);new_data->key = data.key;strncpy(new_data->data, data.data, DATAMAX);return new_data;
}Node* create_node(Data data)
{Node* node = (Node*)calloc(1, sizeof(Node));assert(node);node->data = creata_data(data);assert(node->data);return node;
}

插入节点

采用递归简历树。

// 插入过程建树
void push_tree(Node** root, Data data)
{assert(root);// 树为NULLif (*root == NULL) {*root = create_node(data);return;}else {   // 树不为NULLif (data.key < (*root)->data->key) {push_tree(&(*root)->lChild, data);}else {   // > =默认也插在右边,但是一般这种kv存储,是不允许有重复值的push_tree(&(*root)->rChild, data);}}
}

删除节点

删除节点要注意,采用递归删除有5种情况,据图代码所示(清理可以参考代码随想录力扣题目解析:BST树的删除):

// 删除
// 这里采用:左节点,最右节点
// 利用BST树的特点
// 5种情况
Node* erase_tree(Node* root, Data data)
{if (root == NULL) {return root;}if (root->data->key == data.key) {if (root->lChild == NULL && root->rChild == NULL) {free(root);root = NULL;return root;}else if (root->lChild == NULL && root->rChild != NULL) {Node* t = root;root = root->rChild;free(t);t = NULL;return root;}else if (root->lChild != NULL && root->rChild == NULL) {Node* t = root;root = root->lChild;free(t);t = NULL;return root;}else {Node* t = root->lChild;while (t->rChild) {t = t->rChild;}t->rChild = root->rChild;Node* temp = root;root = root->lChild;free(temp);return root;}}if (root && root->data->key > data.key) root->lChild = erase_tree(root->lChild, data);if (root && root->data->key < data.key) root->rChild = erase_tree(root->rChild, data);
}

输出(中序遍历有序)

BST树的中序遍历是有序的

// 中序有序
void mid_travel(Node* root)
{if (root == NULL) {return;}mid_travel(root->lChild);printf("K: %d, V: %s\n", root->data->key, root->data->data);mid_travel(root->rChild);
}

总代码

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>
#include <string.h>// 这里采用  kv 存储的方法,进行建立,  key也可以作为一个权重,具体情况需要结合业务#define DATAMAX 20typedef struct Data {int key;char data[DATAMAX];
}Data;typedef struct Node {Data* data;struct Node* lChild;struct Node* rChild;
}Node;Data* creata_data(Data data)
{Data* new_data = (Data*)calloc(1, sizeof(Data));assert(new_data);new_data->key = data.key;strncpy(new_data->data, data.data, DATAMAX);return new_data;
}Node* create_node(Data data)
{Node* node = (Node*)calloc(1, sizeof(Node));assert(node);node->data = creata_data(data);assert(node->data);return node;
}// 插入过程建树
void push_tree(Node** root, Data data)
{assert(root);// 树为NULLif (*root == NULL) {*root = create_node(data);return;}else {   // 树不为NULLif (data.key < (*root)->data->key) {push_tree(&(*root)->lChild, data);}else {   // > =默认也插在右边,但是一般这种kv存储,是不允许有重复值的push_tree(&(*root)->rChild, data);}}
}// 删除
// 这里采用:左节点,最右节点
// 利用BST树的特点
// 5种情况
Node* erase_tree(Node* root, Data data)
{if (root == NULL) {return root;}if (root->data->key == data.key) {if (root->lChild == NULL && root->rChild == NULL) {free(root);root = NULL;return root;}else if (root->lChild == NULL && root->rChild != NULL) {Node* t = root;root = root->rChild;free(t);t = NULL;return root;}else if (root->lChild != NULL && root->rChild == NULL) {Node* t = root;root = root->lChild;free(t);t = NULL;return root;}else {Node* t = root->lChild;while (t->rChild) {t = t->rChild;}t->rChild = root->rChild;Node* temp = root;root = root->lChild;free(temp);return root;}}if (root && root->data->key > data.key) root->lChild = erase_tree(root->lChild, data);if (root && root->data->key < data.key) root->rChild = erase_tree(root->rChild, data);
}// 中序有序
void mid_travel(Node* root)
{if (root == NULL) {return;}mid_travel(root->lChild);printf("K: %d, V: %s\n", root->data->key, root->data->data);mid_travel(root->rChild);
}int main()
{Data data[10] = { {17, "yy"}, {9, "xx"}, {22, "zz"}, {2, "ll"}, {8, "tt"}, {33, "xh"}, {20, "tt"}, {18, "ee"}, {77, "zz"}, {10, "hh"} };Node* root = NULL;for (int i = 0; i < 10; i++) {push_tree(&root, data[i]);}mid_travel(root);int key = 22;Data temp = { 22, "tt" };erase_tree(root, temp);printf("*****************************\n");mid_travel(root);return 0;
}
关键字:网页设计top_托管服务器是什么意思_网络营销与直播电商_软文如何推广

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

责任编辑: