树结构及其算法-二叉树节点的删除

这篇具有很好参考价值的文章主要介绍了树结构及其算法-二叉树节点的删除。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

目录

树结构及其算法-二叉树节点的删除

C++代码


树结构及其算法-二叉树节点的删除

二叉树节点的删除操作稍为复杂,可分为以下3种情况。

  1. 删除的节点为树叶,只要将其相连的父节点指向NULL即可。
  2. 删除的节点只有一棵子树。
  3. 删除的节点有两棵子树。要删除节点,方式有两种,虽然结果不同,但是都符合二叉树的特性。
  • 找出中序立即先行者(Inorder Immediate Predecessor),就是将要删除节点的左子树中的最大者向上提。简单来说,就是从该节点的左子树往右寻找,直到右指针为NULL,这个节点就是中序立即先行者。
  • 找出中序立即后继者(Inorder Immediate Successor),就是把要删除节点的右子树中的最小者向上提。简单来说,就是从该节点的右子树往左寻找,直到左指针为NULL,这个节点就是中序立即后继者。

C++代码

#include<iostream>
using namespace std;

struct TreeNode {
	int data;
	TreeNode* leftNode;
	TreeNode* rightNode;
	TreeNode(int tempData, TreeNode* tempLeftNode = nullptr, TreeNode* tempRightNode = nullptr) {
		this->data = tempData;
		this->leftNode = tempLeftNode;
		this->rightNode = tempRightNode;
	}
};

class Tree {
private:
	TreeNode* treeNode;
public:
	Tree() {
		treeNode = nullptr;
	}
	TreeNode* GetTreeNode() {
		return this->treeNode;
	}
	void AddNodeToTree(int* tempData, int tempSize) {
		for (int i = 0; i < tempSize; i++) {
			TreeNode* currentNode;
			TreeNode* newNode;
			int flag = 0;
			newNode = new TreeNode(tempData[i]);
			if (treeNode == nullptr)
				treeNode = newNode;
			else {
				currentNode = treeNode;
				while (!flag) {
					if (tempData[i] < currentNode->data) {
						if (currentNode->leftNode == nullptr) {
							currentNode->leftNode = newNode;
							flag = 1;
						}
						else
							currentNode = currentNode->leftNode;
					}
					else {
						if (currentNode->rightNode == nullptr) {
							currentNode->rightNode = newNode;
							flag = 1;
						}
						else
							currentNode = currentNode->rightNode;
					}
				}
			}
		}
	}
	void DeleteNodeToTree(TreeNode* tempTree, int tempData) {
		if (tempTree == nullptr)
			return;
		TreeNode* findNode = tempTree;
		TreeNode* pre = nullptr;
		while (findNode != nullptr) {
			if (findNode->data == tempData)
				break;
			else if (tempData < findNode->data) {
				pre = findNode;
				findNode = findNode->leftNode;
			}
			else {
				pre = findNode;
				findNode = findNode->rightNode;
			}
		}
		if (findNode == nullptr)
			return;

		if (findNode->leftNode == nullptr) {
			if (findNode == tempTree) {
				TreeNode* temp = findNode;
				findNode = findNode->rightNode;
				free(temp);
			}
			TreeNode* temp = findNode;
			(pre->data < findNode->data ? pre->rightNode : pre->leftNode) = findNode->rightNode;
			free(temp);
			temp = nullptr;
		}
		else if (findNode->rightNode == nullptr) {
			if (findNode == tempTree) {
				TreeNode* temp = findNode;
				findNode = findNode->leftNode;
				free(temp);
			}
			TreeNode* temp = findNode;
			(pre->data < findNode->data ? pre->rightNode : pre->leftNode) = findNode->leftNode;
			free(temp);
			temp = nullptr;
		}
		else {
			TreeNode* post = findNode;
			TreeNode* max = findNode->leftNode;
			while (max->rightNode != nullptr) {
				post = max;
				max = max->rightNode;
			}
			findNode->data = max->data;
			if (post == findNode)
				post->leftNode = max->leftNode;
			else
				post->rightNode = max->rightNode;
			free(max);
		}
	}
	void Inorder(TreeNode* tempTree) {
		if (tempTree != nullptr) {
			Inorder(tempTree->leftNode);
			cout << tempTree->data << " ";
			Inorder(tempTree->rightNode);
		}
	}
	TreeNode* Find(TreeNode* tree, int value) {
		while (true) {
			if (tree == nullptr)
				return nullptr;
			if (tree->data == value)
				return tree;
			else if (tree->data > value)
				tree = tree->leftNode;
			else
				tree = tree->rightNode;
		}
	}
};

int main() {
	int data[]{ 7,4,1,5,16,8,11,12,15,9,2 };
	cout << "原始数据:" << endl;
	for (int i = 0; i < 11; i++)
		cout << data[i] << " ";
	cout << endl;

	Tree* tree = new Tree;
	tree->AddNodeToTree(data, 11);

	cout << "中序遍历:" << endl;
	tree->Inorder(tree->GetTreeNode());
	cout << endl;

	cout << "请输入要删除的值:";
	int value;
	cin >> value;
	if ((tree->Find(tree->GetTreeNode(), value)) == nullptr)
		cout << "二叉树中没有此节点了" << endl;
	else {
		tree->DeleteNodeToTree(tree->GetTreeNode(), value);
		cout << "中序遍历:" << endl;
		tree->Inorder(tree->GetTreeNode());
		cout << endl;
	}

	return 0;
}

输出结果

树结构及其算法-二叉树节点的删除,算法(Algorithm),c++,开发语言,算法,树结构,二叉树,删除

树结构及其算法-二叉树节点的删除,算法(Algorithm),c++,开发语言,算法,树结构,二叉树,删除文章来源地址https://www.toymoban.com/news/detail-744782.html

到了这里,关于树结构及其算法-二叉树节点的删除的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 力扣日记1.11-【二叉树篇】450. 删除二叉搜索树中的节点

    日期:2024.1.11 参考:代码随想录、力扣 题目描述 难度:中等 给定一个二叉搜索树的根节点 root 和一个值 key,删除二叉搜索树中的 key 对应的节点,并保证二叉搜索树的性质不变。返回二叉搜索树(有可能被更新)的根节点的引用。 一般来说,删除节点可分为两个步骤: 首

    2024年01月23日
    浏览(43)
  • 树和二叉树(概念及其结构)

    1.1树的概念 树是一种非线性的数据结构,它是由n(n=0)个有限结点组成一个具有层次关系的集合。把它 叫做树是因为它看起来像一颗倒挂的树,也就是说它是根朝上,而叶朝下的。 *有一个特殊的节点叫做根节点,根节点没有前驱节点 *除根节点外,其余节点被分成不相交的

    2023年04月22日
    浏览(32)
  • LeetCode算法二叉树—222. 完全二叉树的节点个数

    目录 222. 完全二叉树的节点个数 - 力扣(LeetCode) 代码: 运行结果:  给你一棵  完全二叉树  的根节点  root  ,求出该树的节点个数。 完全二叉树 的定义如下:在完全二叉树中,除了最底层节点可能没填满外,其余每层节点数都达到最大值,并且最下面一层的节点都集

    2024年02月07日
    浏览(46)
  • 数据结构上机实验——二叉树的实现、二叉树遍历、求二叉树的深度/节点数目/叶节点数目、计算二叉树度为1或2的节点数、判断二叉树是否相似

       建立一棵二叉树,试编程实现二叉树的如下基本操作。    1.创建一棵一棵二叉算法。    2.对这棵二叉树进行遍历:先序或中序或后序,分别输出结点的遍历序列。    3.求二叉树的深度/节点数目/叶节点数目。(选做一个)    4.计算二叉树中度为1 的结点数;

    2024年02月06日
    浏览(62)
  • 模拟实现链式二叉树及其结构学习——【数据结构】

    W...Y的主页 😊 代码仓库分享 💕 之前我们实现了用顺序表完成二叉树(也就是堆),顺序二叉树的实际作用就是解决堆排序以及Topk问题。 今天我们要学习的内容是链式二叉树,并且实现链式二叉树,这篇博客与递归息息相关! 目录 链式存储 二叉树链式结构的实现 链式二叉

    2024年02月07日
    浏览(41)
  • 【数据结构】二叉树链式结构的实现及其常见操作

    目录 1.手搓二叉树 2.二叉树的遍历 2.1前序、中序以及后序遍历 2.2二叉树的层序遍历 3.二叉树的常见操作 3.1求二叉树节点数量 3.2求二叉树叶子节点数量 3.3求二叉树第k层节点个数 3.3求二叉树的深度 3.4二叉树查找值为x的节点 4.二叉树的销毁 在学习二叉树的基本操作前,需先要

    2024年02月12日
    浏览(46)
  • 数据结构进阶篇 之 【二叉树】详细概念讲解(带你认识何为二叉树及其性质)

    有朋自远方来,必先苦其心志,劳其筋骨,饿其体肤,空乏其身,鞭数十,驱之别院 1.1 二叉树中组分构成名词概念 1.2 二叉树的结构概念 1.3 特殊的二叉树 2.1 顺序存储 2.2 链式存储 前言: 在你的想象中如果有一个“二叉树”会是什么样子呢? 顾名思义,现实中的二叉树我们

    2024年04月13日
    浏览(46)
  • 数据结构计算二叉树的深度和节点个数

    2022.11.19 本关任务:给定一棵二叉树,计算该二叉树的深度、总节点个数和叶子节点个数。 为了完成本关任务,你需要掌握:1.二叉树深度概念,2.二叉树节点,3.二叉树叶子节点概念。 二叉树深度概念 二叉树的深度指的是二叉树中最大的结点层数。例如:图1所示的二叉树最

    2024年02月04日
    浏览(45)
  • 算法(链表链表的创建、插入节点、删除节点、遍历节点及其长度)

                                  id:671593      转自:Hitsu 本人在idea中能够正常运行出来(结果3 3 2 1 4)。 链表的创建、插入节点、删除节点、遍历节点及其长度。 Java构建链表两种方式 第一种 (这一种写出来看起来更简洁) Java构建链表两种方式 第一种 (这一种写出来

    2024年02月13日
    浏览(36)
  • 面试算法43:在完全二叉树中添加节点

    在完全二叉树中,除最后一层之外其他层的节点都是满的(第n层有2 n-1 个节点)。最后一层的节点可能不满,该层所有的节点尽可能向左边靠拢。例如,图7.3中的4棵二叉树均为完全二叉树。实现数据结构CBTInserter有如下3种方法。 构造函数CBTInserter(TreeNode root),用一棵完全

    2024年02月06日
    浏览(39)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包