exam4.cpp

来自「C++语言程序设计题典」· C++ 代码 · 共 229 行

#include <iostream.h>
#include <malloc.h>
#define MaxSize 100
#define MaxWidth 40
typedef char elemtype;
typedef struct node
{
     elemtype data;
     struct node *left,*right;
} BTree;    //定义二叉树的类型
class Tree
{
	BTree *b;
    void printtree1(BTree *bt);
    void preorder1(BTree *);
    BTree *find1(BTree *,elemtype x);
    void inorder1(BTree *);
    void postorder1(BTree *);
    int treedepth1(BTree *);
public:
	Tree() { b=NULL; }
    void creatree(char *str);
    void disptree();
    void printree();
    void preorder();
    BTree *find(elemtype x);
    void inorder();
    void postorder();
    int treedepth();
};
void Tree::creatree(char *str)
{
   BTree *stack[MaxSize],*p;
   int top=-1,k,j=0;  //top为栈指针,k指定是左还是右孩子,j为str指针
   char ch;
   ch=str[j];
   while (ch!='\0')
   {
 	 switch(ch)
	 {
	    case '(':top++;stack[top]=p;k=1; break;  //为左结点
	    case ')':top--;break;
	    case ',':k=2; break;                     //为右结点
	    default: p=(BTree *)malloc(sizeof(BTree));
		     p->data=ch;p->left=p->right=NULL;
		     if (b==NULL)                        //根结点
			     b=p;
		     else
		     {
		       switch(k)
		       {
			       case 1:stack[top]->left=p;break;
			       case 2:stack[top]->right=p;break;
		       }
		     }
	 }
	 j++;
	 ch=str[j];
  }
}
void Tree::disptree()  //以凹入表表示法输出一棵二叉树
{
   BTree *stack[MaxSize],*p;
   int level[MaxSize][2],top,n,i,width=4;
   char type;
   if (b!=NULL)
   {
       top=1;
	   stack[top]=b;          //根结点入栈
	   level[top][0]=width;
	   level[top][1]=2;       //2表示是根
	   while (top>0)
       {
          p=stack[top];       //退栈并凹入显示该结点值
	      n=level[top][0];
		  switch(level[top][1])
		  {
  		      case 0:type='0';break;   //左结点之前输出（0）
		      case 1:type='1';break;   //右结点之前输出（1）
		      case 2:type='r';break;   //根结点之前输出（r）
		  }
	      for (i=1;i<=n;i++)  //其中n为显示场宽,字符以右对齐显示
	         cout << " ";
	      cout << p->data << " (" << type << ")";
	      for (i=n+1;i<=MaxWidth;i+=2)
	         cout << "━";
	      cout << endl;
	      top--;
          if (p->right!=NULL)
          {                         //将右子树根结点入栈
	         top++;
	         stack[top]=p->right;
	         level[top][0]=n+width; //显示场宽增width
			 level[top][1]=1;       //1表示是右子树
          }
          if (p->left!=NULL)
          {                         //将左子树根结点入栈
	        top++;
            stack[top]=p->left;
	        level[top][0]=n+width;  //显示场宽增width
			level[top][1]=0;        //0表示是左子树
          }
	   }
   }
}
void Tree::printree()
{
	printtree1(b);
}
void Tree::printtree1(BTree *bt)
{
   if (bt!=NULL)
   {
     cout << bt->data;
	 if (bt->left!=NULL || bt->right!=NULL)
	 {
	   cout << "(";
	   printtree1(bt->left);     //递归处理左子树
	   if (bt->right!=NULL) cout << ",";
	   printtree1(bt->right);    //递归处理右子树
	   cout << ")";
	 }
   }
}
void Tree::preorder()
{
	preorder1(b);
}
void Tree::preorder1(BTree *bt)
{
	if (bt!=NULL)
	{
		cout << bt->data << " ";
		preorder1(bt->left);
		preorder1(bt->right);
	}
}
BTree *Tree::find(elemtype x)
{
	return find1(b,x);
}
BTree *Tree::find1(BTree *bt,elemtype x)
{
	BTree *p;
	if (bt==NULL)
		return NULL;
	else if (bt->data==x)
		return bt;
	else
	{
		p=find1(bt->left,x);
		if (p!=NULL)
			return p;
		else
		   return find1(bt->right,x);
	}
}
void Tree::inorder()
{
	inorder1(b);
}
void Tree::inorder1(BTree *bt)
{
	if (bt!=NULL)
	{
		inorder1(bt->left);
		cout << bt->data << " ";
		inorder1(bt->right);
	}
}
void Tree::postorder()
{
	postorder1(b);
}
void Tree::postorder1(BTree *bt)
{
	if (bt!=NULL)
	{
		postorder1(bt->left);
		postorder1(bt->right);
		cout << bt->data << " ";
	}
}
int Tree::treedepth()
{
	return treedepth1(b);
}
int Tree::treedepth1(BTree *bt)
{
   int leftdep,rightdep;
   if (bt==NULL)         //空树的深度为0
	   return(0);
   else
   {
 	  leftdep=treedepth1(bt->left);
	  rightdep=treedepth1(bt->right);
	  if (leftdep>rightdep)
		  return (leftdep+1);
	  else
		  return (rightdep+1);
   }
}
void main()
{
	Tree bt;
	bt.creatree("(a(b(c),d(e(,f),g)))");
	cout << "嵌套表示法:\n    ";
	bt.printree();
    cout << endl << "\n凹入表示法:\n";
	bt.disptree();
	cout << endl;
	cout << "前序遍历序列:";
	bt.preorder();
	cout << endl;
	cout << "中序遍历序列:";
	bt.inorder();
	cout << endl;
	cout << "后序遍历序列:";
	bt.postorder();
	cout << endl;
	cout << "e结点是否在bt中:";
	if (bt.find('e')!=NULL)
		cout << "在" << endl;
	else
	    cout << "不在" << endl;
	cout << endl;

}