在 C++ 中删除值为 x 的叶节点？
让我们首先定义表示包含数据及其左右节点子节点的树节点的结构。如果这是要创建的第一个节点，则它是根节点，否则是子节点。
struct Node {
int data;
struct Node *leftChild, *rightChild;
};接下来我们创建我们的newNode(intdata)函数，它接受一个int值并将其分配给节点的数据成员。该函数返回指向创建的结构节点的指针。新创建的节点的左右子节点也设置为空。
struct Node* newNode(int data){
struct Node* newNode = new Node;
newNode->data = data;
newNode->leftChild = newNode->rightChild = NULL;
return (newNode);
}现在我们创建我们的deleteNode(Node*root,intx)函数，它接受根节点和要删除的节点的数据值。如果给定节点是父节点，则它还会删除其左右子节点。该函数在删除给定节点后返回修改后的根节点。
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输出结果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