数据结构题目52：二叉树的线索化

题目：二叉树的线索化
对二叉树的线索化，就是把二叉树的二叉链表存储结构中结点的所有空指针域改造成指向某结点在某种遍历序列中的直接前驱结点或直接后继结点的过程，因此，因此，二叉树的线索化过程只能在对二叉树的遍历过程中进行。
下面给出二叉树的中序线索化的递归算法。

解题思路：算法中设有指针pointer，用来指向中序遍历过程中访问结点的直接前驱结点，prior的初值为头结点的指针：HEAD初始时指向头结点，但在算法执行过程中，HEAD总是指向当前访问的结点。

具体算法如下：

function inthread(HEAD) {
    let prior = HEAD
    if ( HEAD!=null ) {
        inthread(HEAD.lchild)
        if ( HEAD.rchild==null ) {
            HEAD.rbit = 0
        }
        if ( HEAD.lchild==null ) {
            HEAD.lchild = prior
            HEAD.lbit = 0
        }
        if ( prior.rbit == 0 ) {
            prior.rchild = HEAD
        }
        prior = HEAD
        inthread( HEAD.rchild )
    }
}

class Node{
    constructor(data, lchild, rchild, lbit, rbit){
        this.data = data
        this.lchild = lchild
        this.rchild = rchild
        this.lbit = 1
        this.rbit = 1
    }
}
var str = "ABC  DE  F  G   "
var ch = ''
var len = str.length, i=0
var T = buildBT()
function head(T) {
    var head = new Node()
    head.lchild = T
    head.lbit = 1
    head.rchild = head
    head.rbit = 1
    return head
}
var head = head(T)
inthread(head)