c语言（二叉树）

news/2024/9/18 13:17:34/ 标签: 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.ppmy.cn/news/1518093.html

相关文章

华为OD机试(C卷,200分)- 园区参观路径

华为OD机试(C卷,200分)- 园区参观路径

题目描述 园区某部门举办了Family Day，邀请员工及其家属参加； 将公司园区视为一个矩形，起始园区设置在左上角，终点园区设置在右下角； 家属参观园区时，只能向右和向下园区前进，求从起始园区到终点园区会有多少条不同的参观路径。 输入描述 第一行为园区的长和宽； 后…
阅读更多...
为什么要选择JDK15.0.2

为什么要选择JDK15.0.2

JDK16开始&#xff0c;Oracle移除了JDK中JavaSE的很多类。导致我们用IDK15以后的版本做项目&#xff0c;Maven导入的一些第三方依赖会出现找不到ava工具类的情况&#xff0c;而且更有甚者异常信息也不会提示找不到哪些类&#xff0c;直接就报运行错误。这就让我们调试程序无从下…
阅读更多...
【软件文档】软件质量保证计划书（Word完整版）

【软件文档】软件质量保证计划书（Word完整版）

1 概述 2 质量目标 3 项目基本情况 4 资源 4.1 人员 4.1.1 组织结构 4.1.2 职责 4.2 工具及设施 5 质量保证的主要工作 6 质量保证工作量估算 7 质量保证工作提交的产物 8 变更管理 9 评价标准 10 形成的记录 软件全套资料部分文档清单&#xff1a; 工作安排任务书&#xff0c;…
阅读更多...
aspose.pdf实现图片转pdf

aspose.pdf实现图片转pdf

/*** 图片转pdf*/ public static void ImagesToPdf(){String folderPath "D:\\Desktop\\xuanku";File folder new File(folderPath);List<String> images new ArrayList<>();// 检查文件夹是否存在if (folder.exists() && folder.isDirectory…
阅读更多...
【论文速读】| ARVO: 开源软件可重现漏洞的全景图

【论文速读】| ARVO: 开源软件可重现漏洞的全景图

本次分享论文&#xff1a;ARVO: Atlas of Reproducible Vulnerabilities for Open Source Software 基本信息 原文作者&#xff1a;Xiang Mei, Pulkit Singh Singaria, Jordi Del Castillo, Haoran Xi, Abdelouahab (Habs) Benchikh, Tiffany Bao, Ruoyu Wang, Yan Shoshitai…
阅读更多...
js基础速成-条件语句

js基础速成-条件语句

条件语句 条件语句用于根据不同的条件做出决策。 默认情况下&#xff0c;JavaScript 中的语句是从上到下顺序执行的。如果处理逻辑需要&#xff0c;可以通过两种方式改变执行的顺序&#xff1a; 条件执行&#xff1a;如果某个表达式为真&#xff0c;将执行一个或多个语句的代…
阅读更多...
一起搭WPF之列表数据绑定

一起搭WPF之列表数据绑定

一起搭WPF之列表数据绑定 1 前言2 数据绑定2.1 前端2.2 后端实现2.2.1 界面后台2.2.2 模型与逻辑 3 问题3.2 解决 总结 1 前言 之前已经简单介绍了列表的大致设计&#xff0c;在设计完列表界面后&#xff0c;我们可以开展列表的数据绑定&#xff0c;在前端显示我们的数据&…
阅读更多...
房产报备小程序房产报备系统源码搭建方案

房产报备小程序房产报备系统源码搭建方案

房产客户报备小程序开发&#xff0c;php开发语言&#xff0c;前端是uniapp。 房产报备小程序三个端&#xff1a;报备端&#xff08;经纪人报备客户&#xff09;&#xff0c;确客端&#xff08;员工确认报备的客户&#xff09;&#xff0c;管理后台 一 报备端 经纪人报备客户…
阅读更多...
特异性心肌细胞靶向肽(PCM)；WLSEAGPVVTVRALRGTGSW；CAS:771479-86-8

特异性心肌细胞靶向肽(PCM)；WLSEAGPVVTVRALRGTGSW；CAS:771479-86-8

【特异性心肌细胞靶向肽(PCM) 简介】 特异性心肌细胞靶向肽&#xff08;PCM&#xff09;是一种设计用于识别和结合心肌细胞特有的受体或分子标记的多肽序列。PCM可以通过其氨基酸序列的特定配置和表面特性实现对心肌细胞的选择性靶向&#xff0c;从而在心脏病治疗中递送药物、作…
阅读更多...
Linux文件编程（进阶）

Linux文件编程（进阶）

文章目录 Linux文件编程内核数据结构重定向dup2函数代码示例&#xff1a;将定义为输入重定向符号&#xff0c;将-定义为输出重定向符号 fcntl函数代码示例&#xff1a;使用O_APPEND标志位保证原子操作 I/O处理方式代码示例&#xff1a;阻塞I/O模型代码示例&#xff1a;非阻塞I/…
阅读更多...
Nosql数据库redis集群配置详解

Nosql数据库redis集群配置详解

一、Redis的安装 环境介绍&#xff1a; 一主双从&#xff1a;10&#xff08;redis-node1&#xff09;主&#xff0c;20&#xff08;redis-node2&#xff09; 30&#xff08;redis-node3&#xff09;从——使用的是红帽9.1系统 源码安装redis [rootredis-node1 ~]# tar zxf red…
阅读更多...
Ceruletide 雨蛙素；雨蛙肽；硫酸化蓝肽 简介

Ceruletide 雨蛙素；雨蛙肽；硫酸化蓝肽 简介

目录号 M9316 Ceruletide 雨蛙素&#xff1b;雨蛙肽&#xff1b;硫酸化蓝肽 Ceruletide (Caerulein) 是从澳大利亚青蛙皮肤中分离的生物活性十肽&#xff0c;是一种缩胆囊素受体 (cholecystokinin receptor) 激动剂。此外&#xff0c;Ceruletide还可用于构建小鼠急性胰腺炎模型…
阅读更多...
强烈推荐！大模型辅助软件开发

强烈推荐！大模型辅助软件开发

图书推荐 作者介绍 很喜欢作者在书上的这句话了&#xff1a;是人类工程师的能力&#xff0c;而不是大模型的能力&#xff0c;决定了大模型协作式开发的上限。 本书内容 软件开发正在经历一场前所未有的范式变革。人工智能的飞速发展&#xff0c;特别是大型语言模型所取得的成…
阅读更多...
tortoisegit突然停止工作

tortoisegit突然停止工作

TortoiseGit突然停止工作可能由多种原因引起&#xff0c;以下是一些可能的原因及相应的解决方案&#xff1a; 可能原因及解决方案 Git进程冲突 描述&#xff1a;当TortoiseGit检测到有其他Git进程正在运行或之前崩溃未清理完全时&#xff0c;可能会出现冲突&#xff0c;导致T…
阅读更多...
鸿蒙开发5.0【基于Swiper的页面布局】

鸿蒙开发5.0【基于Swiper的页面布局】

场景一&#xff1a;Swiper页面支持自定义动画 方案&#xff1a; 给Swiper组件设置.nextMargin(50).prevMargin(50)属性。 给Swiper组件添加onChange事件&#xff0c;设置当前this.currentIndexindex&#xff0c;当currentIndex为首页或者尾页时&#xff0c;设置上一张以及下一…
阅读更多...
黑马JavaWeb开发笔记10(前端完结)——Vue路由介绍入门、前端工程打包、nginx前端部署

黑马JavaWeb开发笔记10(前端完结)——Vue路由介绍入门、前端工程打包、nginx前端部署

文章目录 前言一、Vue路由1. 介绍2. 路由入门 二、打包部署1. 前端工程打包2. 部署前端工程2.1 nginx介绍2.2 部署 总结 前言 本篇文章是2023年最新黑马JavaWeb开发笔记10&#xff1a;Vue路由介绍&入门、前端工程打包、nginx前端部署的总结&#xff0c;帮助需要学习Web开发…
阅读更多...
Python自动化测试requests库深度详解

Python自动化测试requests库深度详解

前言 发送HTTP请求 import requests# 登录的接口地址url http://............/login# 登录的参数params {"mobile_phone": 18300000000,"pwd": 12345678}# 请求头headers {X-Lemonban-Media-Type: lemonban.v2}# 发送登录请求# 请求类型为 Content-Typ…
阅读更多...
（二十）Flink Paimon

（二十）Flink Paimon

数据湖、湖仓一体是当前大数据领域技术发展的重要趋势。近几年开源数据湖技术如 Apache Hudi、Apache Iceberg、Apache Paimon、DeltaLake 等不断涌现，基于湖仓一体架构的统一元数据管理、数据治理也越来越受到关注。从传统数仓到数据湖、湖仓一体架构，从流批一体计算到基于数…
阅读更多...
YOLOv9改进策略【损失函数篇】| 利用MPDIoU，加强边界框回归的准确性

YOLOv9改进策略【损失函数篇】| 利用MPDIoU，加强边界框回归的准确性

一、背景 目标检测和实例分割中的关键问题&#xff1a; 现有的大多数边界框回归损失函数在不同的预测结果下可能具有相同的值&#xff0c;这降低了边界框回归的收敛速度和准确性。 现有损失函数的不足&#xff1a; 现有的基于 ℓ n \ell_n ℓn​范数的损失函数简单但对各种尺度…
阅读更多...
python学习10-机器学习了解

python学习10-机器学习了解

AI(Artificial Intelligence)是最广泛的概念&#xff0c;是让机器拥有人和组织的能力&#xff0c;执行复杂的任务。下面分为机器人、语言处理、机器学习、深度学习等。机器学习是人工智能的一个子领域&#xff0c;它关注的是如何让计算机通过大量的数据自动学习和训练来对人的能…
阅读更多...
最新文章

Copyright @ 2022~2023

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