bittree.cpp

有关二叉树数据结构的C++程序

#include <iostream>
#include <cctype>

#include "bitTree.h"


int main(void)
{
	using namespace std;

	char choice,oldnodename,newnodename;
	int direct;
	cout<<"welcome to use bittree programm!\n";
MENU:
	
	cout<<"please choose:\n"
		  "N(new bittree)\n"
		  "A(add node)\n"
		  "D(delete node)\n"
		  "S(search node)\n"
		  "R(ransack)\n"
		  "P(print)\n"
		  "any other key to quit"<<endl;
    
	cin>>choice;
	switch(choice)
	{
		case 'n':
		case 'N':
			bitTreeCreate();
			break;
		case 'a':
		case 'A':
			if( pBitTreeHead==NULL )
				break;
			else
			{
				cout<<"add a new node :\n"
					<<"please indicate node name at which node you want to add and child direct\n"
					<<"input node name:";
				cin>>oldnodename;
				cout<<"input new node name:";
				cin>>newnodename;
				cout<<"input child direct:left(0) right(1)";
				cin>>direct;
				if( bitTreeAddChild(bitTreeSearch(pBitTreeHead,oldnodename),newnodename,childDirect(direct)) )
				{
					cout<<"add node "<<newnodename<<" to node "
						<<oldnodename<<" successful!\n";
				}
				else
				{
					cout<<"add node failure!\n";
				}
			}
			break;
		case 'd':
		case 'D':
			cout<<"input node name you want to delete"<<endl;
			cin>>oldnodename;
			if( bitTreeDelete(bitTreeSearch(pBitTreeHead,oldnodename)) )
				cout<<"delete successful!\n";
			else
				cout<<"delete failure!\n";
			break;
		case 'r':
		case 'R':
			bitTreePreRansack(pBitTreeHead);
			break;	
		case 'p':
		case 'P':
			bitTreePrint(pBitTreeHead);
			break;
		default:
			exit(1);
			bitTreeDelete(pBitTreeHead);
			break;
	}
	

	
	goto MENU;
	

		
	return 0;
}
///create a bitTree with a node name input by user
void bitTreeCreate(void)
{
	using namespace std;

	if( pBitTreeHead != NULL )
		bitTreeDelete(pBitTreeHead);
	char name;
	cout<<"input bittree header name:";
	while( (!cin.get(name)) || (!isalpha(name)) )
	{
		cout<<"invalid input! input again:";
		cin.get();
	}
	pBitTreeHead=new bitTreeStruct;
	pBitTreeHead->name=name;
	pBitTreeHead->leftChild=NULL;
	pBitTreeHead->rightChild=NULL;
	pBitTreeHead->parent=pBitTreeHead;

	
	

}

///search a node with the node name supplied ,it will adopt mid-order search method
///first search the middle node ,then the left child and last the right.
bitTreeStruct *bitTreeSearch(bitTreeStruct *head,char name)
{
	bitTreeStruct *result=NULL;
	if(head==NULL)
		return NULL;
	else if(head->name == name)
		return head;
	else if(head->leftChild != NULL)
	{
		result=bitTreeSearch(head->leftChild,name);
		if( (result==NULL) && (head->rightChild != NULL) )
		{
			result=bitTreeSearch(head->rightChild,name);
			if(result!=NULL)
				return result;
		}
		return result;
	}
	else 
		return NULL;
}

bool bitTreeDelete(bitTreeStruct *pNode)
{
	childDirect sonDirect;
	
	if(pNode==NULL)
		return false;
	else
	{
		if( pNode->parent->leftChild == pNode)
			sonDirect=LEFT;
		else
			sonDirect=RIGHT;
		
		if( pNode->leftChild != NULL )
		{
			bitTreeDelete(pNode->leftChild);
		}
		if( pNode->rightChild != NULL )
		{
			bitTreeDelete(pNode->rightChild);
		}

		if( sonDirect == LEFT )
			pNode->parent->leftChild=NULL;
		else
			pNode->parent->rightChild=NULL;
		
		if( pNode==pBitTreeHead )
			pBitTreeHead=NULL;
		delete pNode;
		pNode=NULL;
		return true;
	}
}

bool bitTreeAddChild(bitTreeStruct *pNode,char name,childDirect direct)
{	
	bitTreeStruct *pOldLeft,*pOldRight,*pNewNode;
	
	if(pNode==NULL)
	{
		return false;
	}
	if( !isalpha(name) )
	{
		return false;
	}
	switch ( direct )
	{
	    case LEFT:
		{
			if(pNode->leftChild!=NULL)
			{
				pOldLeft=pNode->leftChild;
				pNewNode= new bitTreeStruct;
				pNewNode->name=name;
				pNode->leftChild=pNewNode;
				pNewNode->leftChild=pOldLeft;
				pNewNode->rightChild=NULL;
				pNewNode->parent=pNode;
			}
			else
			{
				pNewNode= new bitTreeStruct;
				pNewNode->name=name;
				pNode->leftChild=pNewNode;
				pNewNode->leftChild=NULL;
				pNewNode->rightChild=NULL;
				pNewNode->parent=pNode;
			}
			break;
		}
		case RIGHT:
		{
			if(pNode->rightChild!=NULL)
			{
				pOldRight=pNode->rightChild;
				pNewNode= new bitTreeStruct;
				pNewNode->name=name;
				pNode->rightChild=pNewNode;
				pNewNode->rightChild=pOldRight;
				pNewNode->leftChild=NULL;
				pNewNode->parent=pNode;
			}
			else
			{
				pNewNode= new bitTreeStruct;
				pNewNode->name=name;
				pNode->rightChild=pNewNode;
				pNewNode->rightChild=NULL;
				pNewNode->leftChild=NULL;
				pNewNode->parent=pNode;
			}
			break;
		}
	}
	return true;
}


void bitTreePrint(bitTreeStruct *pBitTree)
{
	using namespace std;
	
	if( pBitTreeHead == NULL )
		cout<<"bit tree have not created yet!\n";
	else
	{	
		
		if( (pBitTree->leftChild) != NULL )
		{
			cout<<pBitTree->name<<"----L--->"<<(pBitTree->leftChild)->name<<endl;
		    bitTreePrint(pBitTree->leftChild);
		}
		else
			cout<<pBitTree->name<<"----L--->0"<<endl;
		if( (pBitTree->rightChild) != NULL )
		{	
			cout<<pBitTree->name<<"----R--->"<<(pBitTree->rightChild)->name<<endl;
			bitTreePrint(pBitTree->rightChild);
		}
		else
			cout<<pBitTree->name<<"----R--->0"<<endl;
	
		
	}
}


void bitTreePreRansack(bitTreeStruct *pBitTree)
{
    using namespace std;

	if(pBitTree != NULL)
	{
		cout<<pBitTree->name;
		bitTreePreRansack(pBitTree->leftChild);
		bitTreePreRansack(pBitTree->rightChild);
	}

}