二叉树建立与遍历.cpp

二叉树建立与遍历源代码

//程序用法：本程序二叉树的构造过程采用广义表作为输入，预先把节点信息以广义表字符串形式存储在文本
//文件中，程序运行首先从文件中读出节点信息构造二叉树。
//注意：文件中每一个字母代表一个节点元素值；
//      每个根结点作为由子树构成的表的名字放在前面；
//      每个结点的左孩子与右孩子用逗号隔开，若只有右孩子而无左孩子，逗号不能省略；
//      整个广义表以@作为结尾!!!，切记。
#include<iostream>
#include<fstream>
#include<limits>
#include<queue>//为了避免代码过于冗余，在此不自定义队列类，使用系统容器代替。
#include<stack>//同上
using namespace std;

char read(char *A)//从字符数组读取字符
{
	static count=0;
	return A[count++];
}

//树结点类:
class BinaryTree;
class BinTreeNode{
friend class BinaryTree;
private:
	BinTreeNode *leftChild,*rightChild;//左右孩子指针
	char data;//节点元素
public:
	BinTreeNode():leftChild(NULL),rightChild(NULL){}
	BinTreeNode(char d,BinTreeNode *lp=NULL,
		BinTreeNode *rp=NULL):data(d),leftChild(lp),rightChild(rp){}
	char GetData()//获取节点元素
	{
		return data;
	}
	BinTreeNode *GetLeftChild()//取得左孩子指针
	{
		return leftChild;
	}
	BinTreeNode *GetRightChild()//取得右孩子指针
	{
		return rightChild;
	}
	void SetData(char d)//设置节点元素值
	{
		data=d;
	}
	void SetLeftChild(BinTreeNode *p)//设置左孩子指针
	{
		leftChild=p;
	}
	void SetRightChild(BinTreeNode *p)//设置右孩子指针
	{
		rightChild=p;
	}
};

//二叉树链表类
class BinaryTree{
private:
	BinTreeNode *root;//根结点
	void destroy(BinTreeNode *p);//销毁结点P
	void PreOrderTravers(BinTreeNode *r);//前序遍历
	void InOrderTravers(BinTreeNode *r);//中序遍历
	void PostOrderTravers(BinTreeNode *r);//后序遍历
	int length(BinTreeNode *n);//求树的深度
public:
	BinaryTree():root(NULL){}
	BinaryTree(char d)
	{
		root=new BinTreeNode(d);
	}
	virtual~BinaryTree()
	{
		destroy(root);
	}
    bool IsEmpty(){return root==NULL? true:false;}//判断树非空
    void build(char *A);//建立二叉树
	int length(){return length(root);};//求树的深度接口
    void PreOrderTravers()//前序遍历接口
	{
		PreOrderTravers(root);
	}
	void InOrderTravers()//中序遍历接口
	{
		InOrderTravers(root);
	}
	void PostOrderTravers()//后序遍历接口
	{
		PostOrderTravers(root);
	}
	void LevelOrderTravers();//层次遍历
};
//成员函数实现
void BinaryTree::build(char *A)//建立二叉树，由广义表输入
{
	stack<BinTreeNode*> t;
	BinTreeNode *p;
	int flag;
    do
	{
		char ch=read(A);
		switch(ch)
		{
		case '@':return;
		case '(':{t.push(p);flag=1;}break;
		case ')':t.pop();break;
		case ',':flag=2;break;
		default:{
			        p=new BinTreeNode(ch);
                    if(root==NULL)
					{
						root=p;
					}
					else
					{
						if(flag==1)
						{
							t.top()->SetLeftChild(p);
						}
						else
						{
							t.top()->SetRightChild(p);
						}
					}
				}
			break;
		}
	}while(true);
}
int BinaryTree::length(BinTreeNode *n)//求树深度
{
	if(n==NULL)
	{
		return 0;
	}
	else
	{
		int lclen=length(n->GetLeftChild());
		int rclen=length(n->GetRightChild());
		if(lclen<rclen)
			return rclen+1;
		else
			return lclen+1;
	}
}
void BinaryTree::destroy(BinTreeNode *p)//销毁二叉树
{
	if(p!=NULL)
	{
		destroy(p->GetLeftChild());
		destroy(p->GetRightChild());
		delete p;
	}
}
//前序遍历
void BinaryTree::PreOrderTravers(BinTreeNode *r)
{
	if(r!=NULL)
	{
		cout<<r->GetData()<<" ";
		PreOrderTravers(r->GetLeftChild());
		PreOrderTravers(r->GetRightChild());
	}
}
//中序遍历
void BinaryTree::InOrderTravers(BinTreeNode *r)
{
	if(r!=NULL)
	{
		InOrderTravers(r->GetLeftChild());
		cout<<r->GetData()<<" ";
		InOrderTravers(r->GetRightChild());
	}
}
//后序遍历
void BinaryTree::PostOrderTravers(BinTreeNode *r)
{
	if(r!=NULL)
	{
		PostOrderTravers(r->GetLeftChild());
		PostOrderTravers(r->GetRightChild());
		cout<<r->GetData()<<" ";}
}
//层次遍历
void BinaryTree::LevelOrderTravers()
{
	queue<BinTreeNode*> q;
	BinTreeNode *p=root;
	if(p)
		q.push(p);
	while(!q.empty())
	{
		p=q.front();
		cout<<p->GetData()<<" ";
		if(p->GetLeftChild())
			q.push(p->GetLeftChild());
		if(p->GetRightChild())
			q.push(p->GetRightChild());
		q.pop();
	}
}

void Reset()//输入异常处理函数
{
	cout<<"输入非数字字符,请重输:\n";
	cout<<std::flush;
    std::cin.clear();
    std::cin.ignore(std::numeric_limits<std::streamsize>::max(), '\n' );
}
//主函数
void main()
{
	BinaryTree BTree;
	char *A=new char[30];
	ifstream file("node.txt",ios::in);
	if(!file)
	{
		cout<<"节点文件打开失败,请先配置好二叉树的节点文件!";
		return;
	}
	file.getline(A,30);
	file.close(); 
	BTree.build(A);
	cout<<"二叉树构造完毕!"<<endl;
	do
	{
		cout<<endl;
		cout<<"\t\t\t****请选择操作****\n";
        cout<<"\t\t\t****1.先根遍历****\n";
	    cout<<"\t\t\t****2.中根遍历****\n";
        cout<<"\t\t\t****3.后根遍历****\n";
        cout<<"\t\t\t****4.层次遍历****\n";
     	cout<<"\t\t\t****5.树的深度****\n";
    	cout<<"\t\t\t****6.退出模拟****\n";
    	cout<<"请选择:";
	    int s;//选择
		while(!(cin>>s))
			 Reset();
	    switch(s)
		{
     	case 1:cout<<endl<<"先根遍历结果:"<<endl;BTree.PreOrderTravers();break;
	    case 2:cout<<endl<<"中根遍历结果:"<<endl;BTree.InOrderTravers();break;
	    case 3:cout<<endl<<"后根遍历结果:"<<endl;BTree.PostOrderTravers();break;
        case 4:cout<<endl<<"层次遍历结果:"<<endl;BTree.LevelOrderTravers();break;
		case 5:cout<<endl<<"该二叉树的深度为:";cout<<BTree.length();break;
		case 6:return;
     	default:cout<<"请正确选择!\n";break;
		}
	}while(true);
}