数据结构生成一颗二叉树算法

数据结构生成一颗二叉树算法

木来 木来

通过对输入的字符串进行遍历,如果遇到(就将其进栈,如果遇到)就将其退栈。

//树结构
typedef struct node{
  ElemType data;
  struct node *lchild;
  struct node *rchild;

}BTNode;


//生成树
void CreateBTree(BTNode *&b,char *str){
  BTNode *St[Maxsize],*p;//建立顺序栈St
  int top=-1,j=0;//top为栈指针,初始为-1
  char ch;
  b=NULL;
  ch=str[j];//获取字符串str的第一个字符
  
  while(ch!='\0'){//遍历字符串str
  
  switch(ch){
    case '(':top++;St[top]=p;k=1;break;//处理左孩子结点
    case ')':top--;break;//栈顶结点的子树处理完毕
    case ',':k=2;break;//处理右孩子结点
    default:p=(BTNode *)malloc(sizeof(BTNode));
      p->data=ch;
      p->lchild=p->rchild=NULL;
      if(b==NULL){ //如果树没有根节点
      b=p;//将p作为根节点
      }else{
      switch(k){
        case 1:St[top]->lchild=p;break;
        case 2:St[top]->rchild=p;break;
      }//swicth
      }//swicth
      
    j++;
    ch=str[j];
  
  }//while
  
  
  }

}
0 条评论