javascript线索化二叉树

定义二叉树创建方法

var Node = function (data) {
  this.left = null;
  this.right = null;
  this.LTag = 0;
  this.RTag = 0;
  this.data = data;
}

/**
 * createTree 
 * 采取递归方式创建二叉树
 * arr：二叉树结点数组，其中数字0表示为空节点
 */
function createTree (arr) {
  let data = arr.shift(),
      p = null;

  if (data != 0) {
    p = new Node(data);
    p.data = data;
    p.left = createTree(arr);
    p.right = createTree(arr);
    }

  return p;
}

对二叉树进行中序线索化

/**
 * middleTraverseThreading
 * 
 * 通过递归的方式对二叉树进行中序线索化
 *
 * node：当前结点
 * prev：父结点/前驱结点
 * next：后驱结点
 */
function middleTraverseThreading (node, prev, next) {
  if (node === null) return;

  // 如果是非叶子节点，递归
  if (node.LTag === 0) {
    // 递归左结点
    middleTraverseThreading(node.left, prev, node);
  }  

  // 如果左子树为空，让左子树指向前驱
  if (node.left === null) {
    node.LTag = 1;
    node.left = prev;
  }

  // 如果右子树为空，让右子树指向后驱
  if (node.right === null) {
    node.RTag = 1;
    node.right = next;
  }

  // 如果是非叶子节点，递归
  if (node.RTag === 0) {
    // 递归右节点
    middleTraverseThreading(node.right, node, next);
  }  

}

遍历线索二叉树

/**
 * 遍历线索二叉树
 *
 */
function traverseTree (root) {
  if (root === null) return;
  let p = root;

  // 找到最左边的叶子结点
  while(p.LTag === 0) {
    p = p.left;
  }

  // 从最左边的叶子结点开始遍历
  while (p !== root) {
    console.log(p.data);
    p = p.right;
  }

  // 打印根节点root
  console.log(p.data);

  p = p.right;
  // 从最左边的叶子结点开始遍历
  while (p !== root) {
    console.log(p.data);
    p = p.right;
  }

}

测试

let arr = [1,2,4,0,0,5,0,0,3,6,0,0,7,0,0],
root = createTree(arr);

// 对二叉树进行中序线索化
middleTraverseThreading(root, root, root);

// 遍历线索化二叉树
traverseTree(root);