在 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