在本教程中，我们将学习如何删除二叉树中的节点。
二叉树中的节点不像二叉搜索树那样遵循任何顺序。那么，在删除二叉树中的节点之后如何安排节点呢？
好吧，我们将用删除节点替换树的最深节点。然后，我们将从节点中删除最深的节点。
让我们看看解决问题的步骤。
用二进制节点struct初始化树。
编写一个函数（预顺序，顺序和后顺序）以打印树的节点。
编写一个删除节点的函数。
初始化队列以遍历树。
迭代直到队列为空。
查找具有给定键的节点并将其存储在变量中。
队列中的最后一个节点是最深的节点。
使用另一个功能删除最深的节点。
使用队列遍历树。
当我们找到该节点时，将其删除并返回。
打印树以查看是否删除了该节点。
让我们看一下代码。
#include <bits/stdc++.h>
using namespace std;
struct Node {
int data;
struct Node *left, *right;
};
struct Node* newNode(int data) {
struct Node* temp = new Node;
temp->data = data;
temp->left = temp->right = NULL;
return temp;
};
void inorder(struct Node* node) {
if (node == NULL) {
return;
}
inorder(node->left);
cout << node->data << " ";
inorder(node->right);
}
void deleteDeepestNode(struct Node* root, struct Node* deleting_node){
queue<struct Node*> nodes;
nodes.push(root);
struct Node* temp;
while (!nodes.empty()) {
temp = nodes.front();
nodes.pop();
if (temp == deleting_node) {
temp = NULL;
delete (deleting_node);
return;
}
if (temp->right) {
if (temp->right == deleting_node) {
temp->right = NULL;
delete deleting_node;
return;
}
else {
nodes.push(temp->right);
}
}
if (temp->left) {
if (temp->left == deleting_node) {
temp->left = NULL;
delete deleting_node;
return;
}
else {
nodes.push(temp->left);
}
}
}
}
Node* deleteNode(struct Node* root, int key) {
if (root == NULL){
return NULL;
}
if (root->left == NULL && root->right == NULL) {
if (root->data == key) {
return NULL;
}
else {
return root;
}
}
queue<struct Node*> nodes;
nodes.push(root);
struct Node* temp;
struct Node* key_node = NULL;
while (!nodes.empty()) {
temp = nodes.front();
nodes.pop();
if (temp->data == key) {
key_node = temp;
}
if (temp->left) {
nodes.push(temp->left);
}
if (temp->right) {
nodes.push(temp->right);
}
}
if (key_node != NULL) {
int deepest_node_data = temp->data;
deleteDeepestNode(root, temp);
key_node->data = deepest_node_data;
}
return root;
}
int main() {
struct Node* root = newNode(1);
root->left = newNode(2);
root->left->left = newNode(3);
root->left->right = newNode(4);
root->right = newNode(5);
root->right->left = newNode(6);
root->right->right = newNode(7);
root->right->left->left = newNode(8);
root->right->left->right = newNode(9);
cout << "删除密钥之前的树： ";
inorder(root);
int key = 5;
root = deleteNode(root, key);
cout << "\nTree after deleting key: ";
inorder(root);
cout << endl;
return 0;
}输出结果如果运行上面的代码，则将得到以下结果。
删除密钥之前的树： 3 2 4 1 8 6 9 5 7 Tree after deleting key: 3 2 4 1 8 6 9 7