binarytree.cpp

二叉树的实现功能： （1）生成二叉树 （2）先序遍历 （3）后序遍历 （4）中序遍历 （5）二叉树的高度 （6）统计数的节点数

#include<iostream.h>

struct node
{
	int data;
	node *left;
	node *right;
};

void iterate(node * &root, int m)  //寻找最佳的插入地点
{
	node *p=0;
	if(m<root->data)
	{
		if(root->left)
		{
			iterate(root->left,m);
		}
		else
		{
			p=new node;
			p->data=m;
			p->left=p->right=NULL;
			root->left=p;
		}

	}
	else
	{
		if(root->right)
		{
			iterate(root->right,m);
		}
		else
		{
			p=new node;
			p->data=m;
			p->left=p->right=NULL;
			root->right=p;
		}
	}
}

node *initial()   //生成二叉树
{
	node *root=0;
	cout<<"Please input values with the end of 0"<<endl;
	int m;
	cin>>m;

	root =new node;
	root->data=m;
	root->left=root->right=NULL;
	cin>>m;
	while(m)
	{
		iterate(root,m);
		cin>>m;
	}
	return root;
}

void InorderTraverse(node *root)   //中序遍历
{
	if(root)
	{
		if(root->left)
			InorderTraverse(root->left);
		cout<<root->data<<" ";
		if(root->right)
			InorderTraverse(root->right);
	}
}

void PreoderTraverse(node *root)   //前序遍历
{
	if(root)
	{
		cout<<root->data<<" ";
		if(root->left)
			PreoderTraverse(root->left);
		if(root->right)
			PreoderTraverse(root->right);
	}
}

void PosterorderTraverse(node *root) //后序遍历
{
	if(root)
	{
		if(root->left)
			PosterorderTraverse(root->left);
		if(root->right)
			PosterorderTraverse(root->right);
		cout<<root->data<<" ";
	}
}

int count(node *root) //统计数目
{
	if(root==NULL)
		return 0;
	else
		return 1+count(root->left)+count(root->right);

}

int height(node *root)  //树的高度
{
	if(root==NULL)
		return -1;
	else
	{
		int m=height(root->left);
		int n=height(root->right);
		return (m>n)? m+1:n+1;
	}
}

void main()
{
	node *root=initial();
	InorderTraverse(root);
	cout<<endl;
	int m=height(root);
	cout<<"m="<<m<<endl;

}