数据结构排序二叉树(下)

news/2025/3/14 17:54:29/

哎,调了几天深度学习模型,今天来更新排序二叉树

文章目录

前言

一、排序二叉树的结构定义

二、在排序二叉树添加数据

三、定义创建排序二叉树函数

四、查找一棵二叉排序树中的结点x的所在层数

五、删除二叉排序树中T关键字x的节点

六、查找二叉排序树中的所有小于key的关键字

七、已知二叉排序中每个节点值为整形,采用二叉链表存储,编写算法删除二叉排序树中所有关键字小于x的

八.总结与验证

前言

排序二叉树就这几个习题了,但实际上还有更难得几道习题,因为实现起来真的难,而且在使用中也难用到所以就给大家几道简单的例子,帮助大家来熟悉.

一、排序二叉树的结构定义

typedef int ElemType;
//二叉排序树左>根>右,树中没有重复值
//二叉排序树的数据结构
typedef struct BSTNode {ElemType data;//数据节点类型为intstruct BSTNode* lchild;struct BSTNode* rchild;
}BSTNode,*BSTree;

其实就是二叉树的数据结构只是对树中节点数据有约束.

二、在排序二叉树添加数据

//插入节点函数
void insertNode(BSTree& T, ElemType e) {if (T == NULL) {//找到合适的位置插入节点BSTNode* pNode = (BSTNode*)malloc(sizeof(BSTNode));assert(pNode);pNode->data = e;pNode->lchild = NULL;pNode->rchild = NULL;T = pNode;//别忘了链接上}else if (T->data > e) {//插入左子树insertNode(T->lchild, e);}else if (T->data < e) {//插入右子树insertNode(T->rchild, e);}
}

由于二叉树左>根>右所以在构建二叉树使需要满足要求.

算法思想:运用递归思想,将待插入数据与当前节点比较如果小于当前节点数据表明插入数据应插在当前节点的左子树,反之当如果插入数据比当前的节点数据大,则表明插入数据应插到当前数据的右子树,直到遇到空节点表示找到插入位置,申请节点插入即可.

三、定义创建排序二叉树函数

//定义创建二叉排序树函数
BSTNode* creatBSTree() {BSTNode* T = NULL;ElemType enternum = 999999;//999999表示退出输入printf("请输入序列(以999999作为结束标志):");while (scanf("%d", &enternum) && enternum != 999999) {insertNode(T, enternum);}return T;
}

就依次插入节点就可以了.

四、查找一棵二叉排序树中的结点x的所在层数

//例1:查找一棵二叉排序树中的结点x的所在层数
int nodelevel(BSTree T, int level,ElemType x) {if (T == NULL) {//没找到返回0return 0;}else if (T->data > x) {//左子树寻找return nodelevel(T->lchild, level+1, x);}else if (T->data < x) {//右子树寻找return nodelevel(T->rchild, level+1, x);}else {return level;//返回层次}
}

算法思想:采用递归的形式,但传参时传入一个层数,找到返回即可,注意这里层数是值传递,不是址传递.

五、删除二叉排序树中T关键字x的节点

//例2:删除二叉排序树中T关键字x的节点
//算法思想:首先找到节点x此时就要分情况讨论(1)节点既没有左孩子又没有右孩子,直接删去节点并将指针制空;
//(2)节点只有左孩子(或只有右孩子),指针指向左孩子(右孩子)并删除节点;
//(3)节点既有左孩子又有右孩子,此时有两种处理方案1.找到左子树的最大节点将右孩子链接到最大节点的右指针
//2.找到右子树的最小节点,将左孩子链接到最小节点的左指针
void deleteOperation(BSTree& T) {if (T == NULL) return;if (T->lchild == NULL && T->rchild == NULL) {free(T);T = NULL;}else if (T->lchild != NULL && T->rchild == NULL) {BSTNode* tmp = T;T = T->lchild;free(tmp);tmp = NULL;}else if (T->lchild == NULL && T->rchild != NULL) {BSTNode* tmp = T;T = T->rchild;free(tmp);tmp = NULL;}else {//既有左孩子又有右孩子BSTNode* pMaxnode = T->lchild;while (pMaxnode->rchild != NULL) {pMaxnode = pMaxnode->rchild;}pMaxnode->rchild = T->rchild;BSTNode* tmp = T;T = T->lchild;free(tmp);tmp = NULL;}
}
//查找并删除节点
void deletenode(BSTree &T,ElemType x) {if (T != NULL) {if (T->data == x) {deleteOperation(T);}else if (T->data < x) {deletenode(T->rchild, x);}else {deletenode(T->lchild, x);}}}

这个算法还有一个思想就是找到左子树最大的节点复制到删除节点上,递归在左子树删除左子树最大节点.

字有点丑见谅.

六、查找二叉排序树中的所有小于key的关键字

//例3:查找二叉排序树中的所有小于key的关键字
void getSmallerkey(BSTree T, ElemType key) {if (T != NULL) {getSmallerkey(T->lchild, key);if (T->data < key) {printf("%d ", T->data);getSmallerkey(T->rchild, key);}}
}

七、已知二叉排序中每个节点值为整形,采用二叉链表存储,编写算法删除二叉排序树中所有关键字小于x的

//例4:已知二叉排序中每个节点值为整形,采用二叉链表存储,编写算法删除二叉排序树中所有关键字小于x的节点
//定义递归删除树函数
void deleteFunc(BSTree& T) {//递归删除树if (T != NULL) {deleteFunc(T->lchild);deleteFunc(T->rchild);free(T);T = NULL;}
}
//定义删除小于x节点的函数(采用先序遍历的思想)
void deleteSmallernode(BSTree &T,ElemType x) {if (T != NULL) {if (T->data == x) {//根节点等于x说明左子树都小于x递归删除deleteFunc(T->lchild);}else if (T->data < x) {//根节点小于x左子树均小于x,删除根节点在递归删除右子树小于x的节点deleteFunc(T->lchild);BSTNode* tmp = T;T = T->rchild;free(tmp);tmp = NULL;deleteSmallernode(T, x);}else {//根节点大于x递归删除左子树小于x的节点deleteSmallernode(T->lchild, x);}}
}

八.总结与验证

#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<malloc.h>
#include<assert.h>
typedef int ElemType;
//二叉排序树左>根>右,树中没有重复值
//二叉排序树的数据结构
typedef struct BSTNode {ElemType data;//数据节点类型为intstruct BSTNode* lchild;struct BSTNode* rchild;
}BSTNode,*BSTree;
//插入节点函数
void insertNode(BSTree& T, ElemType e) {if (T == NULL) {//找到合适的位置插入节点BSTNode* pNode = (BSTNode*)malloc(sizeof(BSTNode));assert(pNode);pNode->data = e;pNode->lchild = NULL;pNode->rchild = NULL;T = pNode;//别忘了链接上}else if (T->data > e) {//插入左子树insertNode(T->lchild, e);}else if (T->data < e) {//插入右子树insertNode(T->rchild, e);}
}
//定义创建二叉排序树函数
BSTNode* creatBSTree() {BSTNode* T = NULL;ElemType enternum = 999999;//999999表示退出输入printf("请输入序列(以999999作为结束标志):");while (scanf("%d", &enternum) && enternum != 999999) {insertNode(T, enternum);}return T;
}
//中序遍历二叉排序树
void inorderTraverse(BSTree T) {if (T != NULL) {inorderTraverse(T->lchild);printf("%d ", T->data);inorderTraverse(T->rchild);}
}
//先序遍历二叉排序树
void preorderTraverse(BSTree T) {if (T != NULL) {printf("%d ", T->data);preorderTraverse(T->lchild);preorderTraverse(T->rchild);}
}
//遍历二叉排序树(先,中)
void Traverse(BSTree T) {//这函数主要是用来验证printf("中序遍历结果:");inorderTraverse(T);printf("\n");printf("先序遍历结果:");preorderTraverse(T);printf("\n");
}
//例1:查找一棵二叉排序树中的结点x的所在层数
int nodelevel(BSTree T, int level,ElemType x) {if (T == NULL) {//没找到返回0return 0;}else if (T->data > x) {//左子树寻找return nodelevel(T->lchild, level+1, x);}else if (T->data < x) {//右子树寻找return nodelevel(T->rchild, level+1, x);}else {return level;//返回层次}
}
//例2:删除二叉排序树中T关键字x的节点
//算法思想:首先找到节点x此时就要分情况讨论(1)节点既没有左孩子又没有右孩子,直接删去节点并将指针制空;
//(2)节点只有左孩子(或只有右孩子),指针指向左孩子(右孩子)并删除节点;
//(3)节点既有左孩子又有右孩子,此时有两种处理方案1.找到左子树的最大节点将右孩子链接到最大节点的右指针
//2.找到右子树的最小节点,将左孩子链接到最小节点的左指针
void deleteOperation(BSTree& T) {if (T == NULL) return;if (T->lchild == NULL && T->rchild == NULL) {free(T);T = NULL;}else if (T->lchild != NULL && T->rchild == NULL) {BSTNode* tmp = T;T = T->lchild;free(tmp);tmp = NULL;}else if (T->lchild == NULL && T->rchild != NULL) {BSTNode* tmp = T;T = T->rchild;free(tmp);tmp = NULL;}else {//既有左孩子又有右孩子BSTNode* pMaxnode = T->lchild;while (pMaxnode->rchild != NULL) {pMaxnode = pMaxnode->rchild;}pMaxnode->rchild = T->rchild;BSTNode* tmp = T;T = T->lchild;free(tmp);tmp = NULL;}
}
//查找并删除节点
void deletenode(BSTree &T,ElemType x) {if (T != NULL) {if (T->data == x) {deleteOperation(T);}else if (T->data < x) {deletenode(T->rchild, x);}else {deletenode(T->lchild, x);}}}
//例3:查找二叉排序树中的所有小于key的关键字
void getSmallerkey(BSTree T, ElemType key) {if (T != NULL) {getSmallerkey(T->lchild, key);if (T->data < key) {printf("%d ", T->data);getSmallerkey(T->rchild, key);}}
}
//例4:已知二叉排序中每个节点值为整形,采用二叉链表存储,编写算法删除二叉排序树中所有关键字小于x的节点
//定义递归删除树函数
void deleteFunc(BSTree& T) {//递归删除树if (T != NULL) {deleteFunc(T->lchild);deleteFunc(T->rchild);free(T);T = NULL;}
}
//定义删除小于x节点的函数(采用先序遍历的思想)
void deleteSmallernode(BSTree &T,ElemType x) {if (T != NULL) {if (T->data == x) {//根节点等于x说明左子树都小于x递归删除deleteFunc(T->lchild);}else if (T->data < x) {//根节点小于x左子树均小于x,删除根节点在递归删除右子树小于x的节点deleteFunc(T->lchild);BSTNode* tmp = T;T = T->rchild;free(tmp);tmp = NULL;deleteSmallernode(T, x);}else {//根节点大于x递归删除左子树小于x的节点deleteSmallernode(T->lchild, x);}}
}
int main() {//创建一棵二叉排序树//8 5 4 7 9 10 999999BSTree T = creatBSTree();Traverse(T);printf("\n");int a = 10;printf("数据节点为%d的节点所在层次:%d\n", a,nodelevel(T, 1, a));printf("删除数据节点前树的结构\n");Traverse(T);deletenode(T, 5);printf("删除数据节点后树的结构\n");Traverse(T);printf("比8小的数据节点有:");getSmallerkey(T, 8);printf("\n");int b = 8;printf("删除比%d小的所有节点前\n",b);Traverse(T);deleteSmallernode(T, b);printf("删除比%d小的所有节点后\n", b);Traverse(T);return 0;
}

兄弟们马上要到图啦,最有意思的一部分要到啦.加油哦


http://www.ppmy.cn/news/1326450.html

相关文章

Cmake(1)——Cmake的基本介绍和原理、Cmake的安装、如何使用Cmake构建项目

Cmake(1)——Cmake的基本介绍和原理、Cmake的安装、如何使用Cmake构建项目

Cmake的基本介绍和原理、Cmake的安装、如何使用Cmake构建项目 插播&#xff01;插播&#xff01;插播&#xff01;亲爱的朋友们&#xff0c;我们的Cmake课程上线啦&#xff01;感兴趣的小伙伴可以去下面的链接学习哦~ https://edu.csdn.net/course/detail/39261 1、Cmake的基…
阅读更多...
位运算的奇技淫巧

位运算的奇技淫巧

常见位运算总结&#xff1a; 1、基础位运算 左移<<运算 将二进制数向左移位操作&#xff0c;高位溢出则丢弃&#xff0c;低位补0。 右移>>运算 右移位运算中&#xff0c;无符号数和有符号数的运算并不相同。对于无符号数&#xff0c;右移之后高位补0&#xff…
阅读更多...
基于SpringBoot Vue自习室管理系统

基于SpringBoot Vue自习室管理系统

大家好✌&#xff01;我是Dwzun。很高兴你能来阅读我&#xff0c;我会陆续更新Java后端、前端、数据库、项目案例等相关知识点总结&#xff0c;还为大家分享优质的实战项目&#xff0c;本人在Java项目开发领域有多年的经验&#xff0c;陆续会更新更多优质的Java实战项目&#x…
阅读更多...
利用浏览器开发者工具进行网页性能优化

利用浏览器开发者工具进行网页性能优化

目录 学习目标&#xff1a; 学习内容&#xff1a; 学习时间&#xff1a; 学习产出&#xff1a; 网页性能优化的基本概念和指标&#xff1a; 浏览器开发者工具的基本功能和使用方法&#xff1a; 使用网络面板进行网页加载性能分析&#xff1a; 使用性能面板进行网页渲染性能分析…
阅读更多...
Spring Boot框架中Controller层API接口如何支持使用多个@RequestBody注解接受请求体参数

Spring Boot框架中Controller层API接口如何支持使用多个@RequestBody注解接受请求体参数

一、前言 众所周知&#xff0c;在Spring Boot框架中&#xff0c;Controller层API接口编码获取请求体参数时&#xff0c;在参数上会使用RequestBody注解&#xff1b;如果一次请求中&#xff0c;请求体参数携带的内容需要用多个参数接收时&#xff0c;能不能多次使用RequestBody…
阅读更多...
Git学习笔记（第6章）：GitHub操作（远程库操作）

Git学习笔记（第6章）：GitHub操作（远程库操作）

目录 6.1 远程库操作 6.1.1 创建远程库 6.1.2 命名远程库 6.1.3 本地库推送到远程库(push) 6.1.4 远程库拉取到本地库(pull) 6.1.5 远程库克隆到本地库(clone) 6.2 团队内协作 6.3 跨团队协作 6.4 SSH免密登录 6.1 远程库操作 命令 作用 git remote -v 查看所有远程…
阅读更多...
【24.1.19】

【24.1.19】

24.1.19 本周工作内容下周工作计划 本周工作内容 本周的话主要的一个工作还是第三部分页面部分的完成工作&#xff0c;那就先来汇报一下第三部分的工作进度&#xff0c;第三部分的页面工作呢已经完成啦&#xff0c;就在刚刚提交啦全部的代码&#xff0c;那么这一部分的工作呢也…
阅读更多...
Unity 面试篇|（六）Unity渲染与Shader篇 【全面总结 | 持续更新】

Unity 面试篇|（六）Unity渲染与Shader篇 【全面总结 | 持续更新】

目录 1.问一个Terrain&#xff0c;分别贴3张&#xff0c;4张&#xff0c;5张地表贴图&#xff0c;渲染速度有什么区别&#xff1f;为什么&#xff1f;2.什么是LightMap&#xff1f;3.MipMap是什么&#xff0c;作用&#xff1f;4.请问alpha test在何时使用&#xff1f;能达到什么…
阅读更多...
最新文章

Copyright @ 2022~2023