JavaScript Data Structure - Binary Tree

binary-tree.js

// Node
var Node = function(key) {
  this.key = key;
  this.parent = null;
  this.right = null;
  this.left = null;
}

Node.prototype = {
  getKey: function() { return this.key; }
  ,
  setKey: function(key) { this.key = key; }
  ,
  getParent: function() { return this.parent; }
  ,
  setParent: function(parent) { this.parent = parent; }
  ,
  getRight: function() { return this.right; }
  ,
  setRigth: function(right) { this.right = right; }
  ,
  getLeft: function() { return this.left; }
  ,
  setLeft: function(left) { this.left = left; }
  ,
  sibling: function() {
    if (this.parent === null) { return null; }
    if (this.parent.getRight() === this) { return this.parent.getLeft(); }
    else { return this.parent.getRigth(); }
  }
}

// Tree
var BinaryTree = function() {
  this.root = null;
}

BinaryTree.prototype = {
  traversal: function(node, option) {
    var left, right;
    
    if (node === null) {
      console.log("there is nothing in this tree.");
      return;
    }
    
    left = node.getLeft();
    right = node.getRigth();
    
    switch (option) {
      case 'in':
        this.traversal(left, option);
        console.log(node.getKey());
        this.traversal(right, option);
        return;
      case 'pre':
        console.log(node.getKey());
        this.traversal(left, option);
        this.traversal(right, option);
        return;
      case 'post':
        this.traversal(left, option);
        this.traversal(right, option);
        console.log(node.getKey());
        return;
      case 'level':
        var q = new Queue(); // from queue.js
        q.enqueue(this.root);
        while (q.size() !== 0) {
          var node, children;
          node = q.dequeue();
          console.log(node);
          children = [node.getLeft(), node.getRight()];
          for (var child in children) {
            if (child !== null) { q.enqueue(child); }
          }
        }
        return;
      default:
        console.log("please use proper option. option : 'in', 'pre', 'post', 'level'");
        break;
    }
  },
  
  search: function(node, key) {
    if (node === null || key === node.getKey()) { return node; }
    
    if (key < node.getKey()) { 
      return this.search(node.getLeft(), key); 
    } else { 
      return this.search(node.getRight(), key); 
    }
  },
  
  max: function(node) {
    if (node.getRight() === null) { return node; }
    return this.max(node.getRight());
  },
  
  min: function(node) {
    if (node.getLeft() === null) { return node; }
    return this.max(node.getLeft());
  },
  
  successor: function(node) {
    if (node.getRight() !== null) { return this.min(node.getRight()); }
    
    var parent = node.getParent();
    while (parent!==null && node===parent.getRight()) {
      node = parent;
      parent = parent.getParent();
    }
    return parent;
  },
  
  predecessor: function(node) {
    if (node.getLeft() !== null) { return this.max(node.getLeft()); }
    
    var parent = node.getParent();
    while (parent!==null && node===parent.getLeft()) {
      node = parent;
      parent = parent.getParent();
    }
    return parent;
  },
  
  insert: function(node) {
    var x, y;
    x = this.root;
    y = null;
    
    while (x !== null) {
      y = x;
      x = (node.getKey() < x.getKey()) ? x.getLeft() : x.getRight();
    }
    
    node.setParent(y);
    if (y === null) { this.root = node; }
    else if (node.getKey() < y.getKey()) { y.setLeft(node); }
    else { y.setRight(node); }
  },
  
  delete: function(node) {
    var, x, y;
    y = (node.getLeft() === null || node.getRight() === null) ? node : this.successor(node);
    x = (y.getLeft() !== null) ? y.getLeft() : y.getRight();
    
    if (x !== null) { x.setParent(y.getParent()); }
    
    if (y.getParent() === null) { this.root = x; }
    else if (y === y.getParent().getLeft()) { y.getParent().setLeft(x); }
    else { y.getParent().setRight(x); }
    
    if (y !== node) { node.setKey(y.getKey()); }
    
    return y;
  }
}