数据结构
网络
关系数据库管理系统(RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法学C++中二叉树的删除操作？
删除操作是通过用最底部最右边的节点替换要删除的节点来执行的。
首先，让我们定义一个结构体来表示树节点，其中包含数据及其左右子节点。如果这是第一个创建的节点，则它是根节点，否则是子节点。
struct Node {
int data;
struct Node *leftChild, *rightChild;
};接下来，我们创建 `newNode(int data)` 函数，该函数接收一个整数值并将其赋值给节点的 data 成员。该函数返回指向已创建的 `struct Node` 的指针。此外，新创建节点的左右子节点都设置为 null。
struct Node* newNode(int data){
struct Node* newNode = new Node;
newNode->data = data;
newNode->leftChild = newNode->rightChild = NULL;
return (newNode);
}`deletion(struct Node* root, int data)` 函数用于删除具有给定 data 值的节点。它接收根节点和要搜索和删除的 data 值。如果没有子节点并且 data 值等于根节点的 data 值，则返回 null，否则返回根节点。
Node* deletion(struct Node* root, int data){
if (root == NULL)
return NULL;
if (root->leftChild == NULL && root->rightChild == NULL) {
if (root->data == data)
return NULL;
else
return root;
}现在，我们创建一个类型为 `struct Node*` 的队列，并将其命名为 `q`，并将根节点推入 `q`。我们还声明 `temp` 和 `data_node`，它们是指向 `Node` 的指针，并将 `data_node` 设置为 NULL。
struct Node* temp; struct Node* data_node = NULL;
接下来，我们执行层序遍历以查找最深的节点。当队列 `q` 不为空时，执行 while 循环。队列是一种先进先出 (FIFO) 数据结构，因此，由于我们正在进行层序遍历，队列中的最后一个元素将是最右边的最深节点。`temp` 始终指向队列的前面，并且随着我们的进行，元素会从前面弹出。
while (!q.empty()) {
temp = q.front();
q.pop();
if (temp->data == data)
data_node = temp;
if (temp->leftChild)
q.push(temp->leftChild);
if (temp->rightChild)
q.push(temp->rightChild);
}接下来，如果 `data_node` 不为 NULL，则我们将要删除的节点数据存储在 `x` 中，并删除 `temp`（即最深的节点）。然后，`data_node` 的值被替换为最深节点的值，最深节点被删除。删除和替换后，新节点将从函数返回。
if (data_node != NULL) {
int x = temp->data;
deleteDeepest(root, temp);
data_node->data = x;
}`deleteDeepest(struct Node* root, struct Node* deepestNode)` 函数检查传递的节点是否确实是深度节点，或者其右子节点或左子节点是否是深度节点，在这种情况下，它会在删除父节点（即 `deepestNode`）之前将其子节点值设置为 null。
void deleteDeepest(struct Node* root,
struct Node* deepestNode){
queue<struct Node*> q;
q.push(root);
struct Node* temp;
while (!q.empty()) {
temp = q.front();
q.pop();
if (temp == deepestNode) {
temp = NULL;
delete (deepestNode);
return;
}
if (temp->rightChild) {
if (temp->rightChild == deepestNode) {
temp->rightChild = NULL;
delete (deepestNode);
return;
}
else
q.push(temp->rightChild);
}
if (temp->leftChild) {
if (temp->leftChild == deepestNode) {
temp->leftChild = NULL;
delete (deepestNode);
return;
}
else
q.push(temp->leftChild);
}
}
}示例
让我们看看下面的实现，以了解二叉树中的删除操作：
#include <iostream>
#include <queue>
using namespace std;
struct Node {
int data;
struct Node *leftChild, *rightChild;
};
struct Node* NewNode(int data){
struct Node* temp = new Node;
temp->data = data;
temp->leftChild = temp->rightChild = NULL;
return temp;
};
void inorder(struct Node* temp){
if (!temp)
return;
inorder(temp->leftChild);
cout << temp->data << " ";
inorder(temp->rightChild);
}
void deleteDeepest(struct Node* root,
struct Node* deepestNode){
queue<struct Node*> q;
q.push(root);
struct Node* temp;
while (!q.empty()) {
temp = q.front();
q.pop();
if (temp == deepestNode) {
temp = NULL;
delete (deepestNode);
return;
}
if (temp->rightChild) {
if (temp->rightChild == deepestNode) {
temp->rightChild = NULL;
delete (deepestNode);
return;
}
else
q.push(temp->rightChild);
}
if (temp->leftChild) {
if (temp->leftChild == deepestNode) {
temp->leftChild = NULL;
delete (deepestNode);
return;
}
else
q.push(temp->leftChild);
}
}
}
Node* deletion(struct Node* root, int data){
if (root == NULL)
return NULL;
if (root->leftChild == NULL && root->rightChild == NULL) {
if (root->data == data)
return NULL;
else
return root;
}
queue<struct Node*> q;
q.push(root);
struct Node* temp;
struct Node* data_node = NULL;
while (!q.empty()) {
temp = q.front();
q.pop();
if (temp->data == data)
data_node = temp;
if (temp->leftChild)
q.push(temp->leftChild);
if (temp->rightChild)
q.push(temp->rightChild);
}
if (data_node != NULL) {
int x = temp->data;
deleteDeepest(root,temp);
data_node->data = x;
}
return root;
}
// Driver code
int main(){
struct Node* root = NewNode(12);
root->leftChild = NewNode(13);
root->leftChild->leftChild = NewNode(9);
root->leftChild->rightChild = NewNode(14);
root->rightChild = NewNode(11);
root->rightChild->leftChild = NewNode(17);
root->rightChild->rightChild = NewNode(10);
cout << "Inorder traversal before deletion : ";
inorder(root);
int data = 13;
root = deletion(root, data);
cout <<endl<< "Inorder traversal after deletion : ";
inorder(root);
return 0;
}输出
以上代码将产生以下输出：
Inorder traversal before deletion : 9 13 14 12 17 11 10 Inorder traversal after deletion : 9 10 14 12 17 11
226 次浏览
