c语言（二叉树）

第4章 二叉树和BST

树与二叉树

  1. 基本概念

    • 树是一种非线性结构，其严格的数学定义是：如果一组数据中除了第一个节点（第一个节点称为根节点，没有直接前驱节点）之外，其余任意节点有且仅有一个直接前驱，有零个或多个直接后继，这样的一组数据形成一棵树。这种特性简称为一对多的逻辑关系。即用于描述具有层次关系，类似组织架构关系的一种数据结构。
      在这里插入图片描述
    • 树的组成：根，分支，叶子

  2. 常见例子

    • 日常生活中，很多数据的组织形式本质上是一棵树。比如一个公司中的职员层级关系，一个学校中的院系层级关系，淘汰赛中的各次比赛队伍，一个家族中的族谱成员关系等，这些都是树状逻辑结构。由于树状结构表现出来都是具有层次的，因此也被称为层次结构。
      在这里插入图片描述

  3. 相关术语

    • 通常，在逻辑上表达一棵抽象的树状结构的时候，习惯于将树根放在顶部，树枝树杈向下生长，如下图所示。
      在这里插入图片描述

    • 对于一棵树来说，有如下基本术语：

      • 结点：树中的元素及其子树。
      • 根(root)：树的第一个节点，没有直接前驱。如上图中的A。
      • 双亲节点/父节点(parent)：某节点的直接前驱称为该节点的双亲节点，或成为父节点。例如上图中A是B的父节点。
      • 孩子节点/子节点(child)：某节点的直接后继称为该节点的孩子节点。例如上图中B、C、D均为A的孩子节点。
      • 节点的层次(level)：根节点所在的层次规定为第1层，其孩子所在的层次为第2层，后代节点以此类推。比如上图中节点E的层次是3。
      • 节点的度(degree)：一个节点拥有的孩子节点的总数，称为该节点的度。比如上图中节点B的度为2。
      • 叶子(leaf)：一棵树中度等于0的节点，被称为叶子，又称为终端节点。比如上图中K、L、F、G、M、I、J均为叶子。
      • 树的高度(height)：一棵树中所有节点的层次的最大值，称为这棵树的高度，又称为树的深度。比如上图的树的高度为4。
      • 有序树与无序树：一棵树中，如果某个节点的孩子节点之间是有次序的，则称这棵树为有序树，反之称为无序树。

二叉树

  1. 定义

    • 在各种不同的树状结构中，最常见也最重要的是二叉树(Binary Tree)，下面是二叉树的定义：
    • 有序树，任意节点的度小于等于2。
    • 比如如下这棵树就是一棵二叉树。其中8是根节点，14是10的右孩子（因为二叉树是有序树，因此严格区分左右），而13则是14的左孩子。
      在这里插入图片描述

  2. 特性

    • 第𝑖层上，最多有2𝑖−1个节点。
    • 高度为𝑘的二叉树，最多有2𝑘−1个节点。
    • 假设叶子数目为𝑛0，度为2的节点数目为𝑛2，则有：

二叉树的一般结构

  1. 满二叉树

    • 一棵深度为k，且有2^k - 1个结点的二叉树，称为满二叉树。这种树的特点是每一层上的结点数都是最大结点数。
    • 简单理解：除了叶子节点之外，其余节点的度都为2；其特点是：如果深度为 K，则节点数为 2^K - 1。
      在这里插入图片描述

  2. 完全二叉树

    • 在一棵二叉树中，除最后一层外，若其余层都是满的，或者最后一层是满的，或者是最后一层在右边缺少连续若干结点，则此二叉树为完全二叉树。
    • 简单理解：除最后一层叶子节点外。是一颗满二叉树，最后一层由右向左有连续缺省的0个，1个或多个节点。
      在这里插入图片描述

二叉搜索树(BST)

  1. 特点

    • 如果节点具有左子树，则左子树上所有节点都不大于该节点的值；
    • 节点具有右子树，则右子树上所有节点都不小于该节点的值；
    • 子树又是二叉搜索数。
      在这里插入图片描述

  2. 逻辑上的 内存中的

    • 二叉树 二叉树

  3. 二叉搜索树(BST)的组成

    • 根指针：指向根节点的指针变量。
    • 节点：
      • 数据域(存储的实际数据)。
      • 指针域 (左，右指针)。

结构设计

typedef int data_t;typedef struct _node
{data_t data; // 数据域struct _node *left; // 左子树指针struct _node *right;// 右子树指针
}NODE;

二叉树 (BST) 的算法

  1. 创建二叉树
int btree_create(NODE** root, data_t data);
  1. 二叉树数据添加
int btree_add(NODE** root, data_t data);
  1. 示例图
    在这里插入图片描述

二叉树数据遍历

  1. 前序遍历 (先序遍历，即 根左右)
void Preorder(const NODE* root);

  • 前序遍历通俗的说就是从二叉树的根结点出发，先输出根结点数据，然后输出左结点，最后输出右结点的数据。
    在这里插入图片描述

  • 从根结点出发，则第一次到达结点 A，故输出 A；继续向左访问，第一次访问结点 B，故输出 B；按照同样规则，输出 D，输出 H；当到达叶子结点 H，返回到 D，此时已经是第二次到达 D，故不在输出 D，进而向 D 右子树访问，D 右子树不为空，则访问至 I，第一次到达 I，则输出 I；I 为叶子结点，则返回到 D，D 左右子树已经访问完毕，则返回到 B，进而到 B 右子树，第一次到达 E，故输出 E；向 E 左子树，故输出 J；按照同样的访问规则，继续输出 C、F、G。

  • 前序遍历输出结果：ABDHIEJCFG

  1. 中序遍历 (即 左根右)
void Midorder(const NODE* root);

  • 中序遍历通俗的说就是从二叉树的根结点出发，先输出左结点数据，然后输出根结点，最后输出右结点的数据。
    -在这里插入图片描述

  • 从根结点出发，则第一次到达结点 A，不输出 A，继续向左访问，第一次访问结点 B，不输出 B；继续到达 D，H；

  • 到达 H，H 左子树为空，则返回到 H，此时第二次访问 H，故输出 H；H 右子树为空，则返回至 D，此时第二次到达 D，故输出 D；由 D 返回至 B，第二次到达 B，故输出 B；按照同样规则继续访问，输出 J、E、A、F、C、G；

  • 中序遍历输出结果：HDIBJEAFCG

  1. 后序遍历 (即 左右根)
void Postorder(const NODE* root);

  • 后序遍历通俗的说就是从二叉树的根结点出发，先输出左结点数据，然后输出右结点，最后输出根结点的数据。
    在这里插入图片描述

  • 从根结点出发，则第一次到达结点 A，不输出 A，继续向左访问，第一次访问结点 B，不输出 B；继续到达 D，H；

  • 到达 H，H 左子树为空，则返回到 H，此时第二次访问 H，不输出 H；H 右子树为空，则返回至 H，此时第三次到达 H，故输出 H；由 H 返回至 D，第二次到达 D，不输出 D；继续访问至 I，I 左右子树均为空，故第三次访问 I 时，输出；返回至 D，此时第三次到达 D，故输出 D；按照同样规则继续访问，输出 J、E、B、F、G、C，A；

  • 后序遍历输出为：HIDJEBFGCA

  1. 层序遍历
void Levelorder(const NODE* root);

二叉树数据查询

NODE* btree_find(const NODE* root, data_t data);
  1. 从根结点出发
  2. 如果比根节点小，那么就去其左子树找
  3. 如果比根节点大就去其右子树找
  4. 找到叶子都没找到， 就代表查找失败
    在这里插入图片描述

二叉树数据更新

隐藏过程

复制

int btree_update(const NODE* root, data_t old, data_t newdata);

二叉树回收

隐藏过程

复制

void btree_destroy(NODE** root);

二叉树数据删除

  1. 原则：将待删除的节点尽量转换为删除叶子节点，因为删除叶子节点对 BST 树影响是最小的。

  2. 思路

    ：

    • int btree_delete(NODE** root, data_t data);
    • 从根节点开始遍历 BST 找到待删除的节点；
    • 对待删除的节点状态进行判断，如果节点有左子树，找到左子树中最大的节点，然后利用左子树中最大的节点数据替换待删除的节点数据，删除左子树中最大的节点；左子树中最大的节点大概率是叶子节点。
    • 如果节点只有右子树，找到右子树中最小的节点，然后利用右子树中最小的节点数据替换待删除的节点数据，删除右子树中最小的节点；右子树中最小的节点大概率是叶子节点。
    • 如果待删除节点是叶子节点，直接删除。

二叉树 (BST) 完整实现

队列实现

SQueue.h
#ifndef __SQUEUE_H
#define __SQUEUE_H#include "btree.h"typedef NODE* type_t;typedef struct
{type_t *pData;int size;int head;![在这里插入图片描述](https://i-blog.csdnimg.cn/direct/df354bd58cc5428aa589a2e8aae6fada.png#pic_center)int tail;
}SQueue;int SQ_init(SQueue *q, int num);
int SQ_isfull(SQueue *q);
int SQ_isempty(SQueue *q);
int SQ_push(SQueue *q, type_t data);
int SQ_pop(SQueue *q, type_t *data);
int SQ_free(SQueue *q);
#endif

SQueue.c
#include <stdlib.h>
#include "SQueue.h"int SQ_init(SQueue* q, int num)
{q -> pData = (type_t*)calloc(sizeof(type_t), num);if(q -> pData == NULL)return -1;q -> size = num;q -> head = q -> tail = 0;return 0;
}int SQ_isfull(SQueue *q)
{return (q -> tail + 1) % q -> size == q -> head;
}int SQ_isempty(SQueue *q)
{return q -> tail == q -> head;
}int SQ_push(SQueue *st, type_t data)
{if(SQ_isfull(st))return -1;st -> pData[st -> tail] = data;st -> tail = (st -> tail + 1) % st -> size;return 0;
}int SQ_pop(SQueue *st, type_t *data)
{if(SQ_isempty(st))return -1;*data = st -> pData[st -> head];st -> head = (st -> head + 1) % st -> size;return 0;
}int SQ_free(SQueue *st)
{if(st -> pData){free(st->pData);st -> pData = NULL;}st -> head = st -> tail = 0; 
}

树的实现

btree.h
#ifndef __BTREE_H
#define __BTREE_Htypedef int data_t;typedef struct _node
{data_t data; // 节点上的数据struct _node *left; // 该节点左侧子节点的地址struct _node *right;// 该节点右侧子节点的地址
}NODE;// 创建搜索二叉树
int btree_create(NODE** root, data_t data);
// 二叉树数据添加
int btree_add(NODE** root, data_t data);
// 二叉树数据删除
int btree_delete(NODE** root, data_t data);// 二叉树前序遍历
void Preorder(const NODE* root);
// 二叉树中序遍历
void Midorder(const NODE* root);
// 二叉树后序遍历
void Postorder(const NODE* root);
// 二叉树层序遍历
void Levelorder(const NODE* root);
// 二叉树数据查询
NODE* btree_find(const NODE* root, data_t data);
// 更新二叉树数据old 为 newdata
int btree_update(const NODE* root, data_t old, data_t newdata);
// 二叉树回收
void btree_destroy(NODE** root);#endif

btree.c
#include "btree.h"
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include "SQueue.h"@function: int btree_create(NODE** root, data_t data)
@function:
@ret
@function :
@ret
@brief: 创建搜索二叉树
@argument: root: 根指针地址
@argument: data: 存储的数据
成功
-1 失败int btree_create(NODE** root, data_t 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: 添加的数据
成功
-1 失败
*/
int btree_add(NODE** root, data_t data)
{NODE* pNew = (NODE*)malloc(sizeof(NODE));if(!pNew)return -1;pNew -> data = data;pNew -> left = NULL;pNew -> right = NULL;NODE* p = *root;if(!p){*root = pNew;return 0;}while(p){NODE* q = p;if(memcmp(&data, &(p -> data), sizeof(data_t)) < 0)p = p -> left;elsep = p -> right;if(memcmp(&data, &(q -> data), sizeof(data_t)) < 0)q -> left = pNew;elseq -> right = pNew;}return 0;
} /*
@function: int btree_delete(NODE** root, data_t data)
@brief: 二叉树数据删除
@argument: root: 根指针地址
@argument: data: 待删除的节点数据
成功
-1 失败
*/
int btree_delete(NODE** root, data_t data)
{/*原则:

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.rhkb.cn/news/412151.html

如若内容造成侵权/违法违规/事实不符，请联系长河编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

Python相关系数导图

Python相关系数导图

&#x1f3af;要点 量化变量和特征关联绘图对比皮尔逊相关系数、斯皮尔曼氏秩和肯德尔秩汽车性价比相关性矩阵热图大流行病与资产波动城镇化模型预测交通量宝可梦类别特征非线性依赖性捕捉向量加权皮尔逊相关系数量化图像相似性 Python皮尔逊-斯皮尔曼-肯德尔 皮尔逊相关系…
阅读更多...
Node.js原生开发脚手架工具（下）

Node.js原生开发脚手架工具（下）

前言 在现代软件开发中&#xff0c;脚手架工具成为提高开发效率和一致性的关键利器。使用Node.js原生开发自己的脚手架工具不仅能帮助自动化常见任务&#xff0c;还能根据具体需求进行高度定制。Node.js的异步非阻塞特性和丰富的模块系统使其成为构建这种工具的理想选择。本篇文…
阅读更多...
★ 算法OJ题 ★ 力扣202 - 快乐数

★ 算法OJ题 ★ 力扣202 - 快乐数

Ciallo&#xff5e;(∠・ω< )⌒☆ ~ 今天&#xff0c;我将和大家一起做一道双指针算法题--快乐数~ 目录 一 题目 二 算法解析 三 编写算法 一 题目 202. 快乐数 - 力扣&#xff08;LeetCode&#xff09; 二 算法解析 题⽬告诉我们&#xff0c;当我们不断重复操作…
阅读更多...
Java设计模式之外观模式详细讲解和案例示范

Java设计模式之外观模式详细讲解和案例示范

1. 引言 在软件开发过程中&#xff0c;复杂的系统往往包含许多子系统和模块&#xff0c;随着系统功能的增加&#xff0c;模块之间的交互也变得更加复杂。这种复杂性可能会导致系统的可维护性和扩展性降低。外观模式&#xff08;Facade Pattern&#xff09;是一种结构型设计模式…
阅读更多...
java同步概念

java同步概念

同步&#xff08;Synchronization&#xff09;在Java多线程编程中是一个既重要又复杂的概念。它涉及到如何确保多个线程在访问共享资源时能够保持数据的一致性和完整性&#xff0c;避免出现竞态条件&#xff08;Race Condition&#xff09;等问题。 同步的基本概念 同步的主要目…
阅读更多...
深入解析体育馆蓝牙导航系统的技术实现与应用

深入解析体育馆蓝牙导航系统的技术实现与应用

技术爱好者与开发者们&#xff0c;您是否在大型体育馆内常常为找不到洗手间、休息区或观赛区而烦恼&#xff1f;随着科技的进步&#xff0c;我们团队倾力打造了体育馆蓝牙导航系统&#xff0c;专为解决这一痛点而生。本系统利用先进的蓝牙信标技术和精准的室内定位算法&#xf…
阅读更多...
YOLO | YOLO目标检测算法（YOLO-V1）

YOLO | YOLO目标检测算法（YOLO-V1）

github&#xff1a;https://github.com/MichaelBeechan CSDN&#xff1a;https://blog.csdn.net/u011344545 YOLO目标检测算法 YOLO V1概述&#xff08;2016&#xff09; YOLO V1概述&#xff08;2016&#xff09; 经典的One-stage方法 YOLO&#xff1a;You Only Look Once 把…
阅读更多...
【河北航空-注册安全分析报告-无验证方式导致安全隐患】

【河北航空-注册安全分析报告-无验证方式导致安全隐患】

前言 由于网站注册入口容易被黑客攻击&#xff0c;存在如下安全问题&#xff1a; 1. 暴力破解密码&#xff0c;造成用户信息泄露 2. 短信盗刷的安全问题&#xff0c;影响业务及导致用户投诉 3. 带来经济损失&#xff0c;尤其是后付费客户&#xff0c;风险巨大&#xff0c;造…
阅读更多...
ZaKi：Ingonyama的Prover market基础设施

ZaKi：Ingonyama的Prover market基础设施

1. 引言 Ingonyama团队预计在不久的将来会出现大量去中心化证明市场&#xff08;Prover market&#xff09;。这些市场的独特之处在于高可用性和高性能的基础设施&#xff0c;以及强大的安全性和透明度保障。 2. 证明市场的出现 零知识 (ZK) Rollups&#xff0c;如 Starknet…
阅读更多...
【如何用本机的Navicat远程连接到ubuntu服务器上的mysql】

【如何用本机的Navicat远程连接到ubuntu服务器上的mysql】

文章目录 版本一、ubuntu服务器安装mysql5二、远程连接——mysql配置1.创建新mysql用户2.修改配置文件3.查看端口是否开启 三、远程连接——Navicat 版本 mysql:5.7.32 服务器&#xff1a;ubuntu20.04 PC:win10 一、ubuntu服务器安装mysql5 因为ubuntu20.04默认mysql其实是my…
阅读更多...
命令模式详解

命令模式详解

命令模式 简介:命令模式将一个请求封装为一个对象&#xff0c;从而使你可以用不同的请求对客户进行参数化&#xff0c;对请求排队或记录请求日志&#xff0c;以及支持可撤销的操作。 人话: 总体来说, 就是一个命令类, 一个执行类, 命令类包括执行类, 然后在外部添加一个总的管…
阅读更多...
【数模修炼之旅】10 遗传算法 深度解析（教程+代码）

【数模修炼之旅】10 遗传算法 深度解析（教程+代码）

【数模修炼之旅】10 遗传算法 深度解析&#xff08;教程代码&#xff09; 接下来 C君将会用至少30个小节来为大家深度解析数模领域常用的算法&#xff0c;大家可以关注这个专栏&#xff0c;持续学习哦&#xff0c;对于大家的能力提高会有极大的帮助。 1 遗传算法介绍及应用 …
阅读更多...
Zookeeper官网Java示例代码解读（一）

Zookeeper官网Java示例代码解读（一）

2024-08-22 1. 基本信息 官网地址&#xff1a; https://zookeeper.apache.org/doc/r3.8.4/javaExample.html 示例设计思路 Conventionally, ZooKeeper applications are broken into two units, one which maintains the connection, and the other which monitors data. I…
阅读更多...
在随机点实现凸包包围游戏地区

在随机点实现凸包包围游戏地区

讲解视频在连接点之后&#xff0c;想起来两年前看数学书&#xff0c;记住凸包二字&#xff0c;连接敌人外围点&#xff0c;意外找到凸包算法_哔哩哔哩_bilibili //author bilibili 民用级脑的研发记录 // 开发环境 小熊猫c 2.25.1 raylib 版本 4.5 // 2024-7-14 // AABB 碰撞…
阅读更多...
USB3202N多功能数据采集卡16位模拟量250K频率LabVIEW采集卡

USB3202N多功能数据采集卡16位模拟量250K频率LabVIEW采集卡

品牌&#xff1a;阿尔泰科技 系列&#xff1a;多功能数据采集卡 概述&#xff1a; USB3202N多功能数据采集卡&#xff0c;LabVIEW无缝连接&#xff0c;提供图形化API函数&#xff0c;提供8通道&#xff08;RSE、NRSE&#xff09;、4通道&#xff08;DIFF&#xff09;模拟量输…
阅读更多...
《HelloGitHub》第 101 期

《HelloGitHub》第 101 期

兴趣是最好的老师&#xff0c;HelloGitHub 让你对编程感兴趣&#xff01; 简介 HelloGitHub 分享 GitHub 上有趣、入门级的开源项目。 github.com/521xueweihan/HelloGitHub 这里有实战项目、入门教程、黑科技、开源书籍、大厂开源项目等&#xff0c;涵盖多种编程语言 Python、…
阅读更多...
DataWhale AI夏令营 2024大运河杯-数据开发应用创新赛-task2

DataWhale AI夏令营 2024大运河杯-数据开发应用创新赛-task2

DataWhale AI夏令营 2024大运河杯-数据开发应用创新赛 YOLO(You Only Look Once)上分心得分享 YOLO(You Only Look Once) YOLO算的上是近几年最火的目标检测模型了&#xff0c;被广泛的应用在工业、学术等领域。 YOLOv1&#xff08;You Only Look Once 第一版&#xff09;于 2…
阅读更多...
CTFHub SSRF靶场通关攻略

CTFHub SSRF靶场通关攻略

内网访问 首先进入环境 在url后面输入 http://127.0.0.1/flag.php访问&#xff0c;得出flag 伪协议读取文件 进入环境后再url后面拼接 file:///var/www/html/flag.php 访问后是&#xff1f;&#xff1f;&#xff1f;&#xff0c;那么我们F12检查源码得出flag 端口扫描 我们进行…
阅读更多...
若依微服务ruoyi-auth在knife4j中不显示问题解决

若依微服务ruoyi-auth在knife4j中不显示问题解决

关于若依微服务ruoyi-auth在knife4j中不显示问题解决 解决办法 一、添加swagger依赖文件 在ruoyi-auth模块下的pom.xml文件中添加ruoyi-common-swagger依赖 <!-- RuoYi Common Swagger --><dependency><groupId>com.ruoy
阅读更多...
Python网络爬虫模拟登录与验证解析

Python网络爬虫模拟登录与验证解析

内容导读 使用Selenium模拟登录 使用Cookies登录网站 模拟表单登录网站 爬虫识别简单的验证码 实例解析 一、使用Selenium模拟登录 1、为什么要模拟登录 在互联网上存在大量需要登录才能访问的网站&#xff0c;要爬取这些网站&#xff0c;就需要学习爬虫的模拟登录。对…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023

友情链接： 我的编程经验分享 一条长河网 尧图网站开发