国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專欄INFORMATION COLUMN

數據結構JavaScript描述(三)

張遷 / 2717人閱讀

摘要:有關算法,數據結構的代碼已上傳至算法與數據結構。構造函數深度優先遍歷廣度優先遍歷插入中序遍歷前序遍歷后序遍歷聲明一棵樹聲明一個節點相關算法深度優先遍歷深度優先遍歷,先查看左孩子是否存在,若存在,傳入遞歸,否則,再查看右孩子。

這次來了解一下二叉樹,以及相應的算法。以下代碼并非所有都由本人所寫,只是在此分享出來,以便大家學習。

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

文章版權歸作者所有,未經允許請勿轉載,若此文章存在違規行為,您可以聯系管理員刪除。

轉載請注明本文地址:http://specialneedsforspecialkids.com/yun/93634.html

相關文章

  • 2017前端開發手冊-前端職位描述

    摘要:最常被大家稱呼的兩個職位名稱是前端開發者或者前端工程師。開發者描述具有和技能的開發人員的前端職位稱呼,不要求掌握和應用程序相關的知識。前端專家當一詞包含在職位名稱中時,這表示開發人員具有在前端技術中應用策略的豐富經驗。 以下是各種前端職稱的列表和說明。最常被大家稱呼的兩個職位名稱是前端開發者或者前端工程師。請記住,只要是稱呼中包含前端、client-side、web UI、HTML、C...

    李增田 評論0 收藏0
  • 2017前端開發手冊-前端職位描述

    摘要:最常被大家稱呼的兩個職位名稱是前端開發者或者前端工程師。開發者描述具有和技能的開發人員的前端職位稱呼,不要求掌握和應用程序相關的知識。前端專家當一詞包含在職位名稱中時,這表示開發人員具有在前端技術中應用策略的豐富經驗。 以下是各種前端職稱的列表和說明。最常被大家稱呼的兩個職位名稱是前端開發者或者前端工程師。請記住,只要是稱呼中包含前端、client-side、web UI、HTML、C...

    antyiwei 評論0 收藏0
  • 2017前端開發手冊-前端職位描述

    摘要:最常被大家稱呼的兩個職位名稱是前端開發者或者前端工程師。開發者描述具有和技能的開發人員的前端職位稱呼,不要求掌握和應用程序相關的知識。前端專家當一詞包含在職位名稱中時,這表示開發人員具有在前端技術中應用策略的豐富經驗。 以下是各種前端職稱的列表和說明。最常被大家稱呼的兩個職位名稱是前端開發者或者前端工程師。請記住,只要是稱呼中包含前端、client-side、web UI、HTML、C...

    OBKoro1 評論0 收藏0
  • Nicolas講算法:Computer Science in JavaScript

    摘要:使用來描述算法和數據結構的教程很少,目前市面上用描述算法和數據結構的書屈指可數,并且就我看過的那本而言我只看過數據結構與算法語言描述質量實在堪憂。 使用JavaScript來描述算法和數據結構的教程很少, 目前市面上用JS描述算法和數據結構的書屈指可數,并且就我看過的那本而言(我只看過《數據結構與算法 JavaScript 語言描述》)質量實在堪憂。碰巧有次看到Nicolas博客中的C...

    codergarden 評論0 收藏0

發表評論

0條評論

最新活動
閱讀需要支付1元查看
<