在 C++ 中删除值为 k 的叶节点？
让我们首先定义表示包含数据及其左右节点子节点的树节点的结构。如果这是要创建的第一个节点，则它是根节点，否则是子节点。
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,intk)函数，它接受根节点和要删除的节点的数据值。如果给定节点是父节点，则它还会删除其左右子节点。该函数在删除给定节点后返回修改后的根节点。
Node* deleteLeafNode(Node* root, int k) {
if (root == NULL)
return nullptr;
root->leftChild = deleteLeafNode(root->leftChild, k);
root->rightChild = deleteLeafNode(root->rightChild, k);
if (root->data == k && 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 << " ";
}
}示例
让我们看看下面删除值为k的叶节点的实现。
#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* deleteLeafNode(Node* root, int k){ if (root == NULL) return nullptr; root->leftChild = deleteLeafNode(root->leftChild, k); root->rightChild = deleteLeafNode(root->rightChild, k); if (root->data == k && 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(6); root->leftChild = newNode(7); root->rightChild = newNode(7); root->leftChild->leftChild = newNode(5); root->leftChild->rightChild = newNode(3); root->rightChild->rightChild = newNode(7); deleteLeafNode(root, 7); cout << "删除给定叶节点后的中序遍历： "; inorder(root); return 0; }
上面的代码将产生以下输出-
删除给定叶节点后的中序遍历： 5 3 7 6