منبع اصلی نوشتار زیر در این لینک قرار دارد

کد و الگوریتم درخت جست و جوی دودویی Binary search tree با ++C

BST Binary search tree کد و الگوریتم درخت جست و جوی دودویی Binary search tree با ++C

درخت جست و جوی دو دویی – Binary search tree :

درخت جست و جوی دودویی یکی از بهترین ساختمان داده ها است و بر اساس آن می توان ساختمان داده های متعددی تولید کرد.این درخت که به آن BST هم گفته می شود دارای ویژگی ها بسیار خوبی است ازجمله سرعت در انجام عملیات های نختلف و نگه داری از آن.

درخت جست و جوی دودویی درخت است که حداکثر دو فرزند دارد و تمام نود ها در زیر درخت سمت راست یک گره برزگ تر مساوی گره است و تمام گره ها در زیر درخت سمت چپ گره کوچک تر از گره است به شکل زیر نگاه کنید :

BST کد و الگوریتم درخت جست و جوی دودویی Binary search tree با ++C

به بالا ترین گره در درخت که فرزند هیج گره ای نیست ریشه می گویند.

برای  گره ها  ساختمان داده زیر را درنظر گرفته ام :

class node
{
public:
	int data;
	node* parent;
	node* leftChild;
	node* rightChild;
	node(void);
};

node::node(void)
{
	data = 0;
	parent = NULL;
	leftChild = NULL;
	rightChild = NULL;
}

که دارای ویژگی های زیر است :

data : دیتا که همان مقدار یا کلید گره است و باید توجه داسته باشید که مقداری منحصر به فرد است یعنی دو گره یک مقدار ندارند ،البنه با کمی تغییر کد می توانید این مشکل را حل کنید.

parent: که اشارگری به کلاس node است و به پدر یک گره اشاره می کند ، تمام گره های پدر دارند بجز ریشه که نال است.

leftChild: اشارگری به شی از کلاس node است که به بچه ی سمت چپ یک گره اشاره می کند و در صورتی که بچه سمت چپ وجود نداشت مقدار نال را دارد.

rightChild: اشارگری به شی از کلاس node است که به بچه ی سمت راست یک گره اشاره می کند و در صورتی که بچه سمت راست وجود نداشت مقدار نال را دارد.

node : سازنده کلاس است .

در شکل زیر ساختمان داده گره ها را می بینید:

Node کد و الگوریتم درخت جست و جوی دودویی Binary search tree با ++C

برای درخت هم کلاس و ساختمان داره زیر را در نظر گرفته ام:

//binary search tree
class bst
{
public:
	node* root;
	
	bst(void);
	void insert(int);
	void display(node*, int);
	node* minimum();
	node* maximum();
	node* search(int);
	void inorder_tree_walk(node*);
	node* successor(node*);
	node* predecessor(node *);
	void transplant(node*, node*);
	void deletion(node *);
};

در ادامه تمام توابع درون آن را همراه الگوریتمشان شرح خواهیم داد:

root: این کلاس فقط یک ویژگی دارد و آن ریشه درخت است.

تابع Insert :

این تابع یک مقدار را می گیرد و آن را به درخت اضافه می کند.اگر یادتان باشد گفتیم که در درخت جست و جوی دودویی گره های سمت راست یک گره بزرگ تر مساوی یک گره اند و  گره های سمت سمت یک گره کوچک تر یک گره انید ما نیز برای اضافه کردن یک گره از همین قاعده استفاده می کنیم اگر درخت خالی بود آن هیچ کار خاصی نمی کنیم و گره جدید را ریشه قرار می دهیم اگر درخت خالی نبود از ریشه شروع به حرکت می کنیم . مقداری که می خواهیم به درخت اضافه کنیم اگر بزرگ تر مساوی ریشه بود به سمت راست می رویم اگر کوچک تر بود به سمت چپ می رویم و این کار را آنقدر ادامه می دهیم تا به یک جای خالی (گره ی نال) در درخت برسیم . وقتی که به جای مناسب رسیدیم اشارگر به پدر را برای گره ی جدید تنظیم می کنیم در زیر کد تا Insert را می بینید:

void bst::insert(int d)
{
	node* newNode = new node();
	newNode->data = d;

	if (root == NULL)
	{
		root = newNode;
	}
	else
	{
		node* tempNode = new node();
		node* backTempNode = new node();
		tempNode = root;

		while (tempNode != NULL)
		{
			backTempNode = tempNode;
			if (tempNode->data <= newNode->data)
			{
				tempNode = tempNode->rightChild;
			}
			else
			{
				tempNode = tempNode->leftChild;
			}
		}

		newNode->parent = backTempNode;
		if (backTempNode->data <= newNode->data)
		{
			backTempNode->rightChild = newNode;
		}
		else
		{
			backTempNode->leftChild = newNode;
		}
	}
}

اگر ارتفاع درخت h باشد هزینه درج گره جدید برابر  او h  است.

 

تابع display :

این تابع درخت را در خروجی کنسول رسم می کند . رسم یک درخت معمولا کار سخت و زمان گیری است ولی با یه کم کد باحال می شه این کار در چند خط کد به زیبایی انجام داد :

کد تابع نمایش :

//display binary search tree
void bst::display(node *Node,int level)
{
	if (root == NULL)
	{
		cout << "Tree is empty." << endl;
	}
	else
	{
		if (Node->rightChild != NULL)
		{
			display(Node->rightChild, level + 1);
		}
		
		if (Node != root)
		{
			for (int i = 0; i < level + 1; i++)
			{
				cout << "      ";
			}
		}
		else
		{
			cout << "Root->";
		}

		cout << Node->data << endl;

		if (Node->leftChild != NULL)
		{
			display(Node->leftChild, level + 1);
		}
	}

}

در زیر نمونه ای از رسم درخت را می بینید :

display bst tree کد و الگوریتم درخت جست و جوی دودویی Binary search tree با ++C

همین طور که می بینید درخت بسیار مرت چاپ شده است بطوری که هر گره زیر پدر خود قرار دارد ، همین طور ریشه مشخص شده است.

تابع minimum :

این تابع کوچک ترین گره ی درخت را بر می گرداند.همین طور که گفتیم هر گره های سمت چپ یک گره از آن گره کوچک تر هستند، پس کوچک ترین گره سمت چپ ترین گره است پس ما آن قدر به سمت چپ می رویم تا به نال برسیم.

کد زیر که تابع مینیمم است :

node* bst::minimum()
{
	node* tempNode = new node();
	node* backTempNode = new node();
	backTempNode = tempNode = root;
	while (tempNode != NULL)
	{
		backTempNode = tempNode;
		tempNode = tempNode->leftChild;
	}
	return backTempNode;
}

 

تابع maximum :

تابع ماکزیمم هم مانند تابع مینیمم است ، گره های سمت راست یک گره بزرگ تر مساوی آن گره هستند پس بزرگ ترین گره سمت راست ترین گره در درخت است  و برای رسیدن به آن از ریشه شروع می کنیم و آن قدر به راست می رویم تا به هیچ (نال) برسیم.

کد تابع ماکزیمم را در زیر می بینید:

//return maximum node
node* bst::maximum()
{
	node* tempNode = new node();
	node* backTempNode = new node();
	backTempNode = tempNode = root;
	while (tempNode != NULL)
	{
		backTempNode = tempNode;
		tempNode = tempNode->rightChild;
	}
	return backTempNode;
}

 

تابع Search :

همین طور که از اسم درخت (Binary search tree)  مشخص است سرچ در درخت یکی از جنبه های خیلی مهم این درخت است.فرض کنید یک گره به اسم x را در درخت می خواهیم بیابیم از ریشه شروع به مقایسه می کنیم اگر x.data برابر با ریشه بود یک اشارگر به ریشه برمی گردانیم . در صورت برابر نبود ، اگر x.data بزرگ تر مساوی مقدار ریشه بود به سمت راست می رویم

اگر کوچک تر بود به سمت چپ می رویم این کار را مرتب انجام می دهیم تا به گره مورد نظر برسیم و اگر تا برگ های (برگ به گره های آخر درخت می گویند که هیچ فرزندی ندارند) درخت رسیدم و گره مورد نظر را پیدا نکردیم هیچ یا همان نال را بر می گردانیم که مشخص می کند گره ی مورد نظر در درخت نبوده است.

کد زیر مربوط به تا بع سرچ است :

//Search in BST Tree
node* bst::search(int Data)
{
	node* tempNode = new node();
	tempNode = root;
	while (tempNode != NULL)
	{
		if (tempNode->data == Data)
		{
			return tempNode;
		}
		else
		{
			if (tempNode->data <= Data)
			{
				tempNode = tempNode->rightChild;
			}
			else
			{
				tempNode = tempNode->leftChild;
			}
		}
	}
	return NULL;
}

 

تابع  inorder_tree_walk :

این تابع به صورت inorder  درخت را پیمایش می کند یعنی ابتدا فرزند چپ را می بیند بعد ریشه و بعد فرزند سمت راست که این کار نود های درخت را به صورت سعودی و مرتب شده نشان می دهد.

//inoreder tree walk = show all node in sorted mood
void bst::inorder_tree_walk(node* currentNode)
{
	if (root != NULL)
	{
		if (currentNode->leftChild != NULL)
		{
			inorder_tree_walk(currentNode->leftChild);
		}

		cout << currentNode->data << "  ,";

		if (currentNode->rightChild != NULL)
		{
			inorder_tree_walk(currentNode->rightChild);
		} 
	}
	else
	{
		cout << "Tree is empty!" << endl;
	}
}

 

تابع successor :

successor یک گره به گره ای می گویند که اگر تمام گره های یک درخت را مرتب شده و سعودی کنار هم قرار دهیم بلافاصله بعد از گره مورد نظر ما  ظاهر می شود ، این تابع در تابع حذف گره کاربرد دارد.

می توان درخت را به سورت سورت شده در آورد و بعد ساکسسور گره را پیدا کرد ولی این کار بسیار پرهزینه است . را آسان تری نیز برای این کار وجود دارد.

اگر گره ای که می خواهیم ساکسسورش را پیدا کنیم بچه ی سمت راست داشت آنگاه ساکسسور گره کوچک ترین گره در زیر درخت سمت راست گره است به شکل زیر دقت کنید:

successor کد و الگوریتم درخت جست و جوی دودویی Binary search tree با ++C

همین طور که می بینید successor  گره نود گره ی نود و پنج است که در زیر درخت سمت راست گره ی نو کوچک ترین گره است.

این روش برای زمانی بود که گره بچه ی سمت راست داشته باشد .حال اگر گره ای که می خواستیم  successor آن را پیدا کنیم فرزند سمت راست نداشت یا کلا فرزند نداشت چه کنیم؟
در این موقع از پدر گره ی مورد نظر شروع می کنیم و مرتب به بالا می رویم تا زمانی این کار را می کنیم که گره ای که رویش هستیم فرزند سمت راست پدرش باشد و به نال نرسیده باشیم.

به شکل بالا نگاه کنید successor گره ی ۸۷ را می خواهیم پیدا کنیم ، از پدر ۸۷ مه گره ی ۸۵ است شروع می کنیم به بالا رفتن ، ۸۷ پسر سمت راست ۸۵ است پس مجاز است دوباره یک گره می رویم بالا و به گره ی ۹۰ می رسیم ۸۵ گره ی سمت چپ ۹۰ است پس همین جا دست از کار می کشیم ، ۹۰ ساکسسور ۸۷ است.

کد تابع successor را در زیر می بینید :

//successor
node* bst::successor(node* currentNode)
{
	node* tempNode = new node();
	node* backTempNode = new node();
	tempNode = currentNode;

	if (tempNode->rightChild != NULL)
	{
		tempNode = tempNode->rightChild;
		while (tempNode != NULL)
		{
			backTempNode = tempNode;
			tempNode = tempNode->leftChild;
		}
		return backTempNode;
	}
	else
	{
		backTempNode = tempNode;
		tempNode = tempNode->parent;
		while (tempNode != NULL && tempNode->rightChild == backTempNode)
		{
			backTempNode = tempNode;
			tempNode = tempNode->parent;
		}
		return tempNode;
	}
}

 

تابع predecessor :

predecessor یک گره به گره ای می گویند که در حالت سورت شده تمام گره ها دقیقا قبل از گره ی مورد نظر می آید.

predecessor دقیقا پیدا کردنش شبیه ساکسسور است ولی هر کاری که برای ساکسسور می کردیم برعکسش را برای این تابع می کنیم.

کد تابع predecessor را در زیر می بینید :

 

//predecessor
node* bst::predecessor(node* currentNode)
{
	node* tempNode = new node();
	node* backTempNode = new node();
	tempNode = currentNode;

	if (tempNode->leftChild != NULL)
	{
		tempNode = tempNode->leftChild;
		while (tempNode != NULL)
		{
			backTempNode = tempNode;
			tempNode = tempNode->rightChild;
		}
		return backTempNode;
	}
	else
	{
		backTempNode = tempNode;
		tempNode = tempNode->parent;
		while (tempNode != NULL && tempNode->leftChild == backTempNode)
		{
			backTempNode = tempNode;
			tempNode = tempNode->parent;
		}
		return tempNode;
	}
}

تابع transplant :

این تابع در تابع حذف گره از درخت استفاده می شود ، این تابع دوگره u و v را به عنوان ورودی می گیرد و اگر u ریشه درخت باشد آنگاه v را ریشه درخت قرار می دهد ،اگر u ریشه دره نباشد پدر u را به v اشاره می دهد ،و اگر v نال نبود پدر v را پدر u قرار می دهد ، در واقع این تابع v را جای u قرار می دهد و از نظر رابطه با گره ی پدر کار ها را درست می کند ولی کاری به جابهجا کردن فرزندان u , v ندارد.

کد این تابع را در زیر آمده است :

//transplant
void bst::transplant(node* u, node* v)
{
	if (u->parent == NULL)
	{
		root = v;
	}
	else
	{
		if (u == u->parent->leftChild)
		{
			u->parent->leftChild = v;
		}
		else
		{
			u->parent->rightChild = v;
		}
	}
	if (v != NULL)
	{
		v->parent = u->parent;
	}
}

تابع deletion :

این تابع گره ای را به عنوان ورودی می گیرد و آن را از درخت حذف می کند ، الگوریتم آن به این شکل است :

– اگر گره هیچ فرزندی نداشت خوب کاری خاصی انجام نمی دهیم فقط حذفش می کنیم.

– اگر گره فرزند سمت راست نداشت با استفاده از تابع transplant فرزند سمت چپش را جایش می گذاریم.

-اگر گره فرزند فقط سمت راست  داشت ، با استفاده از transplant فرزند سمت راستش را جایش می می گذاریم.

– اگر گره دو فرزند داشت ، آنگاه  successor گره را پیدا می کنیم ،
-اگر ساکسسور گره فرزند گره مورد نظر نبود : آنگاه با استفاده از transplant بچه ی سمت راست ساکسسور را جا ساسسکسور می گداریم و فرزند راشت ساکسسور را فرزند راست گره ی مورد نظر قرار می دهیم،و در ادامه با استفاده از تابع transplant ساکسسور را جای گره ی مورد نظز می گذاریم و بچه ی سمت چپ ساکسسور را بچه ی سمت راست گره ی مورد می کنیم.

-اگر ساکسسور گره ی فرزند گره ی مورد نظر بود:با استفاده از تابع transplant ساکسسور را جای گره ی مورد نظز می گذاریم و بچه ی سمت چپ ساکسسور را بچه ی سمت راست گره ی مورد می کنیم.

یه خورده چیزی که خواستم بگم عجیب قریب شد اگر به کد نگاه کنید حتما متوجه منظورم می شوید :

//remove node from tree
void bst::deletion(node *z)
{
	if (z->leftChild == NULL)
	{
		transplant(z, z->rightChild);
	}
	else
	{
		if (z->rightChild == NULL)
		{
			transplant(z, z->leftChild);
		}
		else
		{
			node* succesor = new node();
			succesor = successor(z);
			if (succesor->parent != z)
			{
				transplant(succesor, succesor->rightChild);
				succesor->rightChild = z->rightChild;
				succesor->rightChild->parent = succesor;
			}
			transplant(z, succesor);
			succesor->leftChild = z->leftChild;
			succesor->leftChild->parent = succesor;
		}
	}
	delete z;
}

 

 تابع menu :

این تابع منویی برای  کار کردن با درخت جست و جوی دودویی می سازد مانند شکل زیر:

menu کد و الگوریتم درخت جست و جوی دودویی Binary search tree با ++C

کد منو را در زیر می بینید:

//menu
void menu()
{
	char ch;
	int inttemp;
	node *temp = new node();
	bst myTree;
	int select;
	do
	{
		system("CLS");
		cout << "0. Exit" << endl;
		cout << "1. Insert"<<endl;
		cout << "2. Display" << endl;
		cout << "3. Minimum" << endl;
		cout << "4. Maximum" << endl;
		cout << "5. Search" << endl;
		cout << "6. Inorder walk(sort)" << endl;
		cout << "7. Successor" << endl;
		cout << "8. Predecessor" << endl;
		cout << "9. Delete" << endl;
		cout << endl << "Enter your selection:" << endl;
		cin >> select;
		system("CLS");

		switch (select)
		{
		case 0:
		{
				  break;
		}
		case 1:
		{
				  do
				  {
					  int data;
					  cout << "Enter Data: ";
					  cin >> data;
					  myTree.insert(data);
					  cout << endl << "Do you want another node?[y/n]" << endl;
					  cin >> ch;
				  } 
				  while (ch != 'n');
				  break;
		}
		case 2:
		{
				  myTree.display(myTree.root, 0);
				  cout << endl << "Press 0 to continue!" << endl;
				  cin >> ch;
				  break;
		}
		case 3:
		{
				  temp = myTree.minimum();
				  if (temp != NULL)
				  {
					  cout << "Minimum:" << temp->data << endl;
				  }
				  else
				  {
					  cout << "Tree is empty!" << endl;
				  }
				  cout << endl << "Press 0 to continue!" << endl;
				  cin >> ch;
				  break;
		}
		case 4:
		{
				  temp = myTree.maximum();
				  if (temp != NULL)
				  {
					  cout << "Maximum:" << temp->data << endl;
				  }
				  else
				  {
					  cout << "Tree is empty!" << endl;
				  }
				  cout << endl << "Press 0 to continue!" << endl;
				  cin >> ch;
				  break;
		}
		case 5:
		{

				  cout << "Enter key of node:";
				  cin >> inttemp;
				  temp = myTree.search(inttemp);
				  if (temp != NULL)
				  {
					  cout << "Node with key (" << temp->data << ") exist in tree." << endl;
				  }
				  else
				  {
					  cout << "It isn't in tree!"<< endl;
				  }
				  
				  cout << endl << "Press 0 to continue!" << endl;
				  cin >> ch;
				  break;
		}
		case 6:
		{
				  cout << "Sorted order:" << endl;
				  myTree.inorder_tree_walk(myTree.root);		  
				  cout << endl << "Press 0 to continue!" << endl;
				  cin >> ch;
				  break;
		}
		case 7:
		{
				  cout << "Enter key of node , for finding it's successor: ";
				  cin >> inttemp;
				  temp = myTree.search(inttemp);
				  if (temp == NULL)
				  {
					  cout << "Node with key (" << inttemp << ") isn't in tree." << endl;
				  }
				  else
				  {
					  temp = myTree.successor(temp);
					  if (temp == NULL)
					  {
						  cout << "It hasn't successor" << endl;
					  }
					  else
					  {
						  cout << "Successor: " << temp->data << endl;
					  }
				  }
				  cout << endl << "Press 0 to continue!" << endl;
				  cin >> ch;
				  break;
		}
		case 8:
		{
				  cout << "Enter key of node , for finding it's predecessor: ";
				  cin >> inttemp;
				  temp = myTree.search(inttemp);
				  if (temp == NULL)
				  {
					  cout << "Node with key (" << inttemp << ") isn't in tree." << endl;
				  }
				  else
				  {
					  temp = myTree.predecessor(temp);
					  if (temp == NULL)
					  {
						  cout << "It hasn't predecessor" << endl;
					  }
					  else
					  {
						  cout << "Predecessor: " << temp->data << endl;
					  }
				  }
				  cout << endl << "Press 0 to continue!" << endl;
				  cin >> ch;
				  break;
		}
		case 9:
		{
				  cout << "Enter key(Data) of node that you want delete: ";
				  cin >> inttemp;
				  temp = myTree.search(inttemp);
				  if (temp == NULL)
				  {
					  cout << "Node with key (" << inttemp << ") isn't in tree." << endl;
				  }
				  else
				  {
					  myTree.deletion(temp);
					  cout << "Node with key (" << inttemp << ") removed from tree." << endl;
				  }
				  cout << endl << "Press 0 to continue!" << endl;
				  cin >> ch;
				  break;
		}
		default:
			break;
		}

	} while (select != 0);
}

 

و در آخر هم کد کلی درخت جست و جوی دو دویی (Binary search tree – BST ) را می بینید همراه main  برنامه :

 

// Binary Search Tree.cpp 
//www.open-mind.ir
//Farhad Dalirani
#include "stdafx.h"
#include <iostream>
#include <iomanip>

using namespace std;

//tree node
//------------------------------------------
class node
{
public:
	int data;
	node* parent;
	node* leftChild;
	node* rightChild;
	node(void);
};

node::node(void)
{
	data = 0;
	parent = NULL;
	leftChild = NULL;
	rightChild = NULL;
}
//------------------------------------------
//binary search tree
class bst
{
public:
	node* root;
	
	bst(void);
	void insert(int);
	void display(node*, int);
	node* minimum();
	node* maximum();
	node* search(int);
	void inorder_tree_walk(node*);
	node* successor(node*);
	node* predecessor(node *);
	void transplant(node*, node*);
	void deletion(node *);
};

bst::bst(void)
{
	root = NULL;
}

void bst::insert(int d)
{
	node* newNode = new node();
	newNode->data = d;

	if (root == NULL)
	{
		root = newNode;
	}
	else
	{
		node* tempNode = new node();
		node* backTempNode = new node();
		tempNode = root;

		while (tempNode != NULL)
		{
			backTempNode = tempNode;
			if (tempNode->data <= newNode->data)
			{
				tempNode = tempNode->rightChild;
			}
			else
			{
				tempNode = tempNode->leftChild;
			}
		}

		newNode->parent = backTempNode;
		if (backTempNode->data <= newNode->data)
		{
			backTempNode->rightChild = newNode;
		}
		else
		{
			backTempNode->leftChild = newNode;
		}
	}
}
//display binary search tree
void bst::display(node *Node,int level)
{
	if (root == NULL)
	{
		cout << "Tree is empty." << endl;
	}
	else
	{
		if (Node->rightChild != NULL)
		{
			display(Node->rightChild, level + 1);
		}
		
		if (Node != root)
		{
			for (int i = 0; i < level + 1; i++)
			{
				cout << "      ";
			}
		}
		else
		{
			cout << "Root->";
		}

		cout << Node->data << endl;

		if (Node->leftChild != NULL)
		{
			display(Node->leftChild, level + 1);
		}
	}

}
//return minimum node
node* bst::minimum()
{
	node* tempNode = new node();
	node* backTempNode = new node();
	backTempNode = tempNode = root;
	while (tempNode != NULL)
	{
		backTempNode = tempNode;
		tempNode = tempNode->leftChild;
	}
	return backTempNode;
}
//www.open-mind.ir
//return maximum node
node* bst::maximum()
{
	node* tempNode = new node();
	node* backTempNode = new node();
	backTempNode = tempNode = root;
	while (tempNode != NULL)
	{
		backTempNode = tempNode;
		tempNode = tempNode->rightChild;
	}
	return backTempNode;
}
//Search in BST Tree
node* bst::search(int Data)
{
	node* tempNode = new node();
	tempNode = root;
	while (tempNode != NULL)
	{
		if (tempNode->data == Data)
		{
			return tempNode;
		}
		else
		{
			if (tempNode->data <= Data)
			{
				tempNode = tempNode->rightChild;
			}
			else
			{
				tempNode = tempNode->leftChild;
			}
		}
	}
	return NULL;
}
//inoreder tree walk = show all node in sorted mood
void bst::inorder_tree_walk(node* currentNode)
{
	if (root != NULL)
	{
		if (currentNode->leftChild != NULL)
		{
			inorder_tree_walk(currentNode->leftChild);
		}

		cout << currentNode->data << "  ,";

		if (currentNode->rightChild != NULL)
		{
			inorder_tree_walk(currentNode->rightChild);
		} 
	}
	else
	{
		cout << "Tree is empty!" << endl;
	}
}
//successor
node* bst::successor(node* currentNode)
{
	node* tempNode = new node();
	node* backTempNode = new node();
	tempNode = currentNode;

	if (tempNode->rightChild != NULL)
	{
		tempNode = tempNode->rightChild;
		while (tempNode != NULL)
		{
			backTempNode = tempNode;
			tempNode = tempNode->leftChild;
		}
		return backTempNode;
	}
	else
	{
		backTempNode = tempNode;
		tempNode = tempNode->parent;
		while (tempNode != NULL && tempNode->rightChild == backTempNode)
		{
			backTempNode = tempNode;
			tempNode = tempNode->parent;
		}
		return tempNode;
	}
}

//predecessor
node* bst::predecessor(node* currentNode)
{
	node* tempNode = new node();
	node* backTempNode = new node();
	tempNode = currentNode;

	if (tempNode->leftChild != NULL)
	{
		tempNode = tempNode->leftChild;
		while (tempNode != NULL)
		{
			backTempNode = tempNode;
			tempNode = tempNode->rightChild;
		}
		return backTempNode;
	}
	else
	{
		backTempNode = tempNode;
		tempNode = tempNode->parent;
		while (tempNode != NULL && tempNode->leftChild == backTempNode)
		{
			backTempNode = tempNode;
			tempNode = tempNode->parent;
		}
		return tempNode;
	}
}
//transplant
void bst::transplant(node* u, node* v)
{
	if (u->parent == NULL)
	{
		root = v;
	}
	else
	{
		if (u == u->parent->leftChild)
		{
			u->parent->leftChild = v;
		}
		else
		{
			u->parent->rightChild = v;
		}
	}
	if (v != NULL)
	{
		v->parent = u->parent;
	}
}
//remove node from tree
void bst::deletion(node *z)
{
	if (z->leftChild == NULL)
	{
		transplant(z, z->rightChild);
	}
	else
	{
		if (z->rightChild == NULL)
		{
			transplant(z, z->leftChild);
		}
		else
		{
			node* succesor = new node();
			succesor = successor(z);
			if (succesor->parent != z)
			{
				transplant(succesor, succesor->rightChild);
				succesor->rightChild = z->rightChild;
				succesor->rightChild->parent = succesor;
			}
			transplant(z, succesor);
			succesor->leftChild = z->leftChild;
			succesor->leftChild->parent = succesor;
		}
	}
	delete z;
}
//------------------------------------------
//menu
void menu()
{
	char ch;
	int inttemp;
	node *temp = new node();
	bst myTree;
	int select;
	do
	{
		system("CLS");
		cout << "0. Exit" << endl;
		cout << "1. Insert"<<endl;
		cout << "2. Display" << endl;
		cout << "3. Minimum" << endl;
		cout << "4. Maximum" << endl;
		cout << "5. Search" << endl;
		cout << "6. Inorder walk(sort)" << endl;
		cout << "7. Successor" << endl;
		cout << "8. Predecessor" << endl;
		cout << "9. Delete" << endl;
		cout << endl << "Enter your selection:" << endl;
		cin >> select;
		system("CLS");

		switch (select)
		{
		case 0:
		{
				  break;
		}
		case 1:
		{
				  do
				  {
					  int data;
					  cout << "Enter Data: ";
					  cin >> data;
					  myTree.insert(data);
					  cout << endl << "Do you want another node?[y/n]" << endl;
					  cin >> ch;
				  } 
				  while (ch != 'n');
				  break;
		}
		case 2:
		{
				  myTree.display(myTree.root, 0);
				  cout << endl << "Press 0 to continue!" << endl;
				  cin >> ch;
				  break;
		}
		case 3:
		{
				  temp = myTree.minimum();
				  if (temp != NULL)
				  {
					  cout << "Minimum:" << temp->data << endl;
				  }
				  else
				  {
					  cout << "Tree is empty!" << endl;
				  }
				  cout << endl << "Press 0 to continue!" << endl;
				  cin >> ch;
				  break;
		}
		case 4:
		{
				  temp = myTree.maximum();
				  if (temp != NULL)
				  {
					  cout << "Maximum:" << temp->data << endl;
				  }
				  else
				  {
					  cout << "Tree is empty!" << endl;
				  }
				  cout << endl << "Press 0 to continue!" << endl;
				  cin >> ch;
				  break;
		}
		case 5:
		{

				  cout << "Enter key of node:";
				  cin >> inttemp;
				  temp = myTree.search(inttemp);
				  if (temp != NULL)
				  {
					  cout << "Node with key (" << temp->data << ") exist in tree." << endl;
				  }
				  else
				  {
					  cout << "It isn't in tree!"<< endl;
				  }
				  
				  cout << endl << "Press 0 to continue!" << endl;
				  cin >> ch;
				  break;
		}
		case 6:
		{
				  cout << "Sorted order:" << endl;
				  myTree.inorder_tree_walk(myTree.root);		  
				  cout << endl << "Press 0 to continue!" << endl;
				  cin >> ch;
				  break;
		}
		case 7:
		{
				  cout << "Enter key of node , for finding it's successor: ";
				  cin >> inttemp;
				  temp = myTree.search(inttemp);
				  if (temp == NULL)
				  {
					  cout << "Node with key (" << inttemp << ") isn't in tree." << endl;
				  }
				  else
				  {
					  temp = myTree.successor(temp);
					  if (temp == NULL)
					  {
						  cout << "It hasn't successor" << endl;
					  }
					  else
					  {
						  cout << "Successor: " << temp->data << endl;
					  }
				  }
				  cout << endl << "Press 0 to continue!" << endl;
				  cin >> ch;
				  break;
		}
		case 8:
		{
				  cout << "Enter key of node , for finding it's predecessor: ";
				  cin >> inttemp;
				  temp = myTree.search(inttemp);
				  if (temp == NULL)
				  {
					  cout << "Node with key (" << inttemp << ") isn't in tree." << endl;
				  }
				  else
				  {
					  temp = myTree.predecessor(temp);
					  if (temp == NULL)
					  {
						  cout << "It hasn't predecessor" << endl;
					  }
					  else
					  {
						  cout << "Predecessor: " << temp->data << endl;
					  }
				  }
				  cout << endl << "Press 0 to continue!" << endl;
				  cin >> ch;
				  break;
		}
		case 9:
		{
				  cout << "Enter key(Data) of node that you want delete: ";
				  cin >> inttemp;
				  temp = myTree.search(inttemp);
				  if (temp == NULL)
				  {
					  cout << "Node with key (" << inttemp << ") isn't in tree." << endl;
				  }
				  else
				  {
					  myTree.deletion(temp);
					  cout << "Node with key (" << inttemp << ") removed from tree." << endl;
				  }
				  cout << endl << "Press 0 to continue!" << endl;
				  cin >> ch;
				  break;
		}
		default:
			break;
		}

	} while (select != 0);
}
//------------------------------------------
int main( )
{
	menu();
	return 0;
}

digg کد و الگوریتم درخت جست و جوی دودویی Binary search tree با ++C  reddit کد و الگوریتم درخت جست و جوی دودویی Binary search tree با ++C  stumbleupon کد و الگوریتم درخت جست و جوی دودویی Binary search tree با ++C  yahoo buzz کد و الگوریتم درخت جست و جوی دودویی Binary search tree با ++C  dzone کد و الگوریتم درخت جست و جوی دودویی Binary search tree با ++C  facebook کد و الگوریتم درخت جست و جوی دودویی Binary search tree با ++C  delicious کد و الگوریتم درخت جست و جوی دودویی Binary search tree با ++C  dotnetkicks کد و الگوریتم درخت جست و جوی دودویی Binary search tree با ++C  dotnetshoutout کد و الگوریتم درخت جست و جوی دودویی Binary search tree با ++C  linkedin کد و الگوریتم درخت جست و جوی دودویی Binary search tree با ++C  technorati کد و الگوریتم درخت جست و جوی دودویی Binary search tree با ++C  twitter کد و الگوریتم درخت جست و جوی دودویی Binary search tree با ++C  google buzz کد و الگوریتم درخت جست و جوی دودویی Binary search tree با ++C  



برچسب ها : , , , ,

به سیاره لینوکس امتیاز دهید

به اين صفحه امتياز دهيد