欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

javascript數(shù)據(jù)結(jié)構(gòu)之多叉樹(shù)經(jīng)典操作示例【創(chuàng)建、添加、遍歷、移除等】

 更新時(shí)間:2018年08月01日 10:51:54   作者:winjowind  
這篇文章主要介紹了javascript數(shù)據(jù)結(jié)構(gòu)之多叉樹(shù)經(jīng)典操作,簡(jiǎn)單描述了多叉樹(shù)的概念,并結(jié)合實(shí)例形式分析了javascript多叉樹(shù)的創(chuàng)建、添加、遍歷、移除等常見(jiàn)操作方法,需要的朋友可以參考下

本文實(shí)例講述了javascript數(shù)據(jù)結(jié)構(gòu)之多叉樹(shù)經(jīng)典操作。分享給大家供大家參考,具體如下:

多叉樹(shù)可以實(shí)現(xiàn)復(fù)雜的數(shù)據(jù)結(jié)構(gòu)的存儲(chǔ),通過(guò)遍歷方法可以方便高效的查找數(shù)據(jù),提高查找的效率,同時(shí)方便管理節(jié)點(diǎn)數(shù)據(jù)。javascript的DOM其實(shí)就是以多叉樹(shù)的形式存儲(chǔ)的。下面用javascript來(lái)實(shí)現(xiàn)多叉樹(shù)的數(shù)據(jù)結(jié)構(gòu)

1、創(chuàng)造一個(gè)節(jié)點(diǎn)

數(shù)據(jù)是以節(jié)點(diǎn)的形式存儲(chǔ)的:

class Node {
  constructor(data) {
    this.data = data;
    this.parent = null;
    this.children = [];
  }
}

2、創(chuàng)造樹(shù)

樹(shù)用來(lái)連接節(jié)點(diǎn),就像真實(shí)世界樹(shù)的主干一樣,延伸著很多分支

class MultiwayTree {
  constructor() {
    this._root = null;
  }
}

3、添加一個(gè)節(jié)點(diǎn)

function add(data, toData, traversal) {
  let node = new Node(data)
  // 第一次添加到根節(jié)點(diǎn)
  // 返回值為this,便于鏈?zhǔn)教砑庸?jié)點(diǎn)
  if (this._root === null) {
    this._root = node;
    return this;
  }
  let parent = null,
    callback = function(node) {
      if (node.data === toData) {
        parent = node;
        return true;
      }
    };
  // 根據(jù)遍歷方法查找父節(jié)點(diǎn)(遍歷方法后面會(huì)講到),然后把節(jié)點(diǎn)添加到父節(jié)點(diǎn)
  // 的children數(shù)組里
  // 查找方法contains后面會(huì)講到
  this.contains(callback, traversal);
  if (parent) {
    parent.children.push(node);
    node.parent = parent;
    return this;
  } else {
    throw new Error('Cannot add node to a non-existent parent.');
  }
}

4、深度優(yōu)先遍歷

深度優(yōu)先會(huì)盡量先從子節(jié)點(diǎn)查找,子節(jié)點(diǎn)查找完再?gòu)男值芄?jié)點(diǎn)查找,適合數(shù)據(jù)深度比較大的情況,如文件目錄

function traverseDF(callback) {
  let stack = [], found = false;
  stack.unshift(this._root);
  let currentNode = stack.shift();
  while(!found && currentNode) {
    // 根據(jù)回調(diào)函數(shù)返回值決定是否在找到第一個(gè)后繼續(xù)查找
    found = callback(currentNode) === true ? true : false;
    if (!found) {
      // 每次把子節(jié)點(diǎn)置于堆棧最前頭,下次查找就會(huì)先查找子節(jié)點(diǎn)
      stack.unshift(...currentNode.children);
      currentNode = stack.shift();
    }
  }
}

5、廣度優(yōu)先遍歷

廣度優(yōu)先遍歷會(huì)優(yōu)先查找兄弟節(jié)點(diǎn),一層層往下找,適合子項(xiàng)較多情況,如公司崗位級(jí)別

function traverseBF(callback) {
  let queue = [], found = false;
  queue.push(this._root);
  let currentNode = queue.shift();
  while(!found && currentNode) {
    // 根據(jù)回調(diào)函數(shù)返回值決定是否在找到第一個(gè)后繼續(xù)查找
    found = callback(currentNode) === true ? true : false;
    if (!found) {
      // 每次把子節(jié)點(diǎn)置于隊(duì)列最后,下次查找就會(huì)先查找兄弟節(jié)點(diǎn)
      queue.push(...currentNode.children)
      currentNode = queue.shift();
    }
  }
}

6、包含節(jié)點(diǎn)

function contains(callback, traversal) {
  traversal.call(this, callback);
}

回調(diào)函數(shù)算法可自己根據(jù)情況實(shí)現(xiàn),靈活度較高

7、移除節(jié)點(diǎn)

// 返回被移除的節(jié)點(diǎn)
function remove(data, fromData, traversal) {
  let parent = null,
    childToRemove = null,
    callback = function(node) {
      if (node.data === fromData) {
        parent = node;
        return true;
      }
    };
  this.contains(callback, traversal);
  if (parent) {
    let index = this._findIndex(parent.children, data);
    if (index < 0) {
      throw new Error('Node to remove does not exist.');
    } else {
      childToRemove = parent.children.splice(index, 1);
    }
  } else {
    throw new Error('Parent does not exist.');
  }
  return childToRemove;
}

_findIndex實(shí)現(xiàn):

function _findIndex(arr, data) {
  let index = -1;
  for (let i = 0, len = arr.length; i < len; i++) {
    if (arr[i].data === data) {
      index = i;
      break;
    }
  }
  return index;
}

完整算法

class Node {
  constructor(data) {
    this.data = data;
    this.parent = null;
    this.children = [];
  }
}
class MultiwayTree {
  constructor() {
    this._root = null;
  }
  //深度優(yōu)先遍歷
  traverseDF(callback) {
    let stack = [], found = false;
    stack.unshift(this._root);
    let currentNode = stack.shift();
    while(!found && currentNode) {
      found = callback(currentNode) === true ? true : false;
      if (!found) {
        stack.unshift(...currentNode.children);
        currentNode = stack.shift();
      }
    }
  }
  //廣度優(yōu)先遍歷
  traverseBF(callback) {
    let queue = [], found = false;
    queue.push(this._root);
    let currentNode = queue.shift();
    while(!found && currentNode) {
      found = callback(currentNode) === true ? true : false;
      if (!found) {
        queue.push(...currentNode.children)
        currentNode = queue.shift();
      }
    }
  }
  contains(callback, traversal) {
    traversal.call(this, callback);
  }
  add(data, toData, traversal) {
    let node = new Node(data)
    if (this._root === null) {
      this._root = node;
      return this;
    }
    let parent = null,
      callback = function(node) {
        if (node.data === toData) {
          parent = node;
          return true;
        }
      };
    this.contains(callback, traversal);
    if (parent) {
      parent.children.push(node);
      node.parent = parent;
      return this;
    } else {
      throw new Error('Cannot add node to a non-existent parent.');
    }
  }
  remove(data, fromData, traversal) {
    let parent = null,
      childToRemove = null,
      callback = function(node) {
        if (node.data === fromData) {
          parent = node;
          return true;
        }
      };
    this.contains(callback, traversal);
    if (parent) {
      let index = this._findIndex(parent.children, data);
      if (index < 0) {
        throw new Error('Node to remove does not exist.');
      } else {
        childToRemove = parent.children.splice(index, 1);
      }
    } else {
      throw new Error('Parent does not exist.');
    }
    return childToRemove;
  }
  _findIndex(arr, data) {
    let index = -1;
    for (let i = 0, len = arr.length; i < len; i++) {
      if (arr[i].data === data) {
        index = i;
        break;
      }
    }
    return index;
  }
}

控制臺(tái)測(cè)試代碼

var tree = new MultiwayTree();
tree.add('a')
  .add('b', 'a', tree.traverseBF)
  .add('c', 'a', tree.traverseBF)
  .add('d', 'a', tree.traverseBF)
  .add('e', 'b', tree.traverseBF)
  .add('f', 'b', tree.traverseBF)
  .add('g', 'c', tree.traverseBF)
  .add('h', 'c', tree.traverseBF)
  .add('i', 'd', tree.traverseBF);
console.group('traverseDF');
tree.traverseDF(function(node) {
  console.log(node.data);
});
console.groupEnd('traverseDF');
console.group('traverseBF');
tree.traverseBF(function(node) {
  console.log(node.data);
});
console.groupEnd('traverseBF');
// 深度優(yōu)先查找
console.group('contains1');
tree.contains(function(node) {
  console.log(node.data);
  if (node.data === 'f') {
    return true;
  }
}, tree.traverseDF);
console.groupEnd('contains1')
// 廣度優(yōu)先查找
console.group('contains2');
tree.contains(function(node) {
  console.log(node.data);
  if (node.data === 'f') {
    return true;
  }
}, tree.traverseBF);
console.groupEnd('contains2');
tree.remove('g', 'c', tree.traverseBF);

這里使用在線HTML/CSS/JavaScript代碼運(yùn)行工具http://tools.jb51.net/code/HtmlJsRun測(cè)試運(yùn)行效果如下:

感興趣的朋友可以自己測(cè)試一下看看運(yùn)行效果。

更多關(guān)于JavaScript相關(guān)內(nèi)容感興趣的讀者可查看本站專題:《JavaScript數(shù)據(jù)結(jié)構(gòu)與算法技巧總結(jié)》、《JavaScript數(shù)學(xué)運(yùn)算用法總結(jié)》、《JavaScript排序算法總結(jié)》、《JavaScript遍歷算法與技巧總結(jié)》、《JavaScript查找算法技巧總結(jié)》及《JavaScript錯(cuò)誤與調(diào)試技巧總結(jié)

希望本文所述對(duì)大家JavaScript程序設(shè)計(jì)有所幫助。

相關(guān)文章

  • 小程序安全指南之如何禁止外部直接跳轉(zhuǎn)到小程序某頁(yè)面

    小程序安全指南之如何禁止外部直接跳轉(zhuǎn)到小程序某頁(yè)面

    由于小程序跳轉(zhuǎn)的對(duì)象比較多,各自的規(guī)則又不一樣,因此小程序跳轉(zhuǎn)外部鏈接是用戶咨詢較多的問(wèn)題之一,下面這篇文章主要給大家介紹了關(guān)于小程序安全指南之如何禁止外部直接跳轉(zhuǎn)到小程序某頁(yè)面的相關(guān)資料,需要的朋友可以參考下
    2022-09-09
  • javascript 一段代碼引發(fā)的思考

    javascript 一段代碼引發(fā)的思考

    寫(xiě)在前面:這是一個(gè)關(guān)于Ext, Prototype, JavaScript方面的問(wèn)題,其實(shí)下面遇到的問(wèn)題本不是問(wèn)題,都是因?yàn)殄e(cuò)誤的理解造成的,本文的宗旨是希望讀者朋友避免我犯的同類錯(cuò)誤,遇事三思而后行,同時(shí)也體會(huì)下發(fā)現(xiàn)問(wèn)題,解決問(wèn)題,反思問(wèn)題這種精神活動(dòng)所帶來(lái)的快樂(lè)!
    2009-01-01
  • 原生js事件的添加和刪除的封裝

    原生js事件的添加和刪除的封裝

    在IE瀏覽器中添加或刪除事件用attachEvent、detachEvent,下面的對(duì)事件的添加和刪除做了封裝,感興趣的朋友可以參考下
    2014-07-07
  • JavaScript中如何計(jì)算字符串文本的寬度

    JavaScript中如何計(jì)算字符串文本的寬度

    這篇文章主要介紹了JavaScript中如何計(jì)算字符串文本的寬度問(wèn)題,具有很好的參考價(jià)值,希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方,望不吝賜教
    2023-02-02
  • 微信小程序中為什么使用var that=this

    微信小程序中為什么使用var that=this

    這篇文章主要介紹了小程序中為什么使用var that=this的相關(guān)知識(shí),本文通過(guò)示例代碼給大家介紹的非常詳細(xì),具有一定的參考借鑒價(jià)值,需要的朋友可以參考下
    2019-08-08
  • TypeScript基礎(chǔ)入門(mén)教程之三重斜線指令詳解

    TypeScript基礎(chǔ)入門(mén)教程之三重斜線指令詳解

    這篇文章主要給大家介紹了關(guān)于TypeScript基礎(chǔ)入門(mén)教程之三重斜線指令的相關(guān)資料,文中通過(guò)示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧
    2018-10-10
  • JavaScript仿微博發(fā)布信息案例

    JavaScript仿微博發(fā)布信息案例

    這篇文章主要為大家詳細(xì)介紹了JavaScript仿微博發(fā)布信息案例,具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下
    2016-11-11
  • 探索Emberjs制作一個(gè)簡(jiǎn)單的Todo應(yīng)用

    探索Emberjs制作一個(gè)簡(jiǎn)單的Todo應(yīng)用

    使用Emberjs制作一個(gè)簡(jiǎn)單的Todo應(yīng)用,需要的朋友可以參考下
    2012-11-11
  • 微信小程序自定義導(dǎo)航教程(兼容各種手機(jī))

    微信小程序自定義導(dǎo)航教程(兼容各種手機(jī))

    這篇文章主要給大家介紹了關(guān)于微信小程序自定義導(dǎo)航的相關(guān)內(nèi)容,文中通過(guò)示例代碼介紹的非常詳細(xì),兼容各種手機(jī),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧
    2018-12-12
  • TypeScript中的混合(Mixin)示例詳解

    TypeScript中的混合(Mixin)示例詳解

    由于TypeScrip中的類不支持多繼承,所以引入了混合(Mixin)的特性,可以間接實(shí)現(xiàn)多繼承的效果,這篇文章主要介紹了一文弄懂TypeScript中的混合(Mixin),需要的朋友可以參考下
    2023-09-09

最新評(píng)論