数据结构题目36：根据将广义表形式表示的二叉树建立二叉链表存储结

题目：已知非空二叉树采用广义表形式作为输入，请写一算法，建立该二叉树的二叉链表存储结构。例如，一棵二叉树的广义表形式为A(B(D,E(G)),C(F(,H)))@

解题思路：
依次从广义表中取得一个元素，并对取得的元素做如下相应的处理：

1. 若当前取得的元素为字母，则按如下规则建立一个新的链结点。
   a) 若该结点为二叉树的根结点，则将该结点的地址送给T。
   b) 若该结点不是二叉树的根结点，则将该结点作为左孩子（若标志flag为1）或者右孩子（若flag为2）链接到其双亲结点上（此时双亲结点的地址在栈顶位置）。
2. 若当前取得的元素为左括号“(”，则表明一个子表开始，将标志flag设置为1，同时将前面那个结点的地址进栈。
3. 若当前取得的元素为右括号“）”，则表明一个子表结束，做退栈操作。
4. 若当前取得的元素为逗号，则表明以左孩子为根的子树处理完毕，接着应该处理以右孩子为根的子树，将标志flag置为2。
   如此处理广义表中的每一个元素，直到取得广义表的结束符号“@”为止。

具体算法如下：

class Node{
    constructor (data, lchild, rchild) {
        this.data = data,
        this.lchild = lchild
        this.rchild = rchild
    }
}

const MaxSize = 100 
function createBT(strBT) {
    let stack = new Array(MaxSize), p, T = null;
    let flag, top = -1
    let i = 0, len = strBT.length, ch
    while ( i<len ) {
        ch = strBT.charAt(i)
        switch (ch) {
            case '@':
                return T;
            case '(':
                stack[++top] = p
                flag = 1
                break;
            case ',':
                flag = 2
                break;
            case ')':
                top--
                break;
            default:
                p = new Node(ch, null, null)
                if ( T == null ) {
                    T = p
                } else if ( flag == 1 ) {
                    stack[top].lchild = p
                } else {
                    stack[top].rchild = p
                }
        }
        i++
    }
}

var strBT="A(B(D,E(G)),C(F(,H)))@"
createBT(strBT)