数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
时尚研究
法律研究使用 C++ 删除带有值 k 的叶子节点？
让我们首先定义表示树节点的结构，它包含数据及其左右节点子节点。如果这是要创建的第一个节点，则它是一个根节点，否则是一个子节点。
struct Node {
int data;
struct Node *leftChild, *rightChild;
};接下来，我们创建我们的 newNode(int data) 函数，它获取一个 int 值并将其分配给节点的数据成员。该函数返回指向所创建的结构 Node 的指针。此外，新创建节点的左右子节点都设置为 null。
struct Node* newNode(int data) {
struct Node* newNode = new Node;
newNode->data = data;
newNode->leftChild = newNode->rightChild = NULL;
return (newNode);
}现在，我们创建我们的 deleteNode(Node* root, int k) 函数，它获取根节点和要删除的节点的数据值。如果给定的节点是父节点，那么它还删除其左右子节点。该函数在删除给定节点后返回修改后的根节点。
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)。
void inorder(Node* root){
if (root != NULL){
inorder(root->leftChild);
inorder(root->rightChild);
cout << root->data << " ";
}
}示例
让我们看看以下删除具有值 k 的叶子节点的实现。
#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* 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 traversal after deleting given leaf node: ";
inorder(root);
return 0;
}输出
以上代码将产生以下输出 −
Inorder traversal after deleting given leaf node: 5 3 7 6
更新时间：2021 年 1 月 16 日
94 次浏览
广告