数据结构——树的实现

野性酷女 2022-06-17 04:08 139阅读 0赞

在做树的遍历的时候发现自己对实现树的方法不太了解，也就是不知道怎么把一棵树的结构存到内存中，所以对树的实现找了一些资料，自己也研究了一下。

首先，要想让计算机正确的保存你的“树”，你要用一种和你代码相匹配的输入方式，我用的是采用广义表表示的输入法，例如：A（B（D,E）,C（F,G））。  
这个式子可以分为以下几部分：  
A（B,C）： A是这个结构的根节点，B,C是A的两个孩子。  
A（B（D,E）,C（F,G））：B，C分别是D、E和F、G的父节点。

A
                /   \
               B     C
              / \   / \
             D   E F   G

当用广义表表示的方法输入之后，就可以用下面的代码来建立二叉树：

void CreateBTree(struct BTreeNode** BT, char* string)
    {
        struct BTreeNode* p;
        struct BTreeNode* s[StackMaxSize];   //定义s数组作为存储根结点的指针的栈使用
        int top = -1;               //栈顶指针置为-1，表示空栈
        int k;                 //k作为处理结点的标志，k=1处理左子树，k=2处理右子树
        int i = 0;              //用i扫描数组string中存储的二叉树广义表字符串，初值为0
        *BT = NULL;               //把树根指针置空，即从空树开始建立二叉树
        while (string[i])
        {
            switch (string[i])
            {
                case ' ':break;
                case '(':
                {
                    if (top == StackMaxSize - 1)
                    {
                        printf("栈空间太小，需增加StackMaxSize!\n");
                        exit(1);
                    }
                    top++;
                    s[top] = p;
                    k = 1;
                    break;
                }
                case ')':
                {
                    if (top == -1)
                    {
                        printf("二叉树广义表字符串错！\n");
                        exit(1);
                    }
                    top--;
                    break;
                }
                case ',':k = 2;break;
                default:
                {
                    p = malloc(sizeof(struct BTreeNode));
                    p->data = string[i];
                    p->left = p->right = NULL;
                    if (*BT == NULL)
                        *BT = p;
                    else
                    {
                        if (k == 1)
                            s[top]->left = p;
                        else
                            s[top]->right = p;
                    }
                }
            }
            i++;
        }
    }