二叉树（C语言版）

ops/2025/2/19 1:42:43/

文章目录

  • 二叉树
    • 完全二叉树和满二叉树
    • 二叉搜索树
    • 基本操作
    • 实现
      • 代码
      • 运行结果
    • 分析
    • 红黑树
      • 2-3-4树(理论模型)
      • 红黑树(实际实现)

二叉树

树是一种层次结构，它在现实生活中是广泛存在的，比如：族谱(family tree)，组织机构，目录结构等。

不过今天我们只讲二叉树。

二叉树有多重要？单就面试而言，在 leetcode 中二叉树相关的题目占据了 300 多道，近三分之一。同时，二叉树在整个算法板块中还起到承上启下的作用：不但是数组和链表的延伸，又可以作为图的基础。总之，非常重要！

那什么是二叉树？

定义：二叉树是一棵树，并且二叉树的每个结点最多有两棵子树。二叉树的子树又分为左子树和右子树。

在这里插入图片描述

完全二叉树和满二叉树

二叉树有两种特殊的形态：完全二叉树和满二叉树。

完全二叉树：若二叉树的深度为 h，除第 h 层外，其它各层(1～h-1)的结点数目都达到最大值，第 h 层的结点都连续排列在最左边，这样的二叉树就是完全二叉树。

满二叉树：每一层的结点数目都达到最大值(包括最下面一层)。

在这里插入图片描述

二叉搜索树

Binary Search Tree (BST) 又叫二叉排序树。要求树中的结点可以按照某个规则进行比较，其定义如下：

  1. .左子树中所有结点的 key 值都比根结点的 key 值小，并且左子树也是二叉搜索树。

  2. 右子树中所有结点的 key 值都比根结点的 key 值大，并且右子树也是二叉搜索树。

在这里插入图片描述

基本操作

search：若 BST 为空，则直接NULL。若 BST 非空，则和根结点比较，若和根结点相等，表明找到了。若比根结点小，则在左子树中递归查找；若比根结点大，则在右子树中递归查找。

insert：若 BST 为空，则创建结点，将其作为根结点。若 BST 非空，则和根结点比较，若和根结点相等，则返回。若比根结点小，则在左子树中递归插入；若比根结点大，则在右子树中递归插入。

delete：分三种情况处理。

  1. 如果要删除结点没有孩子，那么直接将该结点删除就行了。

    在这里插入图片描述

  2. 如果要删除结点只有一个孩子，那么需要将父亲结点对应的指针，指向它唯一 的孩子结点。

    在这里插入图片描述

  3. 如果要删除结点有两个孩子，那么我们可以找到这个结点的右子树中最小结点 (或者左子树中最大结点)，把它替换到要删除的结点上，然后再删除右子树的最小结点 (或左子树的最大结点)。

    在这里插入图片描述

实现

代码

// BST.h
typedef char K;typedef struct tree_node {K key;struct tree_node* left;struct tree_node* right;
} TreeNode;typedef struct {TreeNode* root;
} BST;// API
BST* bst_create();
void bst_destroy(BST* tree);void bst_insert(BST* tree, K key);
TreeNode* bst_search(BST* tree, K key);
void bst_delete(BST* tree, K key);void bst_preorder(BST* tree); // 前序
void bst_inorder(BST* tree); // 中序
void bst_postorder(BST* tree); // 后序
void bst_levelorder(BST* tree); // 层序遍历

// BST.c
#include "BST.h"
#include <stdlib.h>
#include <stdio.h>BST* bst_create() {BST* bst = (BST*)malloc(sizeof(BST));bst->root = NULL;return bst;
}void freeTraversal(TreeNode* node) {// 终止条件if (node == NULL) {return;}freeTraversal(node->left); // 前freeTraversal(node->right); // 后printf("已释放结点 %d\n", node->key);free(node); // 中
}void bst_destroy(BST* tree) {TreeNode* root = tree->root;// 1.释放所有结点freeTraversal(root);// 2.释放BSTfree(tree);printf("已释放BST\n");
}void bst_insert(BST* tree, K key) {if (tree->root == NULL) { // 空树，直接作为根结点插入TreeNode* newNode = (TreeNode*)calloc(1, sizeof(TreeNode));newNode->key = key;tree->root = newNode;return;}// 迭代法TreeNode* cur = tree->root;while (cur) {if (key > cur->key) {// 大于if (cur->right == NULL) {TreeNode* newNode = (TreeNode*)calloc(1, sizeof(TreeNode));newNode->key = key;cur->right = newNode;return;} else {cur = cur->right;}}else if (key < cur->key) {// 小于if (cur->left == NULL) {TreeNode* newNode = (TreeNode*)calloc(1, sizeof(TreeNode));newNode->key = key;cur->left = newNode;return;} else {cur = cur->left;}}else return;} // cur == NULL
}TreeNode* bst_search(BST* tree, K key) {TreeNode* cur = tree->root;while (cur) {if (key > cur->key)cur = cur->right;else if (key < cur->key)cur = cur->left;else {printf("找到结点，结点值 %d\n", cur->key);return cur;}}printf("没找到结点\n");return NULL;
}TreeNode* deleteOneNode(TreeNode* targetNode) {if (targetNode == NULL) return NULL;if (targetNode->right == NULL) { // 右空 左空或不空TreeNode* tmpNode = targetNode->left;free(targetNode);return tmpNode;}// 右不空，左不空或空TreeNode* cur = targetNode->right;while (cur->left) {cur = cur->left;} // 右子树的最左结点 cur->left == NULLcur->left = targetNode->left;TreeNode* tmpNode = targetNode->right;free(targetNode);return tmpNode;
}void bst_delete(BST* tree, K key) {TreeNode* cur = tree->root;TreeNode* prev = NULL;while (cur) {if (cur->key == key) {if (prev == NULL) {// 要删除根节点tree->root = deleteOneNode(cur);}else if (prev->left && prev->left->key == key) {prev->left = deleteOneNode(cur);}else if (prev->right && prev->right->key == key) {prev->right = deleteOneNode(cur);}break;}prev = cur;if (key > cur->key) cur = cur->right;if (key < cur->key) cur = cur->left;}}/* **************************************** */
/*               深度优先遍历                 */
/* **************************************** */// 前序遍历（递归法）
void preorder_traversal(TreeNode* node) {// 终止条件if (node == NULL) {return;}printf(" %d", node->key); // 中preorder_traversal(node->left); // 左preorder_traversal(node->right); // 后
}void bst_preorder(BST* tree) {TreeNode* rootNode = tree->root;preorder_traversal(rootNode);
}// 中序遍历（递归法）
void inorder_traversal(TreeNode* node) {// 终止条件if (node == NULL) {return;}inorder_traversal(node->left); // 前printf(" %d", node->key); // 中inorder_traversal(node->right); // 后
}void bst_inorder(BST* tree) {TreeNode* rootNode = tree->root;inorder_traversal(tree->root);
}// 后序遍历（递归法）
void postorder_traversal(TreeNode* node) {// 终止条件if (node == NULL) {return;}postorder_traversal(node->left); // 前postorder_traversal(node->right); // 后printf(" %d", node->key); // 中
}void bst_postorder(BST* tree) {TreeNode* rootNode = tree->root;postorder_traversal(tree->root);
}/* **************************************** */
/*               广度优先遍历                 */
/* **************************************** */// 实现队列（基于链表）
typedef TreeNode* V;typedef struct que_node{V node;struct que_node* next;
} queNode;typedef struct {queNode* front;queNode* rear;int size;
} Queue;Queue* create_queue() {Queue* que = (Queue*)malloc(sizeof(Queue));que->front = NULL; // 队头que->rear = NULL; // 队尾que->size = 0;return que;
}void push_queue(Queue* q, V val) {queNode* newNode = (queNode*)malloc(sizeof(queNode));newNode->node = val;newNode->next = NULL;if (q->front == NULL) { // 空队列q->front = newNode;q->rear = newNode;q->size++;return;}q->rear->next = newNode;q->rear = newNode;q->size++;
}V pop_queue(Queue* q) {if (q->front == NULL) {return NULL;}queNode* tmpNode = q->front;if (q->size == 1)q->rear = NULL;q->front = tmpNode->next;q->size--;return tmpNode->node;
}V peek_queue(Queue* q) {if (q->front == NULL) {return NULL;}return q->front->node;
}bool is_empty(Queue* q) {return (q->front == NULL);
}/* 层序遍历（迭代法） */
// 层序遍历二叉树
void bst_levelorder(BST* tree) {Queue* que = create_queue();TreeNode* cur = tree->root;if (cur == NULL)return;push_queue(que, cur);while (!(is_empty(que))) {int num = que->size;while (num--) {cur = que->front->node;printf(" %d", que->front->node->key);pop_queue(que);if (cur->left) {push_queue(que, cur->left);}if (cur->right) {push_queue(que, cur->right);}}} 
}

// main.c
#include "BST.h"
#include <stdio.h>int main(void) {BST* bst = bst_create();bst_insert(bst, 1);bst_insert(bst, 2);bst_insert(bst, 5);bst_insert(bst, 7);bst_insert(bst, 5);bst_insert(bst, 9);bst_insert(bst, 4);// bst_search(bst, 5);// bst_search(bst, 100);printf("前序遍历结果：");bst_preorder(bst);printf("\n");printf("中序遍历结果：");bst_inorder(bst);printf("\n");printf("后序遍历结果：");bst_postorder(bst);printf("\n");printf("层序遍历结果：");bst_levelorder(bst);printf("\n");printf("已删除结点2\n");bst_delete(bst, 2);printf("已删除结点5\n");bst_delete(bst, 5);printf("前序遍历结果：");bst_preorder(bst);printf("\n");printf("中序遍历结果：");bst_inorder(bst);printf("\n");printf("后序遍历结果：");bst_postorder(bst);printf("\n");printf("层序遍历结果：");bst_levelorder(bst);printf("\n");bst_destroy(bst);
}

运行结果

在这里插入图片描述

分析

BST 增加、删除和查找的效率取决于它的高度 h。

insert：O(h)

search：O(h)

delete：O(h)

有 n 个结点的二叉树，高度最低时 h = log2n (完全二叉树)，高度最高时 h = n (退化成单链表)。但是我们上面实现的 BST 并不能保证树的高度为 O(logn)，更糟糕的是，随着动态的插入和删除元素，整棵树会慢慢地向一边倾斜。

要想保证二叉树增加，查找，删除的时间复杂度为 O(logn)，我们需要在添加结点和删除结点后，做一些调整操作，以保证二叉树的平衡。

常见的平衡二叉树有：AVL树、红黑树、伸展树、树堆等。其中应用最广，名气最大的当属红黑树了。

红黑树

2-3-4树(理论模型)

2-3-4 树有以下两个性质：

  • 2-3-4 树，在普通的二叉查找树上进行了扩展，它允许一个结点包含多个 key 值。

    2-结点：一个 key 值，两个孩子。

    3-结点：两个 key 值，三个孩子。

    4-结点：三个 key 值，四个孩子

  • 2-3-4树可以动态地保持完美平衡。

    所谓完美平衡，就是从根结点到任意一个叶子结点的路径都是一样长的。

在这里插入图片描述

查找

2-3-4 树的查找和普通 BST 的查找方式几乎一致。

在这里插入图片描述

插入

2-3-4 树的插入和普通 BST 相比，稍微复杂一点。

  • 如果是在2-结点中插入，直接将2-结点转换为3-结点。

    在这里插入图片描述

  • 如果是在3-结点中插入，直接将3-结点转换为4-结点。

在这里插入图片描述

  • 但是，如果是在4-结点中插入，该怎么办呢?

    在这里插入图片描述

这就需要将4-结点进行分裂了。

​在这里插入图片描述

但是，如果父结点也是4-结点，又该怎么办呢?

有两种解决方案：（不变式：当前结点肯定不是4-结点。）

a. 自底向上(Bayer, 1972) 用同样的方法分裂父结点

如果需要，我们会沿着查找路径自底向上依次分裂4-结点

b. 自顶向下(Guibas-Sedgewick, 1978)

在查找插入位置的时候，遇到4-结点就分裂

找到插入位置的时候，就可以直接插入了(当前结点肯定不是4-结点)

在这里插入图片描述

2-3-4树生长的例子在这里插入图片描述

在这里插入图片描述

性能分析

2-3-4树增加，删除，查找操作的时间复杂度取决于它的高度 h.

  • 最坏情况：h = log2N [所有结点都是2-结点]
  • 最好情况：h = log4N = (1/2)log2N [所有结点都是4-结点]

2-3-4树的性能是非常优秀的，举个例子

  • N = 100万时，2-3-4树的高度在 10 到 20 之间。
  • N = 10亿时，2-3-4树的高度在 15 到 30 之间。

实现

那我们如何实现 2-3-4 树呢？如果为2-结点，3-结点，4-结点分别编写不同的结点类型，则处理起来会非常麻烦，我们不得不处理各个结点类型之间得转换。那 2-3-4 树有没有一种更好得实现方式呢？

有的，答案就是红黑树！

红黑树(实际实现)

我们可以用普通的 BST 来表示 2-3-4 树。可是，我们该如何表示3-结点和4-结点呢？

红黑树给出了一个很好的解决方案，我们可以用"红色"的边来表示3-结点和4-结点。如下图所示：

在这里插入图片描述

3-结点有两种表示形式，而4-结点只有一种表示形式。

可是"边"是不存在的呀，它只是逻辑上的一个结构，我们又该如何表示边的颜色呢？

孩子结点到父亲结点的边是唯一的，所以我们可以用孩子结点的颜色，来表示孩子结点到父亲结点的边的颜色。

typedef struct treenode_s {int val;struct treenode_s* left;struct treenode_s* right;bool color;
}

这就是红黑树！

我们来看一看经典教科书(算法导论)对红黑树的定义：

一棵红黑树是满足下面红黑性质的二叉搜索树：
1. 每个结点或者是红色的，或者是黑色的
2. 根结点是黑色的
3. 叶子结点 (Nil) 是黑色的 (注：在算法导论中，叶子结点指得是 NULL 结点)
4. 如果一个结点是红色的，则它的两个子结点都是黑色的 （4-node 只有一种编码方式）
5. 对每个结点，从该结点到其所有后代叶子结点的路径上，包含相同数目的黑色结点。(黑高平衡， 2-3-4树是一个完美平衡的树)

2-3-4 树和红黑树之间是有一张对应关系的，不过这种对应关系不是 1-1 的 (3-结点可以倾向任意一边)。

在这里插入图片描述


http://www.ppmy.cn/ops/158790.html

相关文章

【个人开发】deepseed+Llama-factory 本地数据多卡Lora微调

【个人开发】deepseed+Llama-factory 本地数据多卡Lora微调

文章目录 1.背景2.微调方式2.1 关键环境版本信息2.2 步骤2.2.1 下载llama-factory2.2.2 准备数据集2.2.3 微调模式2.2.4 微调脚本 2.3 踩坑经验2.3.1 问题一&#xff1a;ValueError: Undefined dataset xxxx in dataset_info.json.2.3.2 问题二&#xff1a; ValueError: Target…
阅读更多...
STM32——HAL库开发笔记19（串口中断接收实验）（参考来源：b站铁头山羊）

STM32——HAL库开发笔记19（串口中断接收实验）（参考来源：b站铁头山羊）

本实验&#xff0c;我们以中断的方式使得串口发送数据控制LED的闪烁速度&#xff0c;发送1&#xff0c;慢闪&#xff1b;发送2&#xff0c;速度正常&#xff1b;发送3&#xff0c;快闪。 一、电路连接图 二、实现思路&CubeMx配置 1、实现控制LED的闪烁速度 uint32_t bli…
阅读更多...
Redisson分布式锁和同步器完整篇

Redisson分布式锁和同步器完整篇

Redisson分布式锁和同步器完整篇 在分布式系统中&#xff0c;如何确保多个服务实例之间的数据一致性和资源协调是一个关键挑战。Redisson作为基于Redis的Java客户端&#xff0c;提供了一套完整的分布式锁和同步器解决方案&#xff0c;帮助开发者轻松应对这些挑战。 本文将深入…
阅读更多...
DeepSeek-R1的使用及图解

DeepSeek-R1的使用及图解

目录 1 本地部署 DeepSeek 本地部署 DeepSeek 的优势 DeepSeek 本地部署的三大步骤 2 大语言模型基础 LLM 基础概念解析 大模型与特定数据集模型的区别 扩展规律&#xff08;Scaling Laws&#xff09; Transformer 架构概述 LLM 训练的核心方法 预训练阶段&#xff08…
阅读更多...
在 PyCharm 中接入deepseek的API的各种方法

在 PyCharm 中接入deepseek的API的各种方法

在 PyCharm 中接入 DeepSeek 的 API&#xff0c;通常需要以下步骤&#xff1a; 1. 获取 DeepSeek API 密钥 首先&#xff0c;确保你已经在 DeepSeek 平台上注册并获取了 API 密钥&#xff08;API Key&#xff09;。如果没有&#xff0c;请访问 DeepSeek 的官方网站注册并申请 …
阅读更多...
基于HTML5 Canvas 和 JavaScript 实现的烟花动画效果

基于HTML5 Canvas 和 JavaScript 实现的烟花动画效果

以下是一个使用 HTML5 Canvas 和 JavaScript 实现的烟花动画效果代码盒子： <!DOCTYPE html> <html> <head><title>烟花效果
阅读更多...
DDoS技术解析

DDoS技术解析

这里是Themberfue 今天我们不聊别的&#xff0c;我们聊聊著名的网络攻击手段之一的 DDoS&#xff0c;看看其背后的技术细节。 DoS 了解 DDoS 前&#xff0c;先来讲讲 DoS 是什么&#xff0c;此 DoS 而不是 DOS 操作系统啊。1996年9月6日&#xff0c;世界第三古老的网络服务提供…
阅读更多...
wps配置deepseek

wps配置deepseek

wps 配置deepseek https://e6jy62bip4.feishu.cn/docx/R09IdpU5HoADyDxcgfQcjpR8nnb
阅读更多...
最新文章

Copyright @ 2022~2023