btree.cpp

使用前序

#include <iostream.h>
#include <stdlib.h>


typedef char datatype;
struct bitree 
{ 

	datatype data; 
	struct bitree *lchild;
	struct bitree *rchild;
};

void InitBTree(bitree *&BT)
{
	BT=NULL;
}


		  
int BTreeEmpty(bitree * BT)
{
	return BT==NULL;
}

void CreateBiTree(bitree *&BT)//建立
{
	char ch;
	cin>>ch;
	if(ch=='@') BT=NULL;
	else
	{
		BT=new bitree;
		if(!BT)
			exit(1);
		BT->data=ch;
		CreateBiTree(BT->lchild);
		CreateBiTree(BT->rchild);
	}
}

void Preorder(bitree * BT) //前序遍历
{
	if(BT!=NULL){
		cout<<BT->data<<' ';
		Preorder(BT->lchild);
		Preorder(BT->rchild);
	}
}


void Inorder(bitree * BT) //中序遍历
{
	if(BT!=NULL){
		Inorder(BT->lchild);
		cout<<BT->data<<' ';
		Inorder(BT->rchild);
	}
}

void Postorder(bitree * BT) //后序遍历
{
	if(BT!=NULL){
		Postorder(BT->lchild);
		Postorder(BT->rchild);
		cout<<BT->data<<' ';
	}
}


int BTreeDepth(bitree * BT)                                
  {
	int p,q;
	if (BT==NULL)  return 0;
	else
	{
			p=BTreeDepth(BT->lchild);
            q=BTreeDepth(BT->rchild);
           
            if(p>q) return p+1;

            else return q+1;
	}
  }

int j=0;
int BTreeCount(bitree *BT)
{
	
	if(BT!=NULL){
		j++;
		//cout<<BT->data<<' ';
		j=BTreeCount(BT->lchild);
		j=BTreeCount(BT->rchild);
	}
	return j;
}
int i=0;
int BTreeLeafCount(bitree *BT)
{
	
	if(BT!=NULL){
		if(BT->lchild==NULL && BT->rchild==NULL)
			i++;
		//cout<<BT->data<<' ';
		i=BTreeLeafCount(BT->lchild);
		i=BTreeLeafCount(BT->rchild);
	}
	return i;
}


void main()
{
      bitree *bt;
      InitBTree(bt);
      cout<<"以先序序列输入二叉树："<<endl;
	  CreateBiTree(bt);
	  //change(bt);
      cout <<"前序：";
      Preorder(bt); cout<<endl;
      cout <<"中序: ";
      Inorder(bt); cout<<endl;
      cout <<"后序: ";
      Postorder(bt); cout<<endl;
	  cout<<"深度为：";
	  cout<<BTreeDepth(bt);cout<<endl; 
	  cout<<"结点个数为:";
      cout<<BTreeCount(bt);cout<<endl;
	  cout<<"叶子个数为:";
      cout<<BTreeLeafCount(bt);cout<<endl;   
}