数组构建二叉树

build_binary_tree_with_array.js

function Node(value) {
  this.value = value;
  this.left = null;
  this.right = null;
}

function build_btree(number_array) {  
  length = number_array.length;
  middle = Math.floor((0 + length - 1) / 2);
  root = new Node(number_array[middle]);
  build(number_array, root, 0, middle - 1, middle + 1, length - 1);
  return root;
}

function build(number_array, middle_node, left_begin, left_end, right_begin, right_end) {
  if (left_begin == left_end) {
    left_node = new Node(number_array[left_begin]);
    middle_node.left = left_node;
  } else if (left_begin < left_end) {
    left_middle = Math.floor((left_begin + left_end) / 2);
    left_middle_node = new Node(number_array[left_middle]);
    middle_node.left = left_middle_node;
    build(number_array, left_middle_node, left_begin, left_middle - 1, left_middle + 1, left_end);
  }
  
  if (right_begin == right_end) {
    right_node = new Node(number_array[right_begin]);
    middle_node.right = right_node;
  } else if (right_begin < right_end) {
    right_middle = Math.floor((right_begin + right_end) / 2);
    right_middle_node = new Node(number_array[right_middle]);
    middle_node.right = right_middle_node;
    build(number_array, right_middle_node, right_begin, right_middle - 1, right_middle + 1, right_end);
  }
}

function preorder_travel(root) {
  if (root === null) {
    return;
  }
  console.log(root.value);
  preorder_travel(root.left);
  preorder_travel(root.right);
}

function midorder_travel(root) {
  if (root === null) {
    return;
  }
  midorder_travel(root.left);
  console.log(root.value);
  midorder_travel(root.right);
}

function postorder_travel(root) {
  if (root === null) {
    return;
  }
  postorder_travel(root.left);  
  postorder_travel(root.right);
  console.log(root.value);
}

var number_array = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9];
btree = build_btree(number_array);
preorder_travel(btree);
midorder_travel(btree);
postorder_travel(btree);