请输出c++代码,实现树的节点增加 删减 查找
时间: 2023-06-20 11:04:05 浏览: 85
c++实现二叉查找树示例
以下是一个简单的树结构的 C++ 实现,包括节点的增加、删除和查找功能:
```c++
#include<iostream>
#include<vector>
using namespace std;
struct TreeNode{
int val;
vector<TreeNode*> children;
TreeNode(int x): val(x){}
};
class Tree{
public:
Tree(){
root = NULL;
}
// 添加节点
void addNode(int parent_val, int val){
TreeNode* new_node = new TreeNode(val);
if(!root){
root = new_node;
return;
}
TreeNode* parent = findNode(root, parent_val);
parent->children.push_back(new_node);
}
// 删除节点
void deleteNode(int val){
TreeNode* node = findNode(root, val);
if(!node){
cout << "Node not found!" << endl;
return;
}
if(node == root){
delete root;
root = NULL;
return;
}
TreeNode* parent = findParent(root, val);
for(int i=0; i<parent->children.size(); i++){
if(parent->children[i]->val == val){
parent->children.erase(parent->children.begin() + i);
break;
}
}
delete node;
}
// 查找节点
TreeNode* findNode(TreeNode* node, int val){
if(!node) return NULL;
if(node->val == val) return node;
for(int i=0; i<node->children.size(); i++){
TreeNode* found = findNode(node->children[i], val);
if(found) return found;
}
return NULL;
}
private:
TreeNode* root;
// 查找节点的父节点
TreeNode* findParent(TreeNode* node, int val){
if(!node || node->val == val) return NULL;
for(int i=0; i<node->children.size(); i++){
if(node->children[i]->val == val) return node;
TreeNode* parent = findParent(node->children[i], val);
if(parent) return parent;
}
return NULL;
}
};
int main(){
Tree t;
t.addNode(0, 1);
t.addNode(1, 2);
t.addNode(1, 3);
t.addNode(2, 4);
t.addNode(2, 5);
t.addNode(3, 6);
TreeNode* found = t.findNode(t.root, 2);
if(found) cout << found->val << endl;
t.deleteNode(2);
found = t.findNode(t.root, 2);
if(found) cout << found->val << endl;
else cout << "Node not found!" << endl;
return 0;
}
```
这个实现中,树节点的结构体包括节点值和一个指向其所有子节点的向量。树类中实现了添加节点、删除节点和查找节点的方法。其中,查找节点的方法使用了递归实现。
阅读全文