数据结构

二叉树的广义表表示方法

二叉树的广义表表示如下图所示:

根据广义表创建一颗二叉树:
  1. 若元素为字母,则创建一个新结点nest;
    • 若该结点不是二叉树的根结点,则将该结点作为左孩子(flag=’l’)或者右孩子(flag=’r’)链接到父结点上(即栈顶结点);
  2. 若元素为左括号,将flag置’l’,同时将结点nest压栈;
  3. 若元素为右括号,表明一个子表结束,做退栈操作;
  4. 若元素为逗号,表明以左孩子为根的子树处理完毕,将flag置’r’;
    如此处理直至完毕.
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    #include<cstdio>
    #include<cstdlib>
    #include<cstring>
    #include<stack>
    using namespace std;

    /**
    *    广义表建立二叉树
    */

    typedef char DATA_TYPE;

    typedef struct node
    {
        DATA_TYPE value;
        node *lchild, *rchild;
    } Node;

    stack<Node*> nodeStack;

    //释放内存
    void destroyTree(Node *h)
    {
        if(h)
        {
    //        printf("node = %c\n", h->value);
            destroyTree(h->lchild);
            printf("node = %c\n", h->value);
            destroyTree(h->rchild);
            free(h);
        }
    }

    //根据广义表表示来建立二叉树
    Node *buildTree(char nodeStr[])
    {
        Node *head = NULL, *nest = NULL;
        char flag = 'l';
        int i = 0;
        while(nodeStr[i] != '@')
        {
            switch(nodeStr[i])
            {
            case '(':
                flag = 'l';
                nodeStack.push(nest);
                break;
            case ')':
                nodeStack.pop();
                break;
            case ',':
                flag = 'r';
                break;
            default :
                nest = (Node*)malloc(sizeof(Node));
                nest->value= nodeStr[i];
                nest->lchild = nest->rchild=NULL;
                if(!nodeStack.empty() && flag == 'l')
                {
                    nodeStack.top()->lchild = nest;
                }
                else if(!nodeStack.empty() && flag=='r')
                {
                    nodeStack.top()->rchild=nest;
                }
                if(!head) head = nest;
            }
            i++;
        }
        return head;
    }



    int main()
    {
        char nodeStr[] = "a(b(d),c(f(,e),g))@";
        Node *h = buildTree(nodeStr);
        destroyTree(h);
        return 0;
    }

好久没写c语言了,感觉自己将它们全都忘光了.今天翻出来ppt看到广义表,就想动手写出来,没想到写完发现跟ppt上给的算法一模一样——–看来我不是忘记它们,而是我对自己没有信心,以为自己把它们全都忘记了.
写上一句话激励自己吧:
世上无难事,只要肯登攀!