根据一个广义表来创建一个二叉树-稻草人资讯

根据一个广义表来创建一个二叉树

2024-09-08

56 阅读

根据一个广义表来创建一个二叉树

算法中用了一个指针数组来模拟栈存储结点的双亲指针，根据读入广义表中的字符分四种不同的情况处理：

子表

子表嵌套子表

结点

, 空结点

') {
        switch (ch) {
            case '(':
                top++;
                st[top]=p;
                k=1;
                break;
            case ')':
                top--;
                break;
            case ',':
                k=2;
                break;
            default://读到的是字符，作为结点
                p = (BinTNode *)malloc(sizeof(BinTNode));
                p->data = ch;//填写数据域
                p->lchild=p->rchild=NULL;//填写指针域
                if(b==NULL){//建立第一个结点
                    b=p;
                }else{
                    switch (k) {
                        case 1://前一个字符是‘(’，该结点应该插入左子树
                            st[top]->lchild=p;
                            break;
                        case 2://前一个字符是‘,’，该结点应该插入右子树
                            st[top]->rchild=p;
                            break;
                    }
                }
                break;
        }
        j++;
        ch=str[j];//读取下一个字符
    }
    return b;//返回根结点的指针
}

中间读取的变化