javascript數據結構之多叉樹經典操作示例【創(chuàng)建、添加、遍歷、移除等】

2019-11-19 13:21:53

字體：大中小

來源：轉載

供稿：網友

本文實例講述了javascript數據結構之多叉樹經典操作。分享給大家供大家參考，具體如下：

多叉樹可以實現復雜的數據結構的存儲，通過遍歷方法可以方便高效的查找數據，提高查找的效率，同時方便管理節(jié)點數據。javascript的DOM其實就是以多叉樹的形式存儲的。下面用javascript來實現多叉樹的數據結構

1、創(chuàng)造一個節(jié)點

數據是以節(jié)點的形式存儲的：

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

2、創(chuàng)造樹

樹用來連接節(jié)點，就像真實世界樹的主干一樣，延伸著很多分支

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

3、添加一個節(jié)點

function add(data, toData, traversal) {  let node = new Node(data)  // 第一次添加到根節(jié)點  // 返回值為this，便于鏈式添加節(jié)點  if (this._root === null) {    this._root = node;    return this;  }  let parent = null,    callback = function(node) {      if (node.data === toData) {        parent = node;        return true;      }    };  // 根據遍歷方法查找父節(jié)點（遍歷方法后面會講到），然后把節(jié)點添加到父節(jié)點  // 的children數組里  // 查找方法contains后面會講到  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)先會盡量先從子節(jié)點查找，子節(jié)點查找完再從兄弟節(jié)點查找，適合數據深度比較大的情況，如文件目錄

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

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

廣度優(yōu)先遍歷會優(yōu)先查找兄弟節(jié)點，一層層往下找，適合子項較多情況，如公司崗位級別

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

6、包含節(jié)點

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

回調函數算法可自己根據情況實現，靈活度較高

7、移除節(jié)點

// 返回被移除的節(jié)點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實現:

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

控制臺測試代碼

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代碼運行工具：http://tools.VeVB.COm/code/HtmlJsRun測試運行效果如下：