创建二叉树，根据前序遍历或根据括号表示法

二叉树节点：

typedef struct node{
    elemType data;
    struct node *lchild;
    struct node *rchild;
}BTNode;

输入前序遍历序列建立二叉树，空节点为空格：

//根据前序遍历建立二叉树 
int create(BTNode *&T){
    elemType ch;
    scanf("%c",&ch);
    if(ch==' ')
        T=NULL;
    else{
        T=(BTNode*)malloc(sizeof(BTNode));
        T->data=ch;
        create(T->lchild);
        create(T->rchild);
    }
    return 1;
}

根据树的括号表示法建立二叉树：

//根据括号表示法创建二叉树
void create2(BTNode *&root,char *str){
    root=NULL;
    BTNode *p;
    int i=0,k=0;
    stack<BTNode*> s;
    char ch=str[i];
    while(ch!=''){
        switch(ch){
            case '(':{
                s.push(p);
                k=1;        //下次添加左孩子节点 
                break;
            }
            case ',':{
                k=2;        //下次添加右孩子节点
                break;
            }
            case ')':{
                s.pop();
                break;
            }
            default:{
                p=(BTNode*)malloc(sizeof(BTNode));
                p->lchild=p->rchild=NULL;
                p->data=ch;
                if(root==NULL)
                    root=p;
                else{
                    if(k==1){
                        s.top()->lchild=p;
                    }else if(k==2)
                        s.top()->rchild=p;
                }
                break;
            }
        }
        ch=str[++i];
    }
    
}

测试：

输入 "ABD  G  CE  F  "

int main(){
    BTNode *T;
    //输入前序遍历建立二叉树  
    create(T);
    //层次遍历输出二叉树
    levelorder(T);
    return 0;
}

 

int main(){
    BTNode *T;
    //括号表示法建立二叉树 
    create2(T,"A(B(D(,G)),C(E,F))");
    
    //层次遍历输出二叉树
    levelorder(T);
    return 0;
}