#include<iostream.h>
struct TreeNode{
char data;
TreeNode *firstson,*nextbrother;
};
int max(int a,int b)
{
return (a>b)?a:b;
}
int high(TreeNode *T, int i,int &b)
{
if(T!=NULL)
{
i++;
high(T->firstson,i,b);
while(T->nextbrother!=NULL)
{
T=T->nextbrother;
high(T->firstson,i,b);
}
b=max(b,i);
}
return b;
}
void Broadsense_Output(TreeNode *&T)//广义输出
{
if(T!=NULL)
{
cout<<"(";
L0: cout<<T->data;
Broadsense_Output(T->firstson);
while(T->nextbrother!=NULL && T->firstson==NULL)
{
cout<<","<<T->nextbrother->data;
T=T->nextbrother;
}
if(T->nextbrother==NULL)
cout<<")";
if(T->nextbrother!=NULL && T->firstson!=NULL)
{
cout<<",";
T=T->nextbrother;
goto L0;
}
}
}
class tree
{
public:
tree();
void create(TreeNode *&T);
void preorder(TreeNode *T);
int get_height(TreeNode *&T);
void hiberarchy_output(TreeNode *&T);
void visit_node(TreeNode *&T,int i);
void Broadsense_Output2(TreeNode *&T);
TreeNode *T;
};
tree::tree(){
T=NULL;
}
void tree::create(TreeNode *&T)
{
char x;int st,bt;
cin>>x>>st>>bt;
T=new TreeNode;
T->data=x;
if(st==0)
T->firstson=NULL;
else
create(T->firstson);
if(bt==0)
T->nextbrother=NULL;
else
create(T->nextbrother);
}
void tree::preorder(TreeNode *T){
if(T!=NULL)
{
cout<<T->data<<" ";
preorder(T->firstson);
preorder(T->nextbrother);
}
}
int tree::get_height(TreeNode *&T){
TreeNode *t=T;
int b=0,i=0,c=0,d=0;
while(t!=NULL)
{
c=high(t,i,d);
b=max(b,c);
t=t->nextbrother;
}
return b;
}
void tree::hiberarchy_output(TreeNode *&T)//层次遍历
{
if(T!=NULL)
{
cout<<T->data<<" ";
if(T->nextbrother!=NULL)
{
TreeNode *b=T;
while(T->nextbrother!=NULL)
{
cout<<T->nextbrother->data<<" ";
T=T->nextbrother;
}
T=b;
}
hiberarchy_output(T->firstson);
while(T->nextbrother!=NULL)
{
T=T->nextbrother;
hiberarchy_output(T->firstson);
}
}
}
void tree::visit_node(TreeNode *&T,int i)//遍历
{
if(T!=NULL)
{
i++;
cout<<T->data<<" "<<"层次数为:"<<i<<endl;
if(T->nextbrother!=NULL)
{
TreeNode *b=T;
while(T->nextbrother!=NULL)
{
cout<<T->nextbrother->data<<" "<<"层次数为:"<<i<<endl;
T=T->nextbrother;
}
T=b;
}
visit_node(T->firstson,i);
while(T->nextbrother!=NULL)
{
T=T->nextbrother;
visit_node(T->firstson,i);
}
}
}
void tree::Broadsense_Output2(TreeNode *&T){
TreeNode *d=T;
while(T!=NULL)
{
if(d==T)
cout<<"(";
cout<<T->data;
Broadsense_Output(T->firstson);
if(T->nextbrother!=NULL)
cout<<",";
T=T->nextbrother;
}
cout<<")"<<endl;
}
void main()
{
tree t;
char c;
L1: cout<<"建树时输入节点值 和标志(0,1)表示孩子或兄弟结点为空"<<endl;
cout<<"1.将一棵树（或森林）转换为二叉树并显示"<<endl;
cout<<"2.求森林的高度"<<endl;
cout<<"3.按层次方式遍历森林"<<endl;
cout<<"4.输出一个森林中每个结点的值及其对应的层次数"<<endl;
cout<<"5.输出一个森林的广义表形式"<<endl;
int x;
while(x!=0)
{cout<<"请输入你要的操作："<<endl;
cin>>x;
switch(x){
case 1:cout<<"请先建立一个森林或树："<<endl;t.create(t.T);
cout<<"兄弟链表表示该树并先序输出为："<<endl;t.preorder(t.T);break;
case 2:cout<<"请先建立一个森林或树："<<endl;t.create(t.T);cout<<"高度为："<<t.get_height(t.T);break;
case 3:cout<<"请先建立一个森林或树："<<endl;t.create(t.T);cout<<"按层次遍历结果为：";t.hiberarchy_output(t.T);break;
case 4:cout<<"请先建立一个森林或树："<<endl;t.create(t.T);cout<<"输出为："<<endl;t.visit_node(t.T,0);break;
case 5:cout<<"请先建立一个森林或树："<<endl;t.create(t.T);cout<<"广义表形式为："<<endl;t.Broadsense_Output2(t.T);break;
default:cout<<"输入错误，请重新输入:";goto L1;
}
cout<<endl<<endl<<"若要继续操作请按y,按其他键退出"<<endl;
cin>>c;
if(c!='y')
x=0;
}
}
