在 C++ 中删除值为 x 的叶节点？

让我们首先定义表示包含数据及其左右节点子节点的树节点的结构。如果这是要创建的第一个节点，则它是根节点，否则是子节点。

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);
}

现在我们创建我们的 deleteNode(Node* root, int x) 函数，它接受根节点和要删除的节点的数据值。如果给定节点是父节点，则它还会删除其左右子节点。该函数在删除给定节点后返回修改后的根节点。

Node* deleteLeafNode(Node* root, int x){
   if (root == NULL)
      return nullptr;
   root->leftChild = deleteLeafNode(root->leftChild, x);
   root->rightChild = deleteLeafNode(root->rightChild, x);
   if (root->data == x && root->leftChild == NULL && root->rightChild == NULL)
      return nullptr;
   return root;
}

最后为了在删除后显示树，我们有一个函数 inorder(Node* root) ，它在 inorder 函数中遍历树。

void inorder(Node* root){
   if (root != NULL){
      inorder(root->leftChild);
      inorder(root->rightChild);
      cout << root->data << " ";
   }
}

示例

让我们看看下面删除值等于 x 的叶节点的实现

#include <iostream>
using namespace std;
struct Node {
   int data;
   struct Node *leftChild, *rightChild;
};
struct Node* newNode(int data){
   struct Node* newNode = new Node;
   newNode->data = data;
   newNode->leftChild = newNode->rightChild = NULL;
   return (newNode);
}
Node* deleteNode(Node* root, int x){
   if (root == NULL)
      return nullptr;
   root->leftChild = deleteNode(root->leftChild, x);
   root->rightChild = deleteNode(root->rightChild, x);
      if (root->data == x && root->leftChild == NULL &&
      root->rightChild == NULL)
         return nullptr;
   return root;
}
void inorder(Node* root){
   if (root != NULL){
      inorder(root->leftChild);
      inorder(root->rightChild);
      cout << root->data << " ";
   }
}
int main(void){
   struct Node* root = newNode(4);
   root->leftChild = newNode(2);
   root->rightChild = newNode(12);
   root->leftChild->leftChild = newNode(3);
   root->leftChild->rightChild = newNode(5);
   root->rightChild->rightChild = newNode(9);
   deleteNode(root, 3);
   cout << "删除后的中序遍历： ";
   inorder(root);
   return 0;
}

上面的代码将产生以下输出 -

删除后的中序遍历： 5 2 9 12 4