struct node{
int data;
struct node*left,*right;
};
node* root; //global root
node* getNode(int item)
{
node* new_node = new node;
new_node->data = item;
new_node->left=new_node->right=NULL;
return new_node;
}
node* insert(node* localroot, int item)
{
if(localroot == NULL){
localroot = getNode(item);
}
else if(item < localroot->data)
localroot->left = insert(localroot->left, item);
else if(item > localroot->data)
localroot->right = insert(localroot->right, item);
root = localroot;
return root; //Why do I have to return root if it is global?
//without this output is wrong
}
void inorder(node* root)
{
if(root != NULL){
inorder(root->left);
std::cout << root->data << ' ';
inorder(root->right);
}
}
void postorder(node* root)
{
if(root != NULL){
postorder(root->left);
postorder(root->right);
std::cout << root->data << ' ';
}
}
int main()
{
insert(root, 15);
insert(root, 9);
insert(root, 2);
insert(root, 1);
insert(root, 4);
insert(root, 18);
std::cout<<"inorder traversal of tree is: ";
inorder(root);
std::cout << "\nPostOrder: ";
postorder(root);
return 0;
}
通常我们在 main 中调用 insert 像 root = insert(root, 10);
(其中 root 在 main() 中声明)。我想全局声明根,但插入函数不能为空,它必须返回 node* 值我能得到解释吗?
如果有更好的方法请分享(实际上我想让 insert 成为 void 类型)。
问候,
最佳答案
你写的方式insert
要求它始终返回它修改或创建的节点。这确保了 insert
在没有子节点的节点上设置正确的成员(左或右)。
你可以改写root
通过传入对要设置的指针的引用来纯粹是强制性的:
void insert(int item, node*& localroot = root) {
if (localroot == nullptr) {
localroot = getNode(item);
return;
}
if (item == localroot->data) {
return;
} else if(item < localroot->data) {
insert(item, localroot->left);
} else if(item > localroot->data) {
insert(item, localroot->right);
}
}
要实现的关键点是分配给 localroot
将反射(reflect)在数据结构中,所以:insert(item)
第一次,localroot
是对 root
的引用这是一个空指针。因此,第一个子句适用并且您覆盖 localRoot
带有一个新节点。因为localRoot
是对 root
的引用,也会更新。 localRoot
绑定(bind)到 N->left
或 N->right
,并且第一个子句将再次用指向新创建的节点的指针覆盖该值。 如果默认参数对你来说太神奇了,拆分成两个函数:
void insert_helper(int item, node*& localroot) {
// as above
}
void insert(int item) {
insert_helper(item, root);
}
关于c++ - 在 BST 中插入一个具有全局根的节点,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/64358444/