题目:在中序线索二叉树中确定地址为x结点的直接前驱结点
解题思路:确定过程具有如下规律:
1.当x->lbit=0(或x->lchild为负值)时,x->lchild所指的结点就是x的直接前驱结点。
2.当x->lbit=1(或x->lchild为正值)时,说明x结点有左子树,它的直接前驱结点应该是x结点的左子树中的最右边那个结点,即顺着x结点左子树的根的右指针链往下寻找,直到某结点的rchild域是线索为止。此时,该结点就是x所指结点的直接前驱结点。
具体算法如下:
function inprior(x) {
let s
s = x.lchild
if ( x.lbit ==1 ) {
while ( s.rbit==1 ) {
s = s.rchild
}
}
return s
}
测试:考虑使用二叉树的线索化构造.