btree.h

严蔚敏 数据结构题集 第六章 答案 自己做的

#include<iostream.h>
#include<strstrea.h>
#include<stdlib.h>
struct BTreeNode
{ 
	ElemType  data;
	BTreeNode *left;
	BTreeNode *right;
};
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
			{
				switch(k)
				{
				case 1:s[top]->left=p;
					break;
				case 2: s[top]->right=p;
				}
			
			}
		}
		ins>>ch;
	}
}




void Preorder(BTreeNode *BT)
{
	if(BT!=NULL)
	{
		cout<<BT->data;
		Preorder(BT->left);
		Preorder(BT->right);
	}
}
void Inorder(BTreeNode *BT)
{
	if(BT!=NULL)
	{
		Inorder(BT->left);
	    cout<<BT->data;
		Inorder(BT->right);
	}
}
void Laorder(BTreeNode *BT)
{
	if(BT!=NULL)
	{
		Laorder(BT->left);
	    Laorder(BT->right);
		cout<<BT->data;
	}
}
void Levelorder(BTreeNode *BT)
{
	BTreeNode *q[30];
	int front=0,rear=0;
	BTreeNode *p;
	if(BT!=NULL)
	{
		rear=(rear+1)%30;
		q[rear]=BT;
	}
	while(front!=rear)
	{
		front=(front+1)%30;
		p=q[front];
		cout<<p->data;
		if(p->left!=NULL)
		{
			rear=(rear+1)%30;
			q[rear]=p->left;
		}
		if(p->right!=NULL)
		{
			rear=(rear+1)%30;
			q[rear]=p->right;
		}
	}
}
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;
	}

}
void PrintBTree(BTreeNode *BT)
{
	if(BT!=NULL)
	{
		cout<<BT->data;
		if(BT->left!=NULL||BT->right!=NULL)
		{
			cout<<'(';
			PrintBTree(BT->left);
			if(BT->right!=NULL)
				cout<<',';
			PrintBTree(BT->right);
			cout<<')';
		}
	}
}
int Count(BTreeNode *BT)
{
	if(BT==NULL)
		return 0;
	else 
		return Count(BT->left)+Count(BT->right)+1;
}
int LeafCount(BTreeNode *BT)
{
	if(BT==NULL)
		return 0;
	else if(BT->left==NULL&&BT->right==NULL)
			return 1;
	else
		return LeafCount(BT->left)+LeafCount(BT->right);
}
void DeleteBTree(BTreeNode *BT)
{
	if(BT!=NULL)
	{
		DeleteBTree(BT->left);
		DeleteBTree(BT->right);
		delete BT;
	}
}
void ClearBTree(BTreeNode *&BT)
{
	DeleteBTree(BT);
	BT=NULL;
}