C++完成二叉树的创建及其它基本操作


#include
#include
#include 
using namespace std;

typedef struct
    {   int    num;      	//学号
        char    name[10];   //姓名
    } student;

//预声明 
template	class StackNode;
template	class ChainStack;
template	class QueueNode;
template	class ChainQueue;
template	class BinaryTreeNode;
template	class BinaryTree;




template							//堆栈结点类 
class StackNode
{	public:
		ElementType data;
		StackNode *link=NULL;
};

template							//堆栈类 
class ChainStack
{	private:
		StackNode *top; 
	public:
		ChainStack()
		{	top=NULL;
		}
		~ChainStack();
		bool IsEmpty()
		{	return top==NULL;
		}
		bool push(ElementType &newvalue);			//进栈 
		bool pop(ElementType &result);				//出栈 
};

//析构函数 
template
ChainStack::~ChainStack()
{	StackNode *n;
	while(top)
	{	n=top->link;
		delete top;
		top=n;
	}
}

//进栈运算
template
bool ChainStack::push(ElementType &newvalue)
{	StackNode *p=new StackNode;
	if(!p)
	{	cout<<"生成新的栈结点失败！"<<'n';
		return false;
	}
	p->data=newvalue;
	p->link=top;
	top=p;
	return true;
}

//出栈运算
template
bool ChainStack::pop(ElementType &result)
{	if(IsEmpty())
	{	cout<<"栈为空！"<<'n';
		return false; 
	}
	result=top->data;
	StackNode *p=top;
	top=top->link;
	delete p;
	return true;	
} 




template
class QueueNode										//队列结点类 
{	public:
		ElementType data;
		QueueNode *link=NULL;
};

template
class ChainQueue
{	public:
		QueueNode *front;
		QueueNode *rear;
	
	public:
		ChainQueue()
		{	front=NULL;
			rear=NULL;	
		} 
		~ChainQueue();
		bool IsEmpty()
		{	return front==NULL;
		}
		bool EnQueue(ElementType &newvalue);		//进队 
		bool DeQueue(ElementType &result);			//出队
		void Display();	
	friend class BinaryTreeNode;
	friend class BinaryTree;
};

//析构函数 
template
ChainQueue::~ChainQueue()
{	while(!IsEmpty())
	{	QueueNode *p=front;
		front=front->link;
		delete p;
	}	
}

//进队运算
template
bool ChainQueue::EnQueue(ElementType &newvalue)
{	QueueNode *p=new QueueNode;
	p->data=newvalue;
	p->link=NULL;
	if(IsEmpty())
	{	front=p;
		rear=p;
	}
	else
	{	rear->link=p;
		rear=p;
	}	
	return true;
}

//出队运算
template
bool ChainQueue::DeQueue(ElementType &result)
{	if(IsEmpty())
	{	cout<<"队列为空！"<<'n';
		return false;	
	}
	result=front->data;
	if(front==rear)
	{	delete front;
		front=NULL;
		rear=NULL;
		return true;
	}
	QueueNode *p=front;
	front=front->link;
	delete p;
	return true;
}





template							 
class BinaryTreeNode								//二叉树结点类 
{	public:
		ElementType data;
		BinaryTreeNode *LChild;
		BinaryTreeNode *RChild;
	public:
		BinaryTreeNode()
		{	LChild=NULL;
			RChild=NULL; 
		} 
		BinaryTreeNode(ElementType &newvalue)
		{	data=newvalue;
			LChild=NULL;
			RChild=NULL; 
		} 
		
	friend class BinaryTree;
};

template							//二叉树类 
class BinaryTree
{	public:
		BinaryTreeNode *btroot;
	public:
		BinaryTree()
		{	btroot=NULL;
		}
		~BinaryTree()
		{
		}
		bool IsEmpty()
		{	return btroot==NULL;
		};
		BinaryTreeNode* MakeNode();
		bool CreatBinaryTree(BinaryTreeNode *root,BinaryTreeNode *left,BinaryTreeNode *right);
		bool DeleteBinaryTree(BinaryTreeNode *btroot);
		void PreOrderRecursive(BinaryTreeNode *btroot,ChainQueue *q);
		void InOrderRecursive(BinaryTreeNode *btroot,ChainQueue *q);
		void PostOrderRecursive(BinaryTreeNode *btroot,ChainQueue *q); 
		void LevelOrder_U_L(BinaryTreeNode *btroot,ChainQueue *q); 
		void LevelOrder_U_R(BinaryTreeNode *btroot,ChainQueue *q); 
		void LevelOrder_D_L(BinaryTreeNode *btroot,ChainStack *q); 
		BinaryTreeNode * Delete(BinaryTreeNode *btroot);
		
	friend class BinaryTreeNode;

	
};


//创建二叉树结点 
template							
BinaryTreeNode* BinaryTree::MakeNode()
{	BinaryTreeNode *p;
	int num;
	char name[10];
	cout<<"请输入学生学号："<<'n';
	cin>>num;
	cout<<"请输入学生姓名："<<'n';
	cin>>name;
	ElementType s;
	s.num=num;
	strcpy(s.name,name);
	p=new BinaryTreeNode(s);
	if(!p)
	{	cout<<"创建结点失败！"<<'n';
		return NULL;
	}
	return p;
}

//创建二叉树		
template 
bool BinaryTree::CreatBinaryTree(BinaryTreeNode *p,BinaryTreeNode *lchild,BinaryTreeNode *rchild)
{	p->LChild=lchild;
	p->RChild=rchild;
}


 
//以下遍历的结果都先暂时存放在q队列中。main函数先把q队列的地址传过来，遍历结束后再让main函数遍历q队列，最后由main函数输出结果。(不足：遍历前没判断树是否为空。） 


//前序遍历二叉树
template 
void BinaryTree::PreOrderRecursive(BinaryTreeNode *btroot,ChainQueue *q)
{	BinaryTreeNode *p=btroot;
	ChainStack*> s;
	BinaryTreeNode *result;
	while(p||!s.IsEmpty())
	{	if(p)
		{	q->EnQueue(p->data);
			s.push(p);
			p=p->LChild;
		}	
		else
		{	s.pop(result);
			p=result->RChild;
		}
	}
}

//中序遍历二叉树 
template 
void BinaryTree::InOrderRecursive(BinaryTreeNode *btroot,ChainQueue *q)
{	BinaryTreeNode *p=btroot;
	ChainStack*> s;
	BinaryTreeNode *result;
	while(p||!s.IsEmpty())
	{	if(p)
		{	s.push(p);
			p=p->LChild;
		}	
		else
		{	s.pop(p);
			q->EnQueue(p->data);
			p=p->RChild;
		}
	}
}

//后序遍历二叉树 (注：后序遍历需要部分结点进栈两次。我的方法是：让结点两次进入不同的栈，第一次进入s，第二次进入m。） 
template 
void BinaryTree::PostOrderRecursive(BinaryTreeNode *btroot,ChainQueue *q)
{	BinaryTreeNode *p=btroot;
	ChainStack*> s,m;
	BinaryTreeNode *result;
	while(p||!s.IsEmpty())
	{	if(p)
		{	s.push(p);
			p=p->LChild;
		}	
		else
		{	s.pop(p);
			if(!(p->RChild))
			{	
				q->EnQueue(p->data);
				p=NULL;
			}
			else
			{	if(!m.IsEmpty()&&m.pop(result)&&p==result)		//判断是否已进栈两次 
				{	q->EnQueue(p->data);
					p=NULL;
					result=NULL;			
				}
				else
				{	if(result!=NULL)		//判断result是否因为上面的if而退过栈。如果因为要判断p==result而让result退栈了，那现在重新把result塞回去 
					{	m.push(result);
						s.push(p);
					}
					m.push(p);
					p=p->RChild;
				}				
			}
		}
	}
}

//从上至下从左到右遍历二叉树
template 
void BinaryTree::LevelOrder_U_L(BinaryTreeNode *btroot,ChainQueue *q)
{	BinaryTreeNode *p=btroot;
	ChainQueue*> l;
	l.EnQueue(p);
	while(!l.IsEmpty())
	{	l.DeQueue(p);
		q->EnQueue(p->data);
		if(p->LChild)
		{	l.EnQueue(p->LChild);
		}
		if(p->RChild)
		{	l.EnQueue(p->RChild);
		}
	}
}

//从上至下从右到左遍历二叉树
template 
void BinaryTree::LevelOrder_U_R(BinaryTreeNode *btroot,ChainQueue *q)
{	BinaryTreeNode *p=btroot;
	ChainQueue*> l;
	l.EnQueue(p);
	while(!l.IsEmpty())
	{	l.DeQueue(p);
		q->EnQueue(p->data);
		if(p->RChild)
		{	l.EnQueue(p->RChild);
		}
		if(p->LChild)
		{	l.EnQueue(p->LChild);
		}
	}
}

//从下至上从左到右遍历二叉树（注：这次遍历没有把结果放在q队列里，而是放在了q栈里。） 
template 
void BinaryTree::LevelOrder_D_L(BinaryTreeNode *btroot,ChainStack *q)
{	BinaryTreeNode *p=btroot;
	ChainQueue*> l;
	l.EnQueue(p);
	while(!l.IsEmpty())
	{	l.DeQueue(p);
		q->push(p->data);
		if(p->RChild)
		{	l.EnQueue(p->RChild);
		}
		if(p->LChild)
		{	l.EnQueue(p->LChild);
		}
	}
}


//删除二叉树（注：利用递归） 
template 
BinaryTreeNode * BinaryTree::Delete(BinaryTreeNode *btroot)
{	if(btroot)
	{	Delete(btroot->LChild);
		Delete(btroot->RChild);
		delete btroot;		
	}	
	btroot=NULL;
	return btroot;
}


int main()
{	BinaryTree t;
	cout << "*******************************操作选择*******************************" <<'n';
	cout << "1.生成二叉树" <<'n';
	cout << "2.前序遍历二叉树" <<'n';
	cout << "3.中序遍历二叉树" <<'n';
	cout << "4.后序遍历二叉树" <<'n';
	cout << "5.从上至下从左到右遍历二叉树" <<'n';
	cout << "6.从上至下从右到左遍历二叉树" <<'n';
	cout << "7.从下至上从左到右遍历二叉树" <<'n';
	cout << "8.删除二叉树" <<'n';
	cout << "**********************************************************************" <<'n';
	while(1)
	{	int o;
		cout<<"请输入操作数："<<'n';
		cin>>o;
		if(o>9||o<1)
		{	cout<<"输入有误！请重新输入"<<'n';
			continue; 
		}
		
		switch(o)
		{	case 1:
			{	int count=1;
				BinaryTreeNode *root,*l,*r;
				
				//第一棵树 
				cout<<"请输入第"< q;
				t.PreOrderRecursive(t.btroot,&q);
				student s;	
				for(int i=1;i<=7;i++)
				{	q.DeQueue(s);
					cout<<"姓名："< q;
				t.InOrderRecursive(t.btroot,&q);
				student s;	
				for(int i=1;i<=7;i++)
				{	q.DeQueue(s);
					cout<<"姓名："< q;
				t.PostOrderRecursive(t.btroot,&q);
				student s;	
				for(int i=1;i<=7;i++)
				{	q.DeQueue(s);
					cout<<"姓名："< q;
				t.LevelOrder_U_L(t.btroot,&q);
				student s;	
				for(int i=1;i<=7;i++)
				{	q.DeQueue(s);
					cout<<"姓名："< q;
				t.LevelOrder_U_R(t.btroot,&q);
				student s;	
				for(int i=1;i<=7;i++)
				{	q.DeQueue(s);
					cout<<"姓名："< q;
				t.LevelOrder_D_L(t.btroot,&q);
				student s;	
				for(int i=1;i<=7;i++)
				{	q.pop(s);
					cout<<"姓名："< 
二叉树示意图： 
 
 
运行结果： 
 
 
 
 
感想： 
①把遍历结果放在队列里面，再把队列的地址传给main函数，让main函数完成输出。自己实现这个过程非常困难。因为老师完全没教过。我在这个过程遇到的bug相当多。其实按照老师的教学水平，我直接在遍历的时候完成输出，就已经很难了。但是我还是想试一试，因为这个想法很好。花了很多时间，最终胜利了，我的想法也落地了。 
②和上次的双向链表比起来，这次我代码的书写规范了很多，希望下次再接再厉。 
（感觉有点像小学生写日记啊……）
C++完成二叉树的创建及其它基本操作

C/C++/C#相关栏目本月热门文章
