16.cpp

该程序采用结构定义二叉树结点的类型

#include<iostream.h>
#include<stdlib.h>
#include<strstrea.h>
#include "16.h"
void InitBTree(BTreeNode*& BT)
{
	BT=NULL;
}
void CreateBTree(BTreeNode*& BT,char* a)
{
	BTreeNode*s[10];
	int top=-1;
	BT=NULL;
	BTreeNode* p;
	int k;
	istrstream ins(a);
	char ch;
	ins>>ch;
	while(ch!='@')
	{
		switch(ch)
		{
		case'(':
			top++;s[top]=p;k=1;break;
		case')':
			top--;break;
		case',':
			k=2;break;
		default:
			p=new BTreeNode;
			p->data=ch;p->left=p->right=NULL;
			if(BT==NULL) BT=p;
			else{
				if(k==1) s[top]->left=p;
				else s[top]->right=p;
			}
		}
		ins>>ch;
	}
}

bool BTreeEmpty(BTreeNode*BT)
{
	return BT==NULL;
}

void TraverseBTree(BTreeNode* BT,int mark)
{
	if(mark==1){
		if(BT!=NULL){
			cout<<BT->data<<' ';
  			TraverseBTree(BT->left,mark);
            TraverseBTree(BT->right,mark);
		}
	}
	else if(mark==2){
		if(BT!=NULL){
	           TraverseBTree(BT->left,mark);
               cout<<BT->data<<' ';
               TraverseBTree(BT->right,mark);
		}
	}
	else if(mark==3){
		if(BT!=NULL){
               TraverseBTree(BT->left,mark);
               TraverseBTree(BT->right,mark);
               cout<<BT->data<<' ';
		}
	}
	else if(mark==4)
	{
		const MaxLength=30;
		BTreeNode*Q[MaxLength];
		int front=0,rear=0;
		BTreeNode * p;
		if(BT!=NULL){
			rear=(rear+1)%MaxLength;
			Q[rear]=BT;
		}
		while (front !=rear)
		{
			front=(front+1)%MaxLength;
			p=Q[front];
			cout<<p->data<<' ';
			if(p->left!=NULL)
			{
				rear=(rear+1)%MaxLength;
				Q[rear]=p->left;
			}
			if(p->right!=NULL)
			{
				rear=(rear+1)%MaxLength;
				Q[rear]=p->right;
			}
		}
	}
	else {
		cerr<<"mark的值无效！遍历失败！"<<endl;
		exit(1);
	}
}

int BTreeDepth(BTreeNode * BT)
{
	if(BT==NULL)
		return 0;
	else
	{
		int dep1=BTreeDepth(BT->left);
		int dep2=BTreeDepth(BT->right);
		if(dep1>dep2) return dep1+1;
		else return dep2+1;
	}
}

int BTreeCount(BTreeNode* BT)
{
	if(BT==NULL) return 0;
	else 
		return BTreeCount(BT->left)+BTreeCount(BT->right)+1;

}

int BTreeLeafCount(BTreeNode* BT)

{
	if(BT==NULL) return 0;
	else if(BT->left==NULL&&BT->right==NULL)return 1;
	else return BTreeLeafCount(BT->left)+BTreeLeafCount(BT->right);
}

void PrintBTree(BTreeNode* BT)
{
	if(BT==NULL) return;
	else{
		cout<<BT->data;
		if(BT->left!=NULL||BT->right!=NULL)
		{
			cout<<'(';
			PrintBTree(BT->left);
			if(BT->right!=NULL)
				cout<<',';
			PrintBTree(BT->right);
			cout<<')';
		}
	}
}

void ClearBTree(BTreeNode* & BT)
{
	if(BT!=NULL)
	{
		ClearBTree(BT->left);
		ClearBTree(BT->right);
		delete BT;
		BT=NULL;
	}
}