[C++] 이진탐색트리를 작성하시오

입력

입력

 

#include <iostream.h>

class Bst;
class BstNode
{
friend class Bst;
private:
	BstNode *Leftchild;
	int data;
	BstNode *Rightchild;
public:
	BstNode(int d=0){
		data=d; Leftchild=0;Rightchild=0;
	}
};

class Bst
{
public:
	Bst(){root=0;};
	BstNode *Find(int x);//탐색
	int degNode(int x);//차수
	int Insert(int x);//삽입
	void maxmin(int &max,int &min, int x); //바로큰값, 바로작은값
	void inorder(); // 중위우선 순회 함수1
	void inorder(BstNode *CurrentNode); // 중위우선 순회 함수1

private:
	BstNode *root;
};

BstNode* Bst::Find(int x) //탐색
{
	BstNode *p=root;
	while(p)
	{
		if(p->data<x)
			p=p->Rightchild;
		else if(p->data>x)
			p=p->Leftchild;
		else
			return p;
	}
	return 0;
}

int Bst::degNode(int x) //차수 (자식수)
{
	int deg=0;
	BstNode *p=root;
	while(p)
	{
		if(p->data<x)
			p=p->Rightchild;
		else if(p->data>x)
			p=p->Leftchild;
		else
			break;
	}
	if(p)
	{
		if(p->Leftchild)
			deg++;
		if(p->Rightchild)
			deg++;
		return deg;
	}else
		return -9999;
}

int Bst::Insert(int x) //삽입
{
	BstNode *p = root;
	BstNode *q = 0;
	
	if(!root) //첫 노드
	{
		root = new BstNode(x);
		return 0;
	}
	else
	{
		while(p)
		{
			q=p;
			if(p->data<x)
				
				p=p->Rightchild;
			else if(p->data>x)
				p=p->Leftchild;
			else
				break; //같은경우 -9999 처리
		}

		if(!p) //널 만나서 종료됨
		{
			if(q->data >x)
				q->Leftchild= new BstNode(x);
			else
				q->Rightchild = new BstNode(x);
			return 0;
		}
		else //같은 수가 있는경우
			return -9999;
	}
}

void Bst::maxmin(int &max,int &min, int x) //바로큰값, 바로작은값
{
	int deg=0;
	BstNode *p=root;
	BstNode *q=0;
	BstNode *r=0;
	BstNode *s=0;

	while(p)
	{
		q=p;
		if(p->data<x)
			p=p->Rightchild;
		else if(p->data>x)
			p=p->Leftchild;
		else
			break;
	}
	if(p)
	{
		if(p->Leftchild)
			deg++;
		if(p->Rightchild)
			deg++;
	}
	if(deg==2)//자식이 2이면
	{
		r=p;

		// 바로 큰 값
		p=p->Rightchild;
		while(p)
		{
			q=p;
			p=p->Leftchild;
		}max=q->data;
		// 바로 작은 값
		r=r->Leftchild;
		while(r)
		{	
			s=r;
			r=r->Rightchild;
		}min=s->data;
	}
}

void Bst::inorder() // 중위우선 순회 함수1
{
	inorder(root);
}
void Bst::inorder(BstNode *CurrentNode) // 중위우선 순회 함수1
{
	if(CurrentNode) {
		inorder(CurrentNode->Leftchild);
		cout << CurrentNode->data << ", ";
		inorder(CurrentNode->Rightchild);
	}
}


int main()
{
	Bst t;
	int max,min;
	int menu,x;

	cout<<"******** 이진 탐색 트리 메뉴 ***********"<<endl;
	cout<<"* 1. 삽입           2. 바로큰값/작은값 *"<<endl;
	cout<<"* 3. 중위우선순회   4. 종료            *"<<endl;
	cout<<"****************************************"<<endl;
	
	while(1) 
	{
		cout << "menu: ";
		cin>>menu;
		
		switch(menu) 
		{
			case 1:
				cout<<"삽입 :";
				cin>>x;
				t.Insert(x);
				break;
			case 2:
				cout<<"기준값 :";
				cin>>x;
				t.maxmin(max,min,x);
				cout<<"max : "<<max<<"	"<<"min : "<<min<<endl;
				break;
			case 3:
				t.inorder();
				cout <<"\n";
				break;
			case 4:
				return 0;
		}
	}
	return 0;
}