数据结构JavaScript描述（三）

摘要：有关算法，数据结构的代码已上传至算法与数据结构。构造函数深度优先遍历广度优先遍历插入中序遍历前序遍历后序遍历声明一棵树声明一个节点相关算法深度优先遍历深度优先遍历，先查看左孩子是否存在，若存在，传入递归，否则，再查看右孩子。

这次来了解一下二叉树，以及相应的算法。以下代码并非所有都由本人所写，只是在此分享出来，以便大家学习。

有关javascript算法，数据结构的代码已上传至 javascript算法与数据结构。

/**
 *        使用js实现一个二叉树。
 *        Tree        构造函数
 *        traverseDF  深度优先遍历
 *        traverseBF  广度优先遍历
 *        insert      插入
 *        inOrderTraverse中序遍历
 *        preOrderTraverse前序遍历
 *        postOderTraverse后序遍历
 */

声明一棵树：

function Tree () {
    this._root;
}

声明一个节点：

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

/**
 *    深度优先遍历，先查看左孩子是否存在，若存在，传入recurse递归，
 *    否则，再查看右孩子。若都不存在，对该节点执行callback操作。
 */
Tree.prototype.traverseDF = function (callback) {
  (function recurse (currentNode) {
     if (currentNode.left) {
       recurse(currentNode.left);
     }
     if (currentNode.right) {
       recurse(currentNode.right);
     }
     callback(currentNode);
  })(this._root)
}

/**
 *    宽度优先遍历借助队列来实现。
 */
Tree.prototype.traverseBF = function (callback) {
  var queue = new Queue();
  if (!this._root) {
    console.log("empty tree");
    return;
  }
  queue.enqueue(this._root);
  var currentNode = queue.dequeue();
  while (currentNode) {
    if (currentNode.left) {
      queue.enqueue(currentNode.left);
    }
    if (currentNode.right) {
      queue.enqueue(currentNode.right);
    }
    callback(currentNode);
    currentNode = queue.dequeue();
  }
}

/**
 *     插入节点用到了宽度优先遍历的思想
 */

Tree.prototype.insert = function (data) {
    var node = new Node(data);
    var message = {
        success: "Inserted successfully!",
    }
    if (!this._root) {
        this._root = node;
        return;
    }
    var queue = new Queue();
    queue.enqueue(this._root);
    var currentNode = queue.dequeue();
    while (currentNode) {
        if (currentNode.left) {
            queue.enqueue(currentNode.left);
        } else {
            currentNode.left = node;
            console.log(message.success);
            return;
        }
        if (currentNode.right) {
            queue.enqueue(currentNode.right);
        } else {
            currentNode.right = node;
            console.log(message.success);
            return;
        } 
        currentNode = queue.dequeue();
    }
}

/**
 *     中序遍历
 */
Tree.prototype.forInOrder = function (node) {
    if (node) {
        this.forInOrder(node.left);
        console.log(node.data);
        this.forInOrder(node.right);
    }
}

Tree.prototype.inOrderTraverse = function () {
    this.forInOrder(this._root);
}

中序遍历的非递归算法

/**
 *   借助一个栈，先沿着左子树到叶节点，依次入栈，
 * 再出栈遍历，对该栈顶节点的右子树进行统一的操作
 */

Tree.prototype.inOrder = function (callback) {
  var currentNode = null;
  if (this.root) {
    currentNode = root;
  } else {
    return;
  }
  var stack = [];
  do {
    while (currentNode != null) {
      stack.push(currentNode);
      currentNode = currentNode.left;
    }
    if (!stack.length) {
      stack.pop(currentNode);
      callback(currentNode);
      currentNode = currentNode.right;
    }
  } while (currentNode !== null && stack.length)
}

/**
 *    前序遍历
 */
Tree.prototype.forPreOrder = function (node) {
    if (node) {
        console.log(node.data);
        this.forPreOrder(node.left);
        this.forPreOrder(node.right);
    }
}

Tree.prototype.preOrderTraverse = function () {
    this.forPreOrder(this._root);
}

当然还有前序遍历的非递归算法。

/**
 *  算法关键思想是用栈为右子树预留位置。
 *  可以利用数组作为一个栈。
 */
Tree.prototype.preOrder = function (callback) {
  var currentNode = null;
  if (this.root) {
    currentNode = this.root;
  } else {
    return;
  }
  var stack = [];
  while (currentNode) {
    callback(currentNode);
    if (currentNode.right) {
      stack.push(currentNode.right);
    }
    if (currentNode.left) {
      currentNode = currentNode.left;
    } else {
      currentNode = stack.pop();
    }
  }
}

/**
 *    后序遍历
 */
Tree.prototype.forPostOrder = function (node) {
    if (node) {
        this.forPostOrder(node.left);
        this.forPostOrder(node.right);
        console.log(node.data);
    }
}

Tree.prototype.postOderTraverse = function () {
    this.forPostOrder(this._root);
}

function Queue () {
    this._oldestIndex = 1;
    this._newestIndex = 1;
    this._storage = {};
}

Queue.prototype.enqueue = function (data) {
    this._storage[this._newestIndex] = data;
    this._newestIndex++;
}

Queue.prototype.dequeue = function () {
    var oldestIndex = this._oldestIndex,
        newestIndex = this._newestIndex,
        deletedData;
    if (oldestIndex !== newestIndex) {
        deletedData = this._storage[oldestIndex];
        delete this._storage[oldestIndex];
        this._oldestIndex++;
        return deletedData;
    }
    return null;
}