#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#include <iostream>

struct Node
{
	int data;
	Node *kiri;
	Node *kanan;
};

void tambah(Node **root, int databaru)
{
	if((*root) == NULL)
	{
		Node *baru;
		baru = new Node;
		baru->data=databaru;
		baru->kiri=NULL;
		baru->kanan=NULL;
		(*root)=baru;
		(*root)->kiri=NULL;
		(*root)->kanan=NULL;
		printf("Data Ditambah !");
	}
	else if(databaru<(*root)->data)
		tambah(&(*root)->kiri,databaru);
	else if(databaru>(*root)->data)
		tambah(&(*root)->kanan,databaru);
	else if (databaru==(*root)->data)
		printf("Data Sudah Ada !");
}

void preOrder(Node *root)
{
	if(root!=NULL)
	{
		printf(" %d ", root->data);
		preOrder(root->kiri);
		preOrder(root->kanan);
	}
}

void inOrder(Node *root)
{
	if(root!=NULL)
	{
		inOrder(root->kiri);
		printf("% d", root->data);
		inOrder(root->kanan);
	}
}

void postOrder(Node *root)
{
	if(root!=NULL)
	{
		postOrder(root->kiri);
		postOrder(root->kanan);
		printf("% d", root->data);
	}
}
void cari_terbesar(Node *p)
{
	if(p==NULL)
	{
		return;
	}
	else
	{
		if(p->kanan==NULL)
		{
			printf("%d",p->data);
			return;
		}
	else
	{
		cari_terbesar(p->kanan);
		return;
	}
	}
}
void cari_terkecil(Node *p)
{
	if(p==NULL)
	{
		return;
	}
	else
	{
		if(p->kiri==NULL)
		{
			printf("%d",p->data);
			return;
		}
	else
	{
		cari_terbesar(p->kiri);
		return;
	}
	}
}

void search(Node **root, int cari)
{
    if((*root) == NULL)
    {
        printf("Data tidak ditemukan!");
    }
    //jika data yang dicari lebih kecil dari isi root
    else if(cari < (*root)->data)
        search(&(*root)->kiri,cari);
    //jika data yang dicari lebih besar dari isi root
    else if(cari > (*root)->data)
        search(&(*root)->kanan,cari);
    //jika data yang dicari sama dengan isi dari variabel root
    else if(cari == (*root)->data)
        printf("Data ditemukan!");
}


int main()
{
	int pil, data, cari;
	Node *pohon;
	pohon=NULL;
	do
	{
		system ("cls");
		printf("\t\n==================================================\n");
		printf("\t\tPROGRAM TREE\n");

		printf("\t\n==================================================\n");
		printf("\nMenu");
		printf("\n------\n");
		printf("1. Tambah\n");
		printf("2. Lihat PreOrder\n");
		printf("3. Lihat InOrder\n");
		printf("4. Lihat PostOrder\n");
		printf("5  Search \n");
		printf("6. EXIT\n");
		printf("7. Pilihan :");
		scanf("%d", &pil);
		switch(pil)
		{
			case 1:
				printf("\nINPUT : ");
				printf("\n======================\n");
				printf("Data Baru : ");
				scanf("%d", &data);
				tambah (&pohon, data );
				printf("\n======================\n");
				break;

			case 2:
				printf("\nOUTPUT PRE-ORDER : ");
				printf("\n======================\n");
				if (pohon!=NULL)
				{
					preOrder(pohon);
					printf("\n======================\n");
				}

				else
				printf("Masih Kosong !");
				break;

			case 3:
				printf("\nOUTPUT in-ORDER : ");
				printf("\n======================\n");
				if (pohon!=NULL)
				{
					inOrder(pohon);
					printf("\n======================\n");
				}
				else
				printf("Masih Kosong !");
				break;

			case 4:
				printf("\nOUTPUT POST-ORDER : ");
				printf("\n======================\n");
				if (pohon!=NULL)
				{
					postOrder(pohon);
					printf("\n======================\n");
				}
				else
				printf("Masih Kosong !");


				break;

                     		case 5:
								printf("\n output search : ");
								if(pohon!=NULL)
								{
									 printf("\nPRE ORDER  : ");
                          			 preOrder(pohon); //panggil fungsi
                          			 printf("\nIN ORDER   : ");
                          			 inOrder(pohon); //panggil fungsi
                          			 printf("\nPOST ORDER : ");
                          		 		postOrder(pohon); //panggil fungsi
                          			 printf("\n\nPENCARIAN DATA");
									printf
									("\n masukan data yg dicari:");
									scanf("%d", &data);
									search(&pohon, data);

								}
								else
								printf("masih kosong");
					break;

			case 6:
				break;
		}getch();
	}while(pil!=7);
	return 0;
}