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

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

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

1. 子表
2. 子表嵌套子表
3. 结点
4. , 空结点

#include<stdio.h>
#include<stdlib.h>

typedef struct node{
    char data;
    struct node * lchild,* rchild;
} BinTNode;

//实现根据一个广义表创建树
BinTNode * CreateTree(char * str)
{
    //str为存储广义表的字符串的指针
    BinTNode *st[100];//用指针数组模拟栈
    BinTNode *p = NULL;//置空栈
    int top,k=0,j=0;//k 作为一个标记，k=1,读到的下一个字符就是子树
    top = -1;
    BinTNode *b = NULL;
    char ch = str[j];
    while (ch!='\0') {
        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;//返回根结点的指针
}

中间读取的变化

image.png

打印结果

char c_array[15] = {'(','A','(','B','(','D','(','E',',','F',')',')',',','C'};
int main(int argc, const char * argv[]) {
    // insert code here...
    printf("Hello, Miaoyixi!\n");
//    BinTNode *s == NULL;
//    BinTNode CreateTree(BinTNode *s,char * str);
//    for(int i = 0;i<15;i++){
    BinTNode *s = CreateTree(c_array);
//    }
   char t = s->data;
    printf("根节点%c\n",t);
    printf("根左结点%c\n",s->lchild->data);
    printf("根右结点%c\n",s->rchild->data);
    printf("执行ok\n");
//    printf(s->rchild);
//    CreateTree("(A,(B,(C,D)),(,D))");
    return 0;
}

image.png