bintree.cpp

这是关于二叉树的建立

#include <malloc.h>
#include <iostream.h>
#include <stdlib.h>
#include "BinTree.h"
//二叉树类的构造函数
BinTree::BinTree()
{
	//初始化成员变量
	S = new SeqStack;
	Q = new LinkQueue;
	InitStack(S);
	InitQueue(Q);
}

//二叉树的建立
BinTree * BinTree::Create()
{
	BinTree *p;
	p = new BinTree;
	char ch;
	cout<<"请输入头结点："<<endl;
	cin>>ch;
	if (ch == '#')	//如果开始就输入结束符“#”，直接退出程序
		exit(1);
	else
	{
		p->data = ch;	//接受第一个输入字符为根节点元素
		cout<<"请输入头结点的左孩子节点："<<endl;
		p->Lchild = CreateCir();	//对左子树调用递归程序
		cout<<"请输入头结点的右孩子节点："<<endl;
		p->Rchild = CreateCir();	//对右子树调用递归程序
	}
	return p;	//返回根结点指针
}

//二叉树创建函数用到的递归函数
BinTree * BinTree::CreateCir()
{
	BinTree *pp;
	pp = new BinTree;
	char c;
	cin>>c;
	if (c == '#')
		return(NULL);
	else
	{
		pp->data = c;
		cout<<"请输入"<<c<<"的左孩子节点："<<endl;
		pp->Lchild = CreateCir();
		cout<<"请输入"<<c<<"的右孩子节点："<<endl;
		pp->Rchild = CreateCir();
		return pp;
	}
	
}

//前序遍历由递归算法实现
void BinTree::PreOrder(BinTree *T)
{
	if (T == NULL)
		return;
	else
		cout<<T->data;
	PreOrder(T->Lchild);
	PreOrder(T->Rchild);
}

//后序遍历由非递归算法实现
void    BinTree::PostOrder(BinTree *T)
{
	BinTree *p,*q;
	Push(S,T);	//根节点入栈
	while (!StackEmpty(S))
	{
		while ((p = StackTop(S)) != NULL)	//栈顶元素非空则把栈顶节点的左节点入栈
			Push(S,p->Lchild);
		q = Pop(S);	
		if(StackEmpty(S)) break;
		p = StackTop(S);
		Push(S,q);	//二次入栈
		Push(S,p->Rchild);	
		while (1) {		//栈顶非空时
			p = StackTop(S);
			if (p == NULL) 
			{
				q=Pop(S);
				p = StackTop(S);
				if (p == NULL) 
				{
					q = Pop(S);
					p = Pop(S);
					cout<<p->data;
					Push(S,q);
				}
				else
				{
					Push(S,q);
					break;
				}
			
			}
			else break;
		
		}
	}
}

//层次遍历由队列实现
void BinTree::LayOrder(BinTree *T)
{
	BinTree *temp = NULL;	//创建一个临时二叉树指针
	if (T == NULL) return;
	else{
		EnQueue(Q,T);	//把根节点入队操作
		while (!QueueEmpty(Q)) {
			temp = DeQueue(Q);	//队列非空时出队操作
			cout<<temp->data;
			if (temp->Lchild != NULL) {		//左子树非空时入队
				EnQueue(Q,temp->Lchild);
			}
			if (temp->Rchild !=NULL) {		//右子树非空时入队
				EnQueue(Q,temp->Rchild);
			}
		}
	}
  }

void main()
{
	BinTree *Tree;
	Tree = Tree->Create();
	cout<<"前序遍历的结果为："<<endl;
	Tree->PreOrder(Tree);
	cout<<endl;
	cout<<"后序遍历的结果为："<<endl;
	Tree->PostOrder(Tree);
	cout<<endl;
	cout<<"层次遍历的结果为："<<endl;
	Tree->LayOrder(Tree);
	cout<<endl;

}