Tree.cpp

# include <iostream>
# include <string>
# include <string.h>
# include <cstring>
# include <bitset>
using namespace std;

struct node
{
	char data;
	node *left;
	node *right;
};

node *root = NULL;
static int flag;

void insert(char key ,node*leaf)
{
	if (root == NULL)
	{
		root = new node;
		root->data = key;
		root->left = NULL;
		root->right = NULL;
	}
	else
	{
		//insert at left node 
		if ((int)key <(int)leaf->data)
		{
			//make sure that the node is empty
			if (leaf->left == NULL)
			{
				leaf->left = new node;
				leaf->left->data = key;
				leaf->left->left = NULL;
				leaf->left->right = NULL;
			}
			else
			{
				insert(key,leaf->left);
			}
		}
		//insert at right node
		else if ((int)key > (int)leaf->data)
		{
			//make sure that node is empty
			if (leaf->right == NULL)
			{
				leaf->right = new node;
				leaf->right->data = key;
				leaf->right->left = NULL;
				leaf->right->right = NULL;
			}
			else
			{
				insert(key, leaf->right);
			}
		}
	}
}

void POST(node *leaf)  //left --- right --- root
{
	if (leaf != NULL)
	{
		if (leaf->left) POST(leaf->left);
		if (leaf->right) POST(leaf->right);
		if (flag == 0)
		{
			cout << leaf->data;
			flag = 1;
		}
		else
			cout <<" "<<leaf->data;
	}
	else return;
}

void IN(node *leaf)  //left --- root --- right
{
	if (leaf != NULL)
	{
		if (leaf->left) IN(leaf->left);
		if (flag == 0)
		{
			cout << leaf->data;
			flag = 1;
		}
		else
			cout << " " << leaf->data;
		if (leaf->right) IN(leaf->right);
	}
	else return;
}

void PRE(node *leaf)  //root --- left --- right
{
	if (leaf != NULL)
	{
		if (flag == 0)
		{
			cout << leaf->data;
			flag = 1;
		}
		else
			cout << " " << leaf->data;
		if (leaf->left) PRE(leaf->left);
		if (leaf->right) PRE(leaf->right);
	}
	else return;
}

bool search(char key, node *leaf)
{
	if (leaf != NULL)
	{
		if ((int)key < (int)leaf->data)
			search(key, leaf->left);
		else if ((int)key >(int)leaf->data)
			search(key, leaf->right);
		else
			return true; ///you have found the key in this tree
	}
	else
		return false; // you ca't search this tree

}


int main()
{
	string Choise;
	while (getline(cin, Choise))
	{
		
		//show the IN order
		if (Choise == "INFIXA")
		{
			flag = 0;
			IN(root);
		}

		//show the PRE order
		if (Choise == "PREFIXA")
		{
			flag = 0;
			PRE(root);
		}

		//show the POST order
		if (Choise == "POSFIXA")
		{
			flag = 0;
			POST(root);
		}

		//insert into the tree
		if (Choise[0] == 'I' && Choise[1]==' ')
		{
			insert(Choise[2], root);
			continue;
		}

		//search the tree
		if (Choise[0] == 'P' && Choise[1] == ' ')
		{
			if (search(Choise[2], root))
			{
				cout << Choise[2] << " existe" ;
			}
			else
			{
				cout<<Choise[2]<<" nao existe";
			}
		}
		

		if (Choise != "")
			cout << endl;

	}

	return 0;
}