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

有关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;}