//树的括号表示转换成树的孩子（数组方式）表示 算法
#include <iostream>
#include<stdio.h>
using namespace std;
#define m 3                 //树的度数
#define maxsize 20          //数的孩子表示法对应数组大小
#define bmaxsize 25       //树的括号表示对应数组大小

typedef char datatype;      //树中节点值类型
typedef struct node         //树的孩子表示法中节点类型
{
 datatype data;
 int child[m];
}treenode;

treenode tree[maxsize];     //树的孩子表示法存储数组
int root;                   //根结点的下标
int length;                 //树中实际所含结点的个数        
char p[bmaxsize];           //存放树括号表示的数组         

void bracktotree(char p[],int* root,int* length,treenode tree[])
{//将树的括号表示法转换成树的孩子表示法
 int stack[maxsize];     //存放树或子树根结点的栈
 int top;                //栈顶指针
 int i,j,k,l,done;       //done 为程序结束标志
 k=0;  j=0;  *root=0;
    top=-1; done=1;         //栈和标志的初始化
 
 tree[j].data=p[k];      //产生孩子表示法的根结点
    ++k;
 for(i=0;i<m;i++)
  tree[j].child[i]=-1;   //初始化根结点的孩子
 while(done)
 {
  if(p[k]=='(')       //遇到左括号，则其前面的元素对应的结点进栈
  {
   ++top;
            stack[top]=j;   //注意：j是标号（P[j]是树或子树的双亲），因为在树的孩子（数组方式）法中，是用标号联系孩子与双亲的
   ++k;            //继续向右扫描
  }
  else if(p[k]==')')  //遇到右括号，栈顶元素出栈,说明以栈顶元素为根的子树构造完毕。若此时栈为空，算法结束
  {
   --top;
   if(top==-1)     //栈为空，算法结束
    done=0;
   else ++k;        //否则继续向右扫描
  }
  else if(p[k]==',')
   ++k;
  else
  {//将当前扫描元素作为栈顶元素的子女
   ++j;
   tree[j].data=p[k]; //首先产生子树根结点，此子树是栈中结点的一个孩子
   for(i=0;i<m;++i)
    tree[j].child[i]=-1;   //初始化子树根结点孩子
   l=stack[top];           //此子树的双亲的结点序号
            i=0;
   //寻找栈顶元素（即此树的双亲）当前的第1个空子女
            while(tree[l].child[i]!=-1)
    ++i;
   tree[l].child[i]=j;       
   ++k;
  }
 }
 *length=j;
}
 
int main()
{
 cout<<"输入一棵树（括号表示）:";
 gets(p);              
    bracktotree( p,&root,&length, tree);  //括号表示转换为（数组方式）孩子表示
 cout<<"输出此树的孩子表示： "<<endl;
 for(int i=0;i<length;i++)
 {
  cout<<tree[i].data<<"   ";         //输出此树根结点
  for(int j=0;j<m;j++)                    //输出他的孩子
   cout<<tree[i].child[j]<<"    ";
  cout<<endl;
 }
}

// 注意：输入树的时候 要 切换 成 字符 输入法 （在大写情况下的智能ABC输入法不行）！
// 有谁知道原因的，说下啊！

评论