//树的括号表示转换成树的孩子（数组方式）表示 算法#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输入法不行）！// 有谁知道原因的，说下啊！

评论