Click here to Skip to main content
15,891,513 members
Please Sign up or sign in to vote.
1.00/5 (1 vote)
See more:
#include <iostream>
using namespace std;
template <typename T>
struct tree_node {
	T key;
	tree_node* left = nullptr, *right = nullptr;
	tree_node(T key)
	{
		this->key = key;
	}
};
template <typename T>
void insert(tree_node<int>*& my_tree, T key)
{
	if (my_tree == nullptr) my_tree = new tree_node<T>{ key };
	if (key < my_tree->key) insert(my_tree->left, key);
	else insert(my_tree->right, key);
}

template <typename T>
void visit_every_member(const tree_node<T>* my_tree)
{
	// This uses an inorder traversal
	// 1. traverse left subtree
	// 2. visit the root
	// 3. traverse right subtree

	if (my_tree == nullptr) return; // nothing to visit for an empty tree
	visit_every_member(my_tree->left);  // Step 1. Traverse left subtree
	std::cout << my_tree->key << std::endl; //Step 2.  Visit the root
	visit_every_member(my_tree->right); // Step 3. Traverse right subtree
}
template <typename T>
T FindingPredecessorSuccessor(tree_node<T>* my_tree, tree_node<T>*& pre, tree_node<T>*& suc, T key)
{
	if (my_tree != nullptr) return 0;
	if (my_tree->key == key)
	{
		if (my_tree->left != nullptr)
		{
			tree_node<T>* tmp = my_tree->left;
			while (tmp->right)
			{
				tmp = tmp->right;
			}
			pre = tmp;
		}
		if (my_tree->right != nullptr)
		{
			tree_node<T>* tmp = my_tree->right;
			while (tmp->left)
			{
				tmp = tmp->left;
			}
			suc = tmp;
		}
		return 0;
	}
	if (my_tree->key > key)
	{
		suc = my_tree;
		FindingPredecessorSuccessor(my_tree->left, pre, suc, key);
	}
	else
	{
		pre = my_tree;
		FindingPredecessorSuccessor(my_tree->right, pre, suc, key);
	}

}
int main()
{
	tree_node<int>* pre = nullptr, *suc = nullptr;
	tree_node<int>* my_tree = nullptr;
	int key = 65;
    my_tree = insert(my_tree, 50);
	insert(my_tree, 50);
	insert(my_tree, 30);
	insert(my_tree, 20);
	insert(my_tree, 40);
	insert(my_tree, 70);
	insert(my_tree, 60);
	insert(my_tree, 80);
	visit_every_member(my_tree);
	
	FindingPredecessorSuccessor(my_tree, pre, suc, key);
	if (pre != nullptr)
		cout << "Predecessor is " << pre->key << endl;
	else
		cout << "There is no Predecessor" << endl;
	if (suc != nullptr)
		cout << "Successor is " << suc->key;
	else
		cout << "There is no Successor" << endl;

}


What I have tried:

I got this problem in the line "my_tree = insert(my_tree, 50);" on main function.
It shows that "A value type 'void' cannot be assigned to any entity of type "tree_node<int>*".

How can I fix it?
Posted
Updated 9-Apr-20 23:03pm

Quote:
template <typename t="">
void insert(tree_node<int>*& my_tree, T key)
The above function returns void, that is nothing. You cannot assign nothing to your variable. Note it takes a reference to a pointer as argument, hence you may call it this way:
insert(my_tree, 50);
no need to assign.
 
Share this answer
 
Comments
Richard MacCutchan 10-Apr-20 6:30am    
+5At last I understand "reference to pointer", thank you.
CPallini 10-Apr-20 7:35am    
Thank you, Richard.
Well, references, where you can use them, are elegant (at least in my opinion) replacements for pointers. Thus, in the OP code the reference to pointer simply replace the equivalent double pointer (which you have to use with C programming language, for instance).
Richard MacCutchan 10-Apr-20 7:37am    
Yes, I guess I should RTFM some more. :)
C++
tree_node<int>* my_tree = nullptr;
int key = 65;
my_tree = insert(my_tree, 50);

You initialise the pointer my_tree to the null pointer value (i.e. nothing), and then try to use that reference as if it points to an actual object. You need to make it point to a proper tree_node like:
C++
tree_node<int>* my_tree = new tree_node<int>(); // syntax may not be correct
int key = 65;
my_tree = insert(my_tree, 50);


Also note that the struct definition is missing the type, it should be
C++
template <typename T>
struct tree_node<T>{


The insert function does not return a tree_node pointer.

There are probably some other issues that I have not noticed.
 
Share this answer
 
v2
It still got same problem after I do
tree_node<int>* my_tree = new tree_node<int>(); // syntax may not be correct
int key = 65;
my_tree = insert(my_tree, 50);
 
Share this answer
 
Comments
Richard MacCutchan 10-Apr-20 4:29am    
What problem? Please do not assume that we can see your screen, or read your mind: provide all the details.
Patrice T 10-Apr-20 5:47am    
Use Improve question to update your question.
So that everyone can pay attention to this information.
Greg Utas 10-Apr-20 7:35am    
Seriously? You're assigning to my_tree again, even though it's been clearly pointed out that insert returns nothing?
Rick York 10-Apr-20 10:34am    
How does this qualify as a solution?

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)



CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900