学步园

本来就是想实现一下二叉树的中序遍历，就用了二叉搜索树来搞，结果发现了一个非常浅显但我之前不知道的现象，就是中序遍历二叉搜索树得到的序列是有序序列。算是涨姿势了……

#include <iostream>
#include<stack> 
using namespace std;
class binNode
{
public:
	int val;
	binNode *left,*right;
	binNode(int v,binNode *leftChild,binNode *rightChild)
		:val(v),left(leftChild),right(rightChild){}
	binNode(){}
};
class binTree
{
private:
	binNode *root;
	stack<binNode*> sta;
	int size;
public:
	binTree()
	{
		root=NULL;
		size=0;
	}
	void insert(const int& n)
	{
		size++;
		binNode* tem=root;
		if(root==NULL) 
		{
			root=new binNode(n,NULL,NULL);
			return ;
		}
		while(1)
		{
			if(n==tem->val) return ;
			else if(n>tem->val) 
			{
				if(tem->right!=NULL)
					tem=tem->right;
				else { tem->right=new binNode(n,NULL,NULL); break;}
			}
			else 
			{
				if(tem->left!=NULL)
					tem=tem->left;
				else {tem->left=new binNode(n,NULL,NULL);break;}
			}
		}
	}
	void travelsal()
	{
		int cnt=0;
		if(root==NULL){ cout<<"empty tree!"<<endl; return;}
		binNode *cur=root;
		while(cnt<size)
		{
			if(cur==NULL) 
			{
				binNode *top=sta.top();
				sta.pop();
				cout<<top->val<<' ';
				cnt++;
				cur=top->right;
			}
			else 
			{
				sta.push(cur);
				cur=cur->left;
			}
		}
	}
};

				
binTree big;		
int main()
{
	
	int size;
	cin>>size;
	int a;
	for(int i=0;i<size;i++)
	{
		cin>>a;
		big.insert(a);
	}
	big.travelsal();
}