BinaryTree.js

/**
 * @author Jakub Melezinek
 * @class Binary tree implementation.
 * 
 * @public
 * @constructor
 * @param {String} name The name of the tree
 */
btv.BinaryTree = function(name) {
    
    /**
     * The name of the tree.
     * 
     * @private
     * @type {String}
     */           
    this.name = "tree"; // default name
    this.setName(name); // if parameter name is given
    
    /**
     * The root node of the tree.
     * 
     * @private
     * @type {btv.BinaryTreeNode}
     */   
    this.root = null;
}

/**
 * @public
 * @param {String} name
 */
btv.BinaryTree.prototype.setName = function(name) {
    if(name != null) {
        this.name = name.toString();
    }
}

/**
 * @public
 * @returns {String}
 */
btv.BinaryTree.prototype.getName = function() {
    return this.name;
}

/**
 * @public
 * @param {btv.BinaryTreeNode} root
 * @throws Throws exception if the given node has a parent.
 */
btv.BinaryTree.prototype.setRoot = function(root) {    
    // It is not necessary. Tree can mean subtree too, but static btv.BinaryTree.getIndex(btv.BinaryTreeNode) still count index from the root of whole tree.
    if(root !== null && !root.isRoot()) {
        throw new btv.BinaryTreeException("The given node has a parent. Cannot be the root of a tree!");
    }
    
    // unset old root
    if(this.getRoot() !== null) {
        this.getRoot().setParent(null);
    }

    this.root = root;
}

/**
 * @public
 * @returns {btv.BinaryTreeNode}
 */
btv.BinaryTree.prototype.getRoot = function() {
    return this.root;
}

/**
 * @public
 * @returns {Number}
 */
btv.BinaryTree.prototype.getCount = function() {
    return this.getCountRec(this.getRoot());
}

/**
 * @private
 * @param {btv.BinaryTreeNode} node
 * @returns {Number}
 */
btv.BinaryTree.prototype.getCountRec = function(node) {
    if(node == null) {
        return 0;
    }
    
    return 1 + this.getCountRec(node.getLeft()) + this.getCountRec(node.getRight()); 
}

/**
 * @public
 * @param {Number[]} array
 */
btv.BinaryTree.prototype.build = function(array) {
    if(array.length <= 0) {
        this.setRoot(null);
        return;
    }
    
    var node = (new btv.BinaryTreeNode(array[0]));
    this.setRoot(node);
    
    this.buildLeftRec(array, 1, node);
    this.buildRightRec(array, 2, node);
}

/**
 * @private
 * @param {Number[]} array
 * @param {Number} index
 * @param {btv.BinaryTreeNode} parent
 */
btv.BinaryTree.prototype.buildLeftRec = function(array, index, parent) {
    if(index > array.length - 1) {
        return;
    }
    
    var node = new btv.BinaryTreeNode(array[index]);
    parent.setLeft(node);
    
    this.buildLeftRec(array, index*2 + 1, node);
    this.buildRightRec(array, index*2 + 2, node);    
}

/**
 * @private
 * @param {Number[]} array
 * @param {Number} index
 * @param {btv.BinaryTreeNode} parent
 */
btv.BinaryTree.prototype.buildRightRec = function(array, index, parent) {
    if(index > array.length - 1) {
        return;
    }
    
    var node = new btv.BinaryTreeNode(array[index]);
    parent.setRight(node);
    
    this.buildLeftRec(array, index*2 + 1, node);
    this.buildRightRec(array, index*2 + 2, node);    
}

/**
 * @public
 * @param {btv.BinaryTreeNode} node1
 * @param {btv.BinaryTreeNode} node2
 * @returns {Boolean} Returns true if nodes was swapped succesfully.
 */
btv.BinaryTree.prototype.swapNodes = function(node1, node2) {
    if(node1 === node2 || node1 == null || node2 == null) {
        return false;
    }
    
    // siblings
    if(node1.getParent() === node2.getParent()) {
        var tmp;
        if(node1.getParent().getLeft() === node1) { // n1 is left child 
            tmp = node1;
            node2.getParent().setLeft(node2);
            node2.getParent().setRight(tmp);
        } else  { // n2 is left child
            tmp = node2;
            node1.getParent().setLeft(node1);
            node1.getParent().setRight(tmp);            
        }
        
        return true;
    }
    
    // child
    if(node1.getLeft() === node2 || node1.getRight() === node2) { // n1 is parent n2
        return this.swapParentChild(node1, node2);
    }
    
    if(node2.getLeft() === node1 || node2.getRight() === node1) { // n2 is parent n1
        return this.swapParentChild(node2, node1);
    }
    
    // descendant (but not a child)
    var parent = node1.getParent();
    while(parent != null) {
        if(parent === node2) { // n1 is descendant of n2
            return this.swapAncestorDescendant(node2, node1);
        }
        parent = parent.getParent();
    }
    
    parent = node2.getParent();
    while(parent != null) {
        if(parent === node1) { // n1 is descendant of n2
            return this.swapAncestorDescendant(node1, node2);
        }
        parent = parent.getParent();
    }
    
    // 2 subtrees => n1 nor n2 are root
    var node2Left = node2.getLeft();
    var node2Right = node2.getRight();
    
    // set node2's new children
    node2.setLeft(node1.getLeft());
    node2.setRight(node1.getRight());
    
    // set node1's new children
    node1.setLeft(node2Left);
    node1.setRight(node2Right);
    
    // now subtrees swapped
    // swap parents - n1 nor n2 are root
        
    var node1parent = node1.getParent();
    var node2parent = node2.getParent();
        
    if(node1parent.getLeft() === node1) {
        node1parent.setLeft(node2);
    } else {
        node1parent.setRight(node2);
    }
        
    if(node2parent.getLeft() === node2) {
        node2parent.setLeft(node1);
    } else {
        node2parent.setRight(node1);
    }
        
    return true;
}

/**
 * @private
 * @param {btv.BinaryTreeNode} parent
 * @param {btv.BinaryTreeNode} child
 * @returns {Boolean} Returns true. Doesn't chceck if given child is child of given parent.
 */
btv.BinaryTree.prototype.swapParentChild = function(parent, child) {
    
    var parentLeft = parent.getLeft();
    var parentRight = parent.getRight();
    
    // set parent's new child
    parent.setLeft(child.getLeft());
    parent.setRight(child.getRight());
        
    // set child's parent
    if(parent.isRoot()) {
        this.setRoot(child);
    } else {
        if(parent.getParent().getLeft() === parent) {
            parent.getParent().setLeft(child);
        } else {
            parent.getParent().setRight(child)
        }
    }
        
    // set child's children
    if(child === parentLeft) {
        child.setLeft(parent);
        child.setRight(parentRight);
    } else {
        child.setLeft(parentLeft);
        child.setRight(parent);
    }
    
    return true;
}

/**
 * @private
 * @param {btv.BinaryTreeNode} ancestor
 * @param {btv.BinaryTreeNode} descendant
 * @returns {Boolean} Returns true. Doesn't chceck if given child is child of given parent.
 */
btv.BinaryTree.prototype.swapAncestorDescendant = function(ancestor, descendant) {
    
    var ancestortLeft = ancestor.getLeft();
    var ancestorRight = ancestor.getRight();
    
    // set ancestor's new children
    ancestor.setLeft(descendant.getLeft());
    ancestor.setRight(descendant.getRight());
    
    
    var ancestorParent = ancestor.getParent();
    var descendantParent = descendant.getParent();
    var descendantIsLeftChild;
    
    if(descendantParent.getLeft() === descendant) { // descendantParent still refer to ancestor, used below
        descendantIsLeftChild = true;
    } else {
        descendantIsLeftChild = false;
    }    
    
    // set descendant's new children
    descendant.setLeft(ancestortLeft);
    descendant.setRight(ancestorRight);
    
    // now subtrees swapped
    // swap parents

    // descendant new parent
    if(ancestor.isRoot()) {
        if(descendantParent.getLeft() === descendant) {
            descendantParent.setLeft(null);
        } else {
            descendantParent.setRight(null);
        }
        this.setRoot(descendant);
    } else {
        if(ancestorParent.getLeft() === ancestor) { // ancestorParent still refer to ancestor
            ancestorParent.setLeft(descendant);
        } else {
            ancestorParent.setRight(descendant);
        }
    }
    
    // ancestor new parent
    if(descendantIsLeftChild) { // descendantParent do not refer to descendant, becouse descendant parent was set to ancestorParent
        descendantParent.setLeft(ancestor);
    } else {
        descendantParent.setRight(ancestor);
    }
}

/**
 * @public
 * @returns {btv.BinaryTreeNode[]}
 */
btv.BinaryTree.prototype.toInorderArray = function() {
    var array = new Array();
    
    if(this.root === null) {
        return null;
    }
    
    btv.BinaryTree.toInorderArrayRec(this.root, array);
    
    return array;
}

/**
 * @private
 * @param {btv.BinaryTreeNode} node
 * @param {Array} [array] Optional, if given push node to that array, otherwise create new array.
 * @returns {btv.BinaryTreeNode[]} Returns given or new array.
 */
btv.BinaryTree.toInorderArrayRec = function(node, array) {
    if(node === null) {
        return null;
    }
    
    if(array == null) { // null or undefined
        array = new Array
    }
    
    btv.BinaryTree.toInorderArrayRec(node.getLeft(), array);
    array.push(node);
    btv.BinaryTree.toInorderArrayRec(node.getRight(), array);
    
    return array;
}

/**
 * Simulate array implementation.
 *
 * @public
 * @returns {btv.BinaryTreeNode[]}
 */
btv.BinaryTree.prototype.toArray = function() {
    var array = new Array();

    if(this.getRoot() == null) {
        return array;
    }

    // pomoci getNode(index)
    var maxIndex = 0;
    var nullCount = 0;
    
    for(var i = 0; i <= maxIndex; i++) {
        array[i] = this.getNode(i);
        if(array[i] !== null) {
            maxIndex = 2*i + 2; // have to check left and right child
            nullCount = 0;
        } else {
            nullCount++;
        }
    }
    
    array.length -= nullCount; // trim nulls at the end
    return array;
}

/**
 * Simulate array implementation.
 *
 * @public
 * @param {Number} index
 * @throws Throws exception if this tree doesn't have root node.
 * @throws Throws exception if given index is negative.
 * @returns {btv.BinaryTreeNode}
 */
btv.BinaryTree.prototype.getNode = function(index) {
    if(this.getRoot() === null) {
        throw new btv.BinaryTreeException("This tree doesn't have a root node.");
    }
    if(index < 0) {
        throw new btv.BinaryTreeException("The index cannot be negative.");
    }
    
    var path = "";

    while(index != 0) {
        if(index % 2 == 1) { // odd => left child
            index = (index-1)/2;
            path += "L";
        }else { // even => left child
            index = (index-2)/2;
            path += "R";
        }
    }
    
    var node = this.getRoot();
    for(var i = path.length; i > 0; i--) { // backwards 
        if(path.charAt(i-1) == "L") {
            node = node.getLeft();
        } else {
            node = node.getRight();
        }
        if(node === null) {
            return null;
        }
    }
    return node;
}

/**
 * Simulate array implementation.
 * 
 * @public
 * @static
 * @param {btv.BinaryTreeNode} node
 * @throws Throws exception if given node is null.
 * @returns {Number} Index of given node.
 */
btv.BinaryTree.getIndex = function(node) {
    if(node === null) {
        throw new btv.BinaryTreeException("Given node is null.");
    }
    
    if(node.isRoot()) // root
        return 0;
    
    // recursion
    var parentIndex = node.getParent().getIndex(); 
    
    if(node.getParent().getLeft() === node) { // this is left child 
        return 2*parentIndex + 1;
    }
    else { // this is right child 
        return 2*parentIndex + 2;
    }
}

/**
 * @public
 * @override
 * @returns {String}
 */
btv.BinaryTree.prototype.toString = function() {
    return "[object btv.BinaryTree" +
    " <name: '" + this.getName() + "'" +
    " root: " + this.getRoot() + ">]";  
}



////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////



/**
 * @author Jakub Melezinek
 * @class Binary tree node implementation.
 * 
 * @public
 * @constructor   
 * @param {Number|String} value The value of the node
 */
btv.BinaryTreeNode = function(value) {
    
    /**
     * The value of this node.
     * 
     * @private
     * @type {Number|String}
     */     
    this.value = value;
    
    /**
     * The parent of this node.
     *
     * @private
     * @type {btv.BinaryTreeNode}
     */
    this.parent = null;
    
    /**
     * The left child of this node.
     *
     * @private
     * @type {btv.BinaryTreeNode}
     */
    this.left = null;
    
    /**
     * The right child of this node.
     *
     * @private
     * @type {btv.BinaryTreeNode}
     */
    this.right = null;
}

/**
 * @public
 * @returns {Number}
 */
btv.BinaryTreeNode.prototype.getValue = function() {
    return this.value;
}

/**
 * @public
 * @see static function btv.BinaryTree#getIndex
 * @returns {Number}
 */
btv.BinaryTreeNode.prototype.getIndex = function() {
    return btv.BinaryTree.getIndex(this);
}

/**
 * @public
 * @returns {Boolean}
 */
btv.BinaryTreeNode.prototype.isRoot = function() {
    if(this.getParent() === null) {
        return true;
    } else {
        return false;
    }
}

/**
 * @public
 * @returns {Boolean}
 */
btv.BinaryTreeNode.prototype.isLeaf = function() {
    if(this.getLeft() === null && this.getRight() === null) {
        return true;
    } else {
        return false;
    }
}

/**
 * For method setLeft(BinaryTreeNode) and setRight(BinaryTreeNode) only!
 * Unset old reference oldParent to thisNode and 
 * set new reference thisNode to newParent,
 * DO NOT set reference newParent to thisNode!
 * Use setLeft(BinaryTreeNode) or setRight(BinaryTreeNode).
 * 
 * @private
 * @see btv.BinaryTreeNode#setLeft
 * @see btv.BinaryTreeNode#setRight
 * @param {btv.BinaryTreeNode} parent
 */
btv.BinaryTreeNode.prototype.setParent = function(parent) {
    // unset old reference
    if(!this.isRoot()) { // has parent
        if(this.getParent().getLeft() === this) { // this is left child 
            this.getParent().left = null;
        }
        else {// this is right child 
            this.getParent().right = null;
        }
    }
    // set new reference
    this.parent = parent;
}

/**
 * @public
 * @returns {btv.BinaryTreeNode}
 */
btv.BinaryTreeNode.prototype.getParent = function() {
    return this.parent;
}


/**
 * Set left child and changes all needed references.
 * 
 * @public
 * @throws Throws an exception if this node is same as given node - try to set yourself as a child of yourself.
 * @param {btv.BinaryTreeNode} left
 */
btv.BinaryTreeNode.prototype.setLeft = function(left) {
    if(this === left) {
        throw new btv.BinaryTreeNodeException("A node cannot be a child of yourself.");
    }
    
    if(left !== null) {
        left.setParent(this);
    }
    
    if(this.getLeft() !== null) {
        this.getLeft().setParent(null);
    }
    
    this.left = left;
}

/**
 * @public
 * @returns {btv.BinaryTreeNode}
 */
btv.BinaryTreeNode.prototype.getLeft = function() {
    return this.left;
}

/**
 * Set right child and changes all needed references.
 *
 * @public
 * @throws Throws an exception if this node is same as given node - try to set yourself as a child of yourself.
 * @param {btv.BinaryTreeNode} right
 */
btv.BinaryTreeNode.prototype.setRight = function(right) {
    if(this === right) {
        throw new btv.BinaryTreeNodeException("A node cannot be a child of yourself.");
    }
    
    if(right !== null) {
        right.setParent(this);
    }
    
    if(this.getRight() !== null) {
        this.getRight().setParent(null);
    }
    
    this.right = right;
}

/**
 * @public
 * @returns {btv.BinaryTreeNode}
 */
btv.BinaryTreeNode.prototype.getRight = function() {
    return this.right;
}

/**
 * @public
 * @override
 * @returns {String}
 */
btv.BinaryTreeNode.prototype.toString = function() {
    return "[object btv.BinaryTreeNode <value: " + this.getValue() + ", index: " + this.getIndex() + ">]";
}