线索二叉树

// 线索存储标志位
// 0 表示指向左右孩子的指针
// 1 表示指向前驱后继的线索
var LINK = 0
var THREAD = 1

// 结构
function BinaryThreadTree_inOrder(data, leftChild, rightChild) {
  this.data = data
  this.leftChild = leftChild || null
  this.rightChild = rightChild || null
  // 相对于普通二叉树新增了左右标记
  this.leftTag = this.rightTag = undefined
}

BinaryThreadTree_inOrder.prototype = {

  constructor: BinaryThreadTree_inOrder,

  // 中序线索二叉树的遍历
  inOrderTraverse_thread: function (visit) {
    var p = this.leftChild

    while (p != this) {
      while (p.leftTag === LINK) p = p.leftChild

      if (visit(p.data) === false) return

      while (p.rightTag == THREAD && p.rightChild != this) {
        p = p.rightChild
        visit(p.data)
      }
      p = p.rightChild
    }
  },

  // 中序线索化
  inOrderThreading: function () {
    return inOrderThreading(this)
  },

  // 在当前结点插入子树 x，p 代表当前结点
  insertSubTree: function (xTree) {
    var s, q
    // x 作为 p 的左子树
    if (this.leftTag === THREAD) {
      // s 为 p 的前驱
      s = this.leftChild
      this.leftTag = LINK
      this.leftChild = xTree
      q = xTree

      while (q.leftChild && q.leftTag === LINK) q = q.leftChild
      // 找到子树中的最左结点，并修改其前驱指向 s
      q.leftChild = s

      xTree.rightTag = THREAD

      // x 的后继指向 p
      xTree.rightChild = this

    // x 作为 p 的右子树
    } else if (this.rightTag === THREAD) {
      // s 为 p 的后继
      s = this.rightChild
      this.rightTag = LINK
      this.rightChild = xTree
      q = xTree

      while (q.leftChild && q.leftTag === LINK) q = q.leftChild
      
      // 找到子树中的最左结点，并修改其前驱指向 p
      q.leftChild = this
      xTree.rightTag = THREAD

      // x 的后继指向 p 的后继
      xTree.rightChild = s

    // x 作为 p 的左子树，p 的左子树作为 x 的右子树
    } else {
      s = this.leftChild
      var t = s

      while (t.leftChild && t.leftTag === LINK) t = t.leftChild
      // 找到 p 的左子树的最左结点 t 和前驱 u
      var u = t.leftChild

      this.leftChild = xTree
      xTree.rightTag = LINK
      
      // x 作为 p 的左子树，p 的左子树作为 x 的右子树
      xTree.rightChild = s
      t.leftChild = xTree
      q = xTree

      while (q.leftChild && q.leftTag === LINK) q = q.leftChild
      // 找到子树中的最左结点，并修改其前驱指向 u
      q.leftChild = u
    }
  }
}

// 二叉树中序线索化
function inOrderThreading(tree) {
  var threadTree = new BinaryThreadTree()
  threadTree.leftTag = LINK
  threadTree.rightTag = THREAD
  
  // 右指针回指
  threadTree.rightChild = threadTree

  var pre
  // 若二叉树为空，左指针回指
  if (!tree) {
    threadTree.leftChild = threadTree
  } else {
    threadTree.leftChild = tree
    pre = threadTree

    // 中序遍历进行中序线索化
    inThreading(tree)

    // 最后一个结点线索化
    pre.rightChild = threadTree
    pre.rightTag = THREAD
    threadTree.rightChild = pre
  }

  return threadTree

  function inThreading(p) {
    if (!p) return

    // 左子树线索化
    inThreading(p.leftChild)

    // 前驱线索
    if (!p.leftChild) {
      p.leftTag = THREAD
      p.leftChild = pre
    }

    // 后继线索
    if (!pre.rightChild) {
      pre.rightTag = THREAD
      pre.rightChild = p
    }

    pre = p

    // 右子树线索化
    inThreading(p.rightChild)
  }
}