threadbinarytreefindnextandfindprev.cpp

创建一棵二叉树

#include<iostream>
#include<queue>
using namespace std;
#define NULL 0



////////////////////////////////////////
//二叉树的结点类
class ThreadBinaryTreeNode{
	friend class ThreadBinaryTree;
private:
	char element;
	ThreadBinaryTreeNode *left;
	ThreadBinaryTreeNode *right;
	int lTag,rTag;
public:
	ThreadBinaryTreeNode()
	{lTag=rTag=0;left=NULL;right=NULL;}

	
	ThreadBinaryTreeNode(const char &ele,ThreadBinaryTreeNode * l=NULL,ThreadBinaryTreeNode *r=NULL)
	{
		element=ele;
		left=l;
		right=r;
		lTag=rTag=0;
	}
	ThreadBinaryTreeNode *leftchild()const
	{return left;}
	ThreadBinaryTreeNode *rightchild()const
	{return right;}


	char value() const;
};


///////////////////////////////////////////////////////////
//二叉树类的定义
class ThreadBinaryTree{
private:
	ThreadBinaryTreeNode * root;
	ThreadBinaryTreeNode *pre;
//	ThreadBinaryTreeNode *GetParent(ThreadBinaryTreeNode *root,ThreadBinaryTreeNode *current);
public:
////////
/////构造函数
	ThreadBinaryTree()
	{
		root=NULL;
		pre=new ThreadBinaryTreeNode;
	}
	ThreadBinaryTree(char x,ThreadBinaryTreeNode *l=NULL,ThreadBinaryTreeNode *r=NULL)
	{
		root=new ThreadBinaryTreeNode(x,l,r);
		pre=new ThreadBinaryTreeNode;
	}
////////////////////	

	void DeleteBinaryTree(ThreadBinaryTreeNode *root);
/////////////////////////
	~ThreadBinaryTree()
	{DeleteBinaryTree(root);}
//////////////////////////析构函数
	ThreadBinaryTreeNode * Root(){return root;}//取根结点的值
	ThreadBinaryTreeNode * &Pre(){return pre;}//取遍历开始的结点
	ThreadBinaryTreeNode * GetPre(){return pre;}
	void GetPreval(){ cout<<"the value of the pre:"<<pre->element<<endl;}
	ThreadBinaryTreeNode ** Root1(){return &root;}//取根结点的地址值，主要是为建立树的时候使用
	void CreateTree(const char & elem,ThreadBinaryTree &leftTree,ThreadBinaryTree & rightTree);
	bool isEmpty()const;

	void BuildTree(ThreadBinaryTreeNode **root);


///////中序遍历
	void InOrder(ThreadBinaryTreeNode *root)const;
	

////////////////线索化二叉树

	void InThread(ThreadBinaryTreeNode * root,ThreadBinaryTreeNode * &pre);

////////////////////寻找当前结点的后继结点
	ThreadBinaryTreeNode * FindNext(ThreadBinaryTreeNode * pointer);


//////////////////寻找当前结点的前驱结点
	ThreadBinaryTreeNode * FindPrev(ThreadBinaryTreeNode *pointer);



};
///////////////////////////////////////
///判断是否为空树
bool ThreadBinaryTree::isEmpty()const
{
	return((root)?true:false);
}
///////////////////////////

///////
////////////////////////////////////////////////
/////


/////////////////////////////////////////////
//删除树
void ThreadBinaryTree::DeleteBinaryTree(ThreadBinaryTreeNode *root)
{
//	if(root)
//	{
//		DeleteBinaryTree(root->left);
//		DeleteBinaryTree(root->right);
//		delete root;
//	}
}

////////////////////////////////
//创建一棵二叉树
void ThreadBinaryTree::BuildTree(ThreadBinaryTreeNode * *current)
{//采用前序遍历的方法建立一棵树，传递的参数为一个指向结点的指针的指针，目的是为了解决传值的问题
	//输入@符号的时候，表示一棵子树结束


	ThreadBinaryTreeNode *current1;
	char ch;
	cout<<"Please input the element:";
	cin>>ch;
	if(ch=='@')
       *current=NULL;//current=NULL;
	else{
		current1=new ThreadBinaryTreeNode(ch);
		if(root==NULL)
			root=current1;
			* current=current1;
		BuildTree(&((*current)->left));
		BuildTree(&((*current)->right));
	}
}




////////////////////////////////////////////
//线索化二叉树
void ThreadBinaryTree::InThread(ThreadBinaryTreeNode * root,ThreadBinaryTreeNode * &pp)
{
	if(root!=NULL)
	{
		InThread(root->leftchild(),pp);
		if(root->leftchild()==NULL)
		{
			root->left=pp;
			root->lTag=1;
		}
		if((pp)&&(pp->rightchild()==NULL))
		{
			pp->right=root;
			pp->rTag=1;
		}
		pp=root;
		InThread(root->rightchild(),pp);
	}
		
			
}

//////////////////////////////

/////////中序遍历

void ThreadBinaryTree::InOrder(ThreadBinaryTreeNode * current) const
{
	ThreadBinaryTreeNode *pointer;
	if(root==NULL)
		return;
	else pointer=root;
	while(pointer->leftchild()->leftchild()!=NULL)
		pointer=pointer->leftchild();
//	pointer=pointer->rightchild();
//	cout<<"view the value of the pointer:"<<endl;
	while(1)
	{
		cout<<pointer->element<<" ";
		if(pointer->rightchild()==NULL)
			return;
		if(pointer->rTag==1)
			pointer=pointer->rightchild();
		else
		{
			pointer=pointer->rightchild();
			while(pointer->lTag==0)
				pointer=pointer->leftchild();
		}
	}
}

///////////////////////////
////////////////////寻找当前结点的后继结点
ThreadBinaryTreeNode * ThreadBinaryTree::FindNext(ThreadBinaryTreeNode * pointer)
{
	ThreadBinaryTreeNode * temppointer=NULL;
	if(pointer->lTag==1)
	{
		cout<<pointer->rightchild()->element;
		return pointer->rightchild();
	}
	else
		temppointer=pointer->rightchild();
	if(temppointer->lTag==0){
		while(temppointer->lTag==0)
			temppointer=temppointer->leftchild();
//		temppointer=temppointer->leftchild();
	}
	cout<<temppointer->element<<endl;
	return temppointer;


}
//////////////////////////////
///////////////////////
//////////////////寻找当前结点的前驱结点
ThreadBinaryTreeNode * ThreadBinaryTree::FindPrev(ThreadBinaryTreeNode * pointer)
{
	ThreadBinaryTreeNode * temppointer;
	if(pointer->lTag==1)
	{
		cout<<pointer->leftchild()->element;
		return pointer->leftchild();
	}
	else
		temppointer=pointer->leftchild();
	if(temppointer->rTag==0){
		while(temppointer->rTag==0)
			temppointer=temppointer->rightchild();
//		temppointer=temppointer->rightchild();
	}
	cout<<temppointer->element<<endl;
	return temppointer;
}

/////////////////////
/////////////////////

void main()
{
	ThreadBinaryTree BT;

	BT.BuildTree(BT.Root1());
	BT.InThread(BT.Root(),BT.Pre());

//	cout<<"线索化完毕"<<endl;
//	cout<<endl<<"中序访问"<<endl;
//	BT.InOrder(BT.Root());
//	BT.GetPreval();
	BT.FindNext((BT.GetPre())->leftchild()->leftchild()->leftchild());
//	BT.GetPreval();
	BT.FindPrev((BT.GetPre())->leftchild());




}