【数据结构】树与二叉树（廿六）：树删除指定结点及其子树（算法DS）

文章目录

  • 5.3.1 树的存储结构
    • 5. 左儿子右兄弟链接结构
  • 5.3.2 获取结点的算法
    • 1. 获取大儿子、大兄弟结点
    • 2. 搜索给定结点的父亲
    • 3. 搜索指定数据域的结点
    • 4. 删除结点及其左右子树
      • a. 逻辑删除与物理删除
      • b. 算法DST
      • c. 算法解析
      • d. 代码实现
        • 递归释放树
        • 算法DS
      • e. 算法测试
    • 5. 代码整合

5.3.1 树的存储结构

5. 左儿子右兄弟链接结构

【数据结构】树与二叉树（十九）：树的存储结构——左儿子右兄弟链接结构（树、森林与二叉树的转化）
  左儿子右兄弟链接结构通过使用每个节点的三个域（FirstChild、Data、NextBrother）来构建一棵树，同时使得树具有二叉树的性质。具体来说，每个节点包含以下信息：

  1. FirstChild： 存放指向该节点的大儿子（最左边的子节点）的指针。这个指针使得我们可以迅速找到一个节点的第一个子节点。
  2. Data： 存放节点的数据。
  3. NextBrother： 存放指向该节点的大兄弟（同一层中右边的兄弟节点）的指针。这个指针使得我们可以在同一层中迅速找到节点的下一个兄弟节点。

  通过这样的结构，整棵树可以用左儿子右兄弟链接结构表示成一棵二叉树。这种表示方式有时候被用于一些特殊的树结构，例如二叉树、二叉树的森林等。这种结构的优点之一是它更紧凑地表示树，而不需要额外的指针来表示兄弟关系。
在这里插入图片描述

   A
  /|\
 B C D
  / \
 E   F

A
|
B -- C -- D
     |
     E -- F

即：

      A
     / 
    B   
    \
	  C
  	 / \ 
  	E   D
  	 \
  	  F

在这里插入图片描述

5.3.2 获取结点的算法

1. 获取大儿子、大兄弟结点

【数据结构】树与二叉树（二十）：树获取大儿子、大兄弟结点的算法（GFC、GNB）

2. 搜索给定结点的父亲

【数据结构】树与二叉树（廿四）：树搜索给定结点的父亲（算法FindFather）

3. 搜索指定数据域的结点

【数据结构】树与二叉树（廿五）：树搜索指定数据域的结点（算法FindTarget）

4. 删除结点及其左右子树

a. 逻辑删除与物理删除

  • 逻辑删除（Logical Deletion）
    • 逻辑删除通常是指在数据结构中标记某个节点为被删除的状态，而不是真正地从内存中删除它。
  • 物理删除（Physical Deletion）
    • 物理删除是指真正地从内存中释放某个节点及其子树的内存。

b. 算法DST

在这里插入图片描述

c. 算法解析

  1. 检查输入参数t和p是否为空，如果其中任一参数为空，则返回。

  2. 调用FindFather(t, p.result)函数，找到以t为根的树中根为p的子树的父节点

  3. 如果找不到父节点（即result为空），则表示根为p的子树不存在，直接删除节点p并返回。

  4. 如果找到了父节点，算法继续执行，检查父节点的第一个子节点是否为p

    • 如果第一个子节点是p，则将父节点的第一个子节点设置为p的下一个兄弟节点（即FirstChild(result)←NextBrother( p)），然后删除节点p并返回。
    • 如果第一个子节点不是p，则算法使用一个循环找到p的下一个兄弟节点q，将q的下一个兄弟节点设置为p的下一个兄弟节点（即NextBrother(q)←NextBrother( p)）。最后，删除节点p并返回。

d. 代码实现

递归释放树
void freeTree(TreeNode* root) {
    if (root != NULL) {
        freeTree(root->firstChild);
        freeTree(root->nextBrother);
        free(root);
    }
}
算法DS
void DelSubtree(TreeNode* t, TreeNode* p) {
    if (t == NULL || p == NULL) {
        return;
    }

    TreeNode* result = NULL;
    FindFather(t, p, &result);

    if (result == NULL) {
        return; // 未找到父亲节点
    }

    if (result->firstChild == p) {
        result->firstChild = p->nextBrother;
        freeTree(p);
        return;
    }

    TreeNode* q = result->firstChild;

    while (q != NULL && q->nextBrother != p) {
        q = q->nextBrother;
    }

    if (q != NULL) {
        q->nextBrother = p->nextBrother;
        freeTree(p);
    }
}

e. 算法测试

int main() {
    // 构建左儿子右兄弟链接结构的树
    TreeNode* A = createNode('A');
    TreeNode* B = createNode('B');
    TreeNode* C = createNode('C');
    TreeNode* D = createNode('D');
    TreeNode* E = createNode('E');
    TreeNode* F = createNode('F');

    A->firstChild = B;
    B->nextBrother = C;
    C->nextBrother = D;
    C->firstChild = E;
    E->nextBrother = F;

    // 要删除的子树的根节点
    TreeNode* subtreeRoot = F;

    // 使用算法 DelSubtree 删除子树
    DelSubtree(A, subtreeRoot);

    // 输出删除子树后的树结构
    printf("Tree after deleting subtree rooted at %c:\n", subtreeRoot->data);

    // 层次遍历算法
    printf("Level Order: \n");
    LevelOrder(A);
    printf("\n");

    // 释放树节点
    freeTree(A);

    return 0;
}
  • 继续采用先前系列文章的树结构
  • 删除指定结点subtreeRoot
  • 层次遍历删除subtreeRoot结点及其子树后的树
  • 释放整棵树
    在这里插入图片描述

5. 代码整合

#include <stdio.h>
#include <stdlib.h>

// 定义树节点
typedef struct TreeNode {
    char data;
    struct TreeNode* firstChild;
    struct TreeNode* nextBrother;
} TreeNode;

// 创建树节点
TreeNode* createNode(char data) {
    TreeNode* newNode = (TreeNode*)malloc(sizeof(TreeNode));
    if (newNode != NULL) {
        newNode->data = data;
        newNode->firstChild = NULL;
        newNode->nextBrother = NULL;
    }
    return newNode;
}

// 释放树节点及其子树
void freeTree(TreeNode* root) {
    if (root != NULL) {
        freeTree(root->firstChild);
        freeTree(root->nextBrother);
        free(root);
    }
}

// 算法GFC：获取大儿子结点
TreeNode* getFirstChild(TreeNode* p) {
    if (p != NULL && p->firstChild != NULL) {
        return p->firstChild;
    }
    return NULL;
}

// 算法GNB：获取下一个兄弟结点
TreeNode* getNextBrother(TreeNode* p) {
    if (p != NULL && p->nextBrother != NULL) {
        return p->nextBrother;
    }
    return NULL;
}


// 队列结构
typedef struct QueueNode {
    TreeNode* treeNode;
    struct QueueNode* next;
} QueueNode;

typedef struct {
    QueueNode* front;
    QueueNode* rear;
} Queue;

// 初始化队列
void initQueue(Queue* q) {
    q->front = NULL;
    q->rear = NULL;
}

// 入队列
void enqueue(Queue* q, TreeNode* treeNode) {
    QueueNode* newNode = (QueueNode*)malloc(sizeof(QueueNode));
    newNode->treeNode = treeNode;
    newNode->next = NULL;

    if (q->rear == NULL) {
        q->front = newNode;
        q->rear = newNode;
    } else {
        q->rear->next = newNode;
        q->rear = newNode;
    }
}

// 出队列
TreeNode* dequeue(Queue* q) {
    if (q->front == NULL) {
        return NULL; // 队列为空
    }

    TreeNode* treeNode = q->front->treeNode;
    QueueNode* temp = q->front;

    q->front = q->front->next;
    free(temp);

    if (q->front == NULL) {
        q->rear = NULL; // 队列为空
    }

    return treeNode;
}

// 层次遍历的算法
void LevelOrder(TreeNode* root) {
    if (root == NULL) {
        return;
    }

    Queue queue;
    initQueue(&queue);

    enqueue(&queue, root);

    while (queue.front != NULL) {
        TreeNode* p = dequeue(&queue);

        while (p != NULL) {
            // 访问当前结点
            printf("%c ", p->data);

            // 将大儿子结点入队列
            if (getFirstChild(p) != NULL) {
                enqueue(&queue, getFirstChild(p));
            }

            // 移动到下一个兄弟结点
            p = getNextBrother(p);
        }
    }
}

// 算法 FindFather
void FindFather(TreeNode* t, TreeNode* p, TreeNode** result) {
    *result = NULL;

    if (t == NULL || p == NULL || p == t) {
        return;
    }

    TreeNode* q = t->firstChild;

    while (q != NULL) {
        if (q == p) {
            *result = t;
            return;
        }

        FindFather(q, p, result);

        if (*result != NULL) {
            return;
        }

        q = q->nextBrother;
    }
}

// 算法 DelSubtree
void DelSubtree(TreeNode* t, TreeNode* p) {
    if (t == NULL || p == NULL) {
        return;
    }

    TreeNode* result = NULL;
    FindFather(t, p, &result);

    if (result == NULL) {
        return; // 未找到父亲节点
    }

    if (result->firstChild == p) {
        result->firstChild = p->nextBrother;
        freeTree(p);
        return;
    }

    TreeNode* q = result->firstChild;

    while (q != NULL && q->nextBrother != p) {
        q = q->nextBrother;
    }

    if (q != NULL) {
        q->nextBrother = p->nextBrother;
        freeTree(p);
    }
}


int main() {
    // 构建左儿子右兄弟链接结构的树
    TreeNode* A = createNode('A');
    TreeNode* B = createNode('B');
    TreeNode* C = createNode('C');
    TreeNode* D = createNode('D');
    TreeNode* E = createNode('E');
    TreeNode* F = createNode('F');

    A->firstChild = B;
    B->nextBrother = C;
    C->nextBrother = D;
    C->firstChild = E;
    E->nextBrother = F;

    // 要删除的子树的根节点
    TreeNode* subtreeRoot = F;

    // 使用算法 DelSubtree 删除子树
    DelSubtree(A, subtreeRoot);

    // 输出删除子树后的树结构
    printf("Tree after deleting subtree rooted at %c:\n", subtreeRoot->data);

    // 层次遍历算法
    printf("Level Order: \n");
    LevelOrder(A);
    printf("\n");

    // 释放树节点
    freeTree(A);

    return 0;
}

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

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

基于C#实现三元组

基于C#实现三元组

我们知道矩阵是一个非常强大的数据结构&#xff0c;在动态规划以及各种图论算法上都有广泛的应用&#xff0c;当然矩阵有着不足的地方就是空间和时间复杂度都维持在 N2 上&#xff0c;比如 1w 个数字建立一个矩阵&#xff0c;在内存中会占用 1w*1w1 亿的类型空间&#xff0c;这…
阅读更多...
【人工智能】Chatgpt的训练原理

【人工智能】Chatgpt的训练原理

前言 前不久&#xff0c;在学习C语言的我写了一段三子棋的代码&#xff0c;但是与我对抗的电脑是没有任何思考的&#xff0c;你看了这段代码就理解为什么了&#xff1a; void computerMove(char Board[ROW][COL], int row, int col) {while (1){unsigned int i rand() % ROW, …
阅读更多...
BC76 [NOIP2008]ISBN号码

BC76 [NOIP2008]ISBN号码

#include<stdio.h> int main() {char arr[13]; //存放13位的ISBNint i, j;scanf("%s",arr);int s 0;for(i0, j1; i<11; i){if(arr[i] ! -){s (arr[i]-0)*j; //将字符换成int累加&#xff1a;0162……29158j; //执行if的时候加&#xff0c;不执行不加…
阅读更多...
Linxu 进程替换

Linxu 进程替换

进程替换的背景&#xff1a; 进程的替换我们需要调用execl这个接口,exxecl在3号手册&#xff0c;属于系统接口。 调用系统命令 execl 为了方便理解execl的作用&#xff0c;我们写一个程序&#xff1a; 单进程替换 我们发现运行结果是通过c库里的exec接口把系统命令 "l…
阅读更多...
【深度学习】DAMO-YOLO，阿里，701类通用检测模型，目标检测

【深度学习】DAMO-YOLO，阿里，701类通用检测模型，目标检测

https://github.com/tinyvision/DAMO-YOLO/blob/master/README_cn.md DAMO-YOLO是由阿里巴巴达摩院智能计算实验室TinyML团队开发的一个兼顾速度与精度的目标检测框架,其效果超越了目前的一众YOLO系列方法&#xff0c;在实现SOTA的同时&#xff0c;保持了很高的推理速度。DAMO…
阅读更多...
Error PostCSS plugin autoprefixer requires PostCSS 8

Error PostCSS plugin autoprefixer requires PostCSS 8

文章目录 一、情况一二、情况二三、总结 在启动 vue项目时&#xff0c;突然控制台报错&#xff1a; Error: PostCSS plugin autoprefixer requires PostCSS 8。然后依次出现下面几种情况&#xff0c;依次解决完&#xff0c;项目就可以正常启动了 一、情况一 error in ./src/…
阅读更多...
【涂鸦T2-U】1、开发环境搭建

【涂鸦T2-U】1、开发环境搭建

前言 本章介绍T2-U的开发环境搭建流程&#xff0c;以及一些遇到的问题。 一、资料 试用网址&#xff1a; 【新品体验】涂鸦 T2-U 开发板免费试用 涂鸦官网文档&#xff1a; 涂鸦 T2-U 开发板 T2-U 模组规格书 T2-U 开发板 淘宝(资料较全)&#xff1a; 涂鸦智能 TuyaOS开发…
阅读更多...
软件测试职业规划导图

软件测试职业规划导图

公司开发的产品专业性较强&#xff0c;软件测试人员需要有很强的专业知识&#xff0c;现在软件测试人员发展出现了一种测试管理者不愿意看到的景象&#xff1a; 1、开发技术较强的软件测试人员转向了软件开发(非测试工具开发)&#xff1b; 2、业务能力较强的测试人员转向了软件…
阅读更多...
基于单片机的肺活量检测系统（论文+源码）

基于单片机的肺活量检测系统（论文+源码）

1.系统设计 在基于单片机的肺活量检测系统中&#xff0c;在硬件上整个系统通过利用主控制器STC89C52单片机来实现对整个系统进行控制的功能&#xff0c;通过采用LCD1602实现实时液晶显示数据的功能&#xff0c;通过肺活量传感器XGZP6847ADC0832实现监测肺活量的工作&#xff0…
阅读更多...
ESP32网络开发实例-远程Web串口监视器

ESP32网络开发实例-远程Web串口监视器

远程Web串口监视器 文章目录 远程Web串口监视器1、应用介绍2、软件准备3、硬件准备4、代码实现在本文中，我们将构建一个 ESP32 网络服务器，用作远程串行监视器。 基于 Web 的串行监视器的工作方式与通常用于调试目的的 Arduino IDE 串行监视器的工作方式相同。 1、应用介绍 …
阅读更多...
系列十六、Spring IOC容器的扩展点

系列十六、Spring IOC容器的扩展点

一、概述 Spring IOC容器的扩展点是指在IOC加载的过程中&#xff0c;如何对即将要创建的bean进行扩展。 二、扩展点 2.1、BeanDefinitionRegistryPostProcessor 2.1.1、概述 BeanDefinitionRegistryPostProcessor是bean定义的后置处理器&#xff0c;在BeanDefinition加载后&a…
阅读更多...
cesium轨迹线（闪烁轨迹线）

cesium轨迹线（闪烁轨迹线）

cesium轨迹线（闪烁轨迹线） 下面有源码 实现思路 使用ellipse方法加载圆型，修改polyline中‘material’方法重写glsl来实现当前效果（cesium版本1.109） 示例代码 index.html <!DOCTYPE html> <html lang="en"><head
阅读更多...
MyBatis框架_01

MyBatis框架_01

Web后端开发_03 MyBatis框架 什么是MyBatis? MyBatis是一款优秀的持久层框架&#xff0c;用于简化JDBC的开发。MyBatis本是 Apache的一个开源项目iBatis&#xff0c;2010年这个项目由apache迁移到了google code&#xff0c;并且改名为MyBatis 。2013年11月迁移到Github。官网…
阅读更多...
基于Pytest+Requests+Allure实现接口自动化测试

基于Pytest+Requests+Allure实现接口自动化测试

一、整体结构 框架组成&#xff1a;pytestrequestsallure 设计模式&#xff1a; 关键字驱动 项目结构&#xff1a; 工具层&#xff1a;api_keyword/ 参数层&#xff1a;params/ 用例层&#xff1a;case/ 数据驱动&#xff1a;data_driver/ 数据层&#xff1a;data/ 逻…
阅读更多...
crontab计划任务

crontab计划任务

银河麒麟v10服务器版和桌面版执行周期计划任务分为两类&#xff1a;系统任务调度和用户任务调度。系统任务是由 cron (crond) 这个系统服务来控制的&#xff0c;这个系统服务是默认启动的&#xff0c;通过vim /etc/crontab执行。用户自己设置的计划任务则使用crontab 命令 配置…
阅读更多...
SpringMVC系列-7 @CrossOrigin注解与跨域问题

SpringMVC系列-7 @CrossOrigin注解与跨域问题

背景 前段时间帮同事分析了一个跨域问题&#xff0c;正好系统分析和整理一下。 1.跨域 理解同源策略是理解跨域的前提。同源策略定义如下&#xff1a; 在同一来源的页面和脚本之间进行数据交互时&#xff0c;浏览器会默认允许操作&#xff0c;而不会造成跨站脚本攻击&#x…
阅读更多...
柑橘病害数据集（四类图像分类，没有打yolo标签）

柑橘病害数据集（四类图像分类，没有打yolo标签）

1.文件夹分为训练集和测试集 在这个数据集中&#xff0c;有一类是新鲜柑橘&#xff0c;还有另外三种疾病&#xff0c;溃疡病、黑斑病和绿化病。 2.train文件夹 2.1.blackspot&#xff08;黑斑病&#xff09; 文件夹 206张照片 2.2.canker&#xff08;溃疡病&#xff09; 文…
阅读更多...
发布鸿蒙的第一个java应用

发布鸿蒙的第一个java应用

1.下载和安装华为自己的app开发软件DevEco Studio HUAWEI DevEco Studio和SDK下载和升级 | HarmonyOS开发者 2.打开IDE新建工程&#xff08;当前用的IDEA 3.1.1 Release&#xff09; 选择第一个&#xff0c;其他的默认只能用(API9)版本&#xff0c;搞了半天才发现8&#xff…
阅读更多...
PPT 遇到问题总结（修改页码统计）

PPT 遇到问题总结（修改页码统计）

PPT常见问题 1. 修改页码自动计数 1. 修改页码自动计数 点击 视图——>幻灯片母版——>下翻找到计数页直接修改——>关闭母版视图
阅读更多...
HarmonyOS4.0系列——02、汉化插件、声明式开发范式ArkTS和类web开发范式

HarmonyOS4.0系列——02、汉化插件、声明式开发范式ArkTS和类web开发范式

编辑器调整 我们在每次退出编辑器后再次打开会直接进入项目文件中&#xff0c;这样在新建项目用起来很是不方便&#xff0c;所以这里跟着设置一下就好 这样下次进入就不会直接跳转到当时的文件项目中&#xff01;&#xff01; 关于汉化 settings → plugins → installe…
阅读更多...
最新文章

Copyright @ 2022~2023