题目:已知非空二叉树采用广义表形式作为输入,请写一算法,建立该二叉树的二叉链表存储结构。例如,一棵二叉树的广义表形式为A(B(D,E(G)),C(F(,H)))@
解题思路:
依次从广义表中取得一个元素,并对取得的元素做如下相应的处理:
- 若当前取得的元素为字母,则按如下规则建立一个新的链结点。
a) 若该结点为二叉树的根结点,则将该结点的地址送给T。
b) 若该结点不是二叉树的根结点,则将该结点作为左孩子(若标志flag为1)或者右孩子(若flag为2)链接到其双亲结点上(此时双亲结点的地址在栈顶位置)。 - 若当前取得的元素为左括号“(”,则表明一个子表开始,将标志flag设置为1,同时将前面那个结点的地址进栈。
- 若当前取得的元素为右括号“)”,则表明一个子表结束,做退栈操作。
- 若当前取得的元素为逗号,则表明以左孩子为根的子树处理完毕,接着应该处理以右孩子为根的子树,将标志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)