bitree.cpp

实现二叉排序树查找实现二叉排序树查找实现二叉排序树查找

#include<iostream>
using namespace std;

struct Bitree 
{ 
	int data; 
	Bitree *lchild;
	Bitree *rchild; 
}; 

void createBitree( int tp, Bitree *hd )
{
	int t;
	Bitree *h;
	t = tp;
	h = new Bitree;
	h = hd;

	if( t >= h->data )  
	{
		if( h->rchild == NULL )
		{
			h->rchild = new Bitree;
			h->rchild->data = t;
			h->rchild->lchild = NULL;
			h->rchild->rchild = NULL;
		}
		else
		{
			h = h->rchild;
			createBitree( t, h );
		}
	}
	else if( t < h->data )
	{	
		if( h->lchild == NULL )
		{
			h->lchild = new Bitree;
			h->lchild->data = t;
			h->lchild->lchild = NULL;
			h->lchild->rchild = NULL;
		}
		else
		{
			h = h->lchild;
			createBitree( tp, h );
		}
	}
}


void level( int keyWord, Bitree *root )
{ 
	int k = 1;//树的根节点所在层次 

	while( root ) 
	{ 
		if( keyWord < root->data ) 
		{ 
			root = root->lchild;//左子树中寻找 
			k++; 
		} 
		else if( keyWord > root->data ) 
		{ 
			root = root->rchild;//右子树中寻找 
			k++; 
		} 
		else
		{
			cout<<"您查找的结点位于该二叉排序树的第 "<<k<<"层 ！"<<endl;//找到后返回层次
			return;
		}
	}

	cout<<"您要查找的结点在该二叉排除树中不存在 ！"<<endl; 
}

int main()
{	
	int temp;
	int key;
	Bitree *r;
	Bitree *head;
	head = new Bitree;
	
                          
	cout<<"请您输入二叉排序树序列（0标志结束） ： ";
	cin >>temp;

	head->data = temp;
	head->lchild = NULL;
	head->rchild = NULL;

	while(1)
	{
		cin>>temp;

		if ( temp == 0 ) break;
		else createBitree( temp, head );
	}

	cout<<"请您输入要求层次的结点的值 ： ";
	cin>>key;
	r = head;
	level( key, r );
	return 0;
}