這篇文章主要講解了“javascript數(shù)據(jù)結(jié)構(gòu)之多叉樹怎么實現(xiàn)”，文中的講解內(nèi)容簡單清晰，易于學(xué)習(xí)與理解，下面請大家跟著小編的思路慢慢深入，一起來研究和學(xué)習(xí)“javascript數(shù)據(jù)結(jié)構(gòu)之多叉樹怎么實現(xiàn)”吧！

創(chuàng)新互聯(lián)專注為客戶提供全方位的互聯(lián)網(wǎng)綜合服務(wù)，包含不限于成都網(wǎng)站制作、成都做網(wǎng)站、廣南網(wǎng)絡(luò)推廣、重慶小程序開發(fā)、廣南網(wǎng)絡(luò)營銷、廣南企業(yè)策劃、廣南品牌公關(guān)、搜索引擎seo、人物專訪、企業(yè)宣傳片、企業(yè)代運營等，從售前售中售后，我們都將竭誠為您服務(wù)，您的肯定，是我們最大的嘉獎；創(chuàng)新互聯(lián)為所有大學(xué)生創(chuàng)業(yè)者提供廣南建站搭建服務(wù)，24小時服務(wù)熱線：028-86922220，官方網(wǎng)址：www.chinadenli.net

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

數(shù)據(jù)是以節(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，便于鏈?zhǔn)教砑庸?jié)點
  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é)點（遍歷方法后面會講到），然后把節(jié)點添加到父節(jié)點
  // 的children數(shù)組里
  // 查找方法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é)點查找，適合數(shù)據(jù)深度比較大的情況，如文件目錄

function traverseDF(callback) {
  let stack = [], found = false;
  stack.unshift(this._root);
  let currentNode = stack.shift();
  while(!found && currentNode) {
    // 根據(jù)回調(diào)函數(shù)返回值決定是否在找到第一個后繼續(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) {
    // 根據(jù)回調(diào)函數(shù)返回值決定是否在找到第一個后繼續(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);
}

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

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實現(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;
  }
}

控制臺測試代碼

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

運行效果如下：

感謝各位的閱讀，以上就是“javascript數(shù)據(jù)結(jié)構(gòu)之多叉樹怎么實現(xiàn)”的內(nèi)容了，經(jīng)過本文的學(xué)習(xí)后，相信大家對javascript數(shù)據(jù)結(jié)構(gòu)之多叉樹怎么實現(xiàn)這一問題有了更深刻的體會，具體使用情況還需要大家實踐驗證。這里是創(chuàng)新互聯(lián)，小編將為大家推送更多相關(guān)知識點的文章，歡迎關(guān)注！

網(wǎng)站欄目：javascript數(shù)據(jù)結(jié)構(gòu)之多叉樹怎么實現(xiàn)
文章源于：http://www.chinadenli.net/article28/jdhejp.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供標(biāo)簽優(yōu)化、定制網(wǎng)站、面包屑導(dǎo)航、動態(tài)網(wǎng)站、品牌網(wǎng)站制作、搜索引擎優(yōu)化

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源： 創(chuàng)新互聯(lián)