在 C++ 中删除二叉树？
删除是通过用底部和最右边的节点替换删除模式来执行的。
让我们首先定义表示包含数据及其左右节点子节点的树节点的结构。如果这是要创建的第一个节点，则它是根节点，否则是子节点。
struct Node { int data;
struct Node *leftChild, *rightChild;
};
接下来我们创建我们的newNode(int data)函数，它接受一个 int 值并将其分配给节点的数据成员。该函数返回指向创建的结构节点的指针。此外，新创建的节点的左右子节点设置为空。
struct Node* newNode(int data){ struct Node* newNode = new Node;
newNode->data = data;
newNode->leftChild = newNode->rightChild = NULL;
return (newNode);
}
delete(struct Node* root, int data) 函数用于删除具有给定数据值的节点。它需要根节点和要搜索和删除的数据值。如果没有任何子节点并且数据值等于根的数据值，则返回空值，否则返回根节点。
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。我们还声明了指向 Node 的指针 temp 和 data_node，并将 data_node 设置为 NULL。
struct Node* temp;struct Node* data_node = NULL;
接下来，我们执行层序遍历以找到最深的节点。while 循环一直执行到队列 q 不为空。队列是一个 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) 函数检查传递的节点是否实际上是最深的节点，或者它的右子节点或左子节点是最深的节点，在这种情况下，它在删除父节点之前将子节点值设置为 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;
}
// 驱动程序代码
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(root);
int data = 13;
root = deletion(root, data);
cout <<endl<< "删除后的中序遍历： ";
inorder(root);
return 0;
}
上面的代码将产生以下输出 -
删除前的中序遍历： 9 13 14 12 17 11 10删除后的中序遍历： 9 10 14 12 17 11
以上是 在 C++ 中删除二叉树？ 的全部内容， 来源链接： utcz.com/z/347612.html
