JavaScript数据结构11——线索二叉树的遍历

线索二叉树包括了

• 将一个二叉树转为线索二叉树
• 建立一个头结点，形成循环双向链表
• 遍历二叉树

//线索二叉树
function BiTrNode(data) {
    this.data = data;
    this.lTag = 1;
    this.rTag = 1;
}
BiTrNode.prototype.setlChild = function(tag,node){
    this.lTag = tag;
    this.lChild = node;
}
BiTrNode.prototype.setRChild = function(tag,node){
    this.rTag = tag;
    this.rChild = node;
}
var Threading = {
    preBiTrTree:null,
    start:null,
    end:null
}
Threading.inThreadingB = function(biTrTree){
    if(biTrTree){
        console.info('当前到达节点'+biTrTree.data);
        this.inThreadingB(biTrTree.lChild);
        if(!biTrTree.lChild){
            console.info(biTrTree.data+' 没有左节点信息')
            biTrTree.lTag = 0;//0代表线索，1代表子树
            biTrTree.lChild = this.preBiTrTree;
            if(!this.preBiTrTree){
                this.start = biTrTree;
            }
            console.info(biTrTree.data+' 左节点赋为'+
                (this.preBiTrTree==null?'空指针':this.preBiTrTree.data));
        }
        if(this.preBiTrTree&&!this.preBiTrTree.rChild){
            console.info(this.preBiTrTree.data+' 没有右节点信息')
            this.preBiTrTree.rTag = 0;
            this.preBiTrTree.rChild = biTrTree;
            console.info(this.preBiTrTree.data+' 右节点赋为'+
                (biTrTree==null?'空指针':biTrTree.data));
        }
        this.preBiTrTree = biTrTree;
        this.end = biTrTree;
        this.inThreadingB(biTrTree.rChild);
    }
}
//中序遍历线索化
Threading.inThreadingA = function(biTrTree){
    this.inThreadingB(biTrTree);
    var T = new BiTrNode(null);
    T.setlChild(0,this.start);
    T.setRChild(1,this.end);
    this.start.lChild = T;
    this.end.rChild = T;
    return T;
}
//遍历二叉树
Threading.inOrderTraverse = function(T){
    var p = T.lChild;
    while(p!=T){
        while(p.lTag ==1){
            p = p.lChild;
        }
        console.info(p.data);
        while(p.rTag==0&&p.rChild!=T){
            p = p.rChild;
            console.info(p.data);
        }
        p =p.rChild;
    }
}
var a = new BiTrNode('a');
var b = new BiTrNode('b');
var c = new BiTrNode('c');
var d = new BiTrNode('d');
var e = new BiTrNode('e');
var f = new BiTrNode('f');
var g = new BiTrNode('g');
var h = new BiTrNode('h');
var i = new BiTrNode('i');
var j = new BiTrNode('j');
a.setlChild(1,b);
a.setRChild(1,c);
b.setlChild(1,d);
b.setRChild(1,e);
d.setlChild(1,h);
d.setRChild(1,i);
e.setlChild(1,j);
c.setlChild(1,f);
c.setRChild(1,g);
var r = Threading.inThreadingA(a);
Threading.inOrderTraverse(r);

控制台输出

当前到达节点a
当前到达节点b
当前到达节点d
当前到达节点h
h 没有左节点信息
h 左节点赋为空指针
h 没有右节点信息
h 右节点赋为d
当前到达节点i
i 没有左节点信息
i 左节点赋为d
i 没有右节点信息
i 右节点赋为b
当前到达节点e
当前到达节点j
j 没有左节点信息
j 左节点赋为b
j 没有右节点信息
j 右节点赋为e
e 没有右节点信息
e 右节点赋为a
当前到达节点c
当前到达节点f
f 没有左节点信息
f 左节点赋为a
f 没有右节点信息
f 右节点赋为c
当前到达节点g
g 没有左节点信息
g 左节点赋为c
hdibjeafcg
[Finished in 0.1s]