孩子兄弟链存储结构

二叉树的孩子兄弟链存储结构

数据结构的大作业实在是头疼，想了好久然后觉得孩子兄弟链存储结构比较合适

先放完整的代码

typedef struct node
{
    char data;
    struct node *sublist; //孩子链指针
    struct node *link;//兄弟链指针
}BTNode;

#define MaxSize 30

char a[MaxSize] = "8(9,2(3,1(4,5)),7(6,A))" ;

void CreatBTNode(BTNode *&b, char *str)
{
    //做一个辅助栈结构
    BTNode *St[MaxSize], *p = NULL;
    int top = -1;

    char ch;
    b = NULL;
    int k = 0;
    int i = 0;
    ch = str[i];
    bool flag = true;
    bool flag2 = false;
    while (ch != '\0')
    {
        switch (ch)
        {
            //有一个标记，遇到左括号清零，
        case '(':flag = true; top++; St[top] = p; k = 1; break;
        case ','://如果逗号前面的一个字符是右括号，那么就不需要进栈
            if (flag2)
            {
                flag2 = false;
                break;
            }
            else
            {
                top++; St[top] = p; k = 2; break;
            }
            //这里如果是第一次遇到右括号，只要减1
            
        case ')':flag2 = true;
            if (flag == true)top -= 1, flag = false;
                 else top -= 2; 
            break;
        default:
            //默认情况下，ch是存储的数据
            p = (BTNode *)malloc(sizeof(BTNode));
            p->data = ch; p->sublist = p->link = NULL;
            if (b == NULL)
                b = p;
            else
            {
                //根据第一个switch的k值来判断
                switch (k)
                {
                case 1://代表要用sublist指针指向
                    St[top]->sublist = p; break;
                    //代表用link指针指向
                case 2:St[top]->link = p; break;

                }
            }
        }
        i++;
        ch = str[i];
    }
}

测试代码

int main()
{
    
    BTNode *b;
    CreatBTNode(b, a);
    system("pause");
    return 0;
}

不得不说，这段代码写得特别的糟心，首先有很大一部分代码是copy自教材上面的，虽然我很看不起那本教材，但是发现自己还是太垃圾了，所以只好按照它的来写代码了。

然后有几个地方稍微强调一下

*我在这里用了两个布尔变量，一个flag，用来判断是不是第一次遇到右括号，我在这里纠结了很久
1.我必须要知道第一次遇到右括号的时候，因为这个时候top(就是栈指针)只能减去1，不然就就会出错
2.因为左括号是在左边，然后遇到右括号的时候开始退栈，所以每次遇到左括号的时候，flag必须是true

*第二个变量是flag2
1.我之所以用这个变量，是因为，如果遇到右括号之后的逗号，这个时候我设定的是遇到括号就要进栈，而如果这个时候进栈又会出错，所以我必须标记一下，逗号之前的那个字符是不是右括号，如果是右括号，那么就啥都不要干

然后其他部分的代码其实和教材上的构造二叉树的代码基本上是一样的。