javascript数据结构之多叉树经典操作示例【创建、添加、遍历、移除等】

本文实例讲述了javascript数据结构之多叉树经典操作。分享给大家供大家参考,具体如下:

多叉树可以实现复杂的数据结构的存储,通过遍历方法可以方便高效的查找数据,提高查找的效率,同时方便管理节点数据。javascript的DOM其实就是以多叉树的形式存储的。下面用javascript来实现多叉树的数据结构

1、创造一个节点

数据是以节点的形式存储的:

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

2、创造树

树用来连接节点,就像真实世界树的主干一样,延伸着很多分支

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

3、添加一个节点

function add(data, toData, traversal) {
  let node = new Node(data)
  // 第一次添加到根节点
  // 返回值为this,便于链式添加节点
  if (this._root === null) {
    this._root = node;
    return this;
  }
  let parent = null,
    callback = function(node) {
      if (node.data === toData) {
        parent = node;
        return true;
      }
    };
  // 根据遍历方法查找父节点(遍历方法后面会讲到),然后把节点添加到父节点
  // 的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、深度优先遍历

深度优先会尽量先从子节点查找,子节点查找完再从兄弟节点查找,适合数据深度比较大的情况,如文件目录

function 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();
    }
  }
}

5、广度优先遍历

广度优先遍历会优先查找兄弟节点,一层层往下找,适合子项较多情况,如公司岗位级别

function 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();
    }
  }
}

6、包含节点

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

回调函数算法可自己根据情况实现,灵活度较高

7、移除节点

// 返回被移除的节点
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;
  }
  //深度优先遍历
  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();
      }
    }
  }
  //广度优先遍历
  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');
// 深度优先查找
console.group('contains1');
tree.contains(function(node) {
  console.log(node.data);
  if (node.data === 'f') {
    return true;
  }
}, tree.traverseDF);
console.groupEnd('contains1')
// 广度优先查找
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.jb51.net/code/HtmlJsRun测试运行效果如下:

感兴趣的朋友可以自己测试一下看看运行效果。

更多关于JavaScript相关内容感兴趣的读者可查看本站专题:《JavaScript数据结构与算法技巧总结》、《JavaScript数学运算用法总结》、《JavaScript排序算法总结》、《JavaScript遍历算法与技巧总结》、《JavaScript查找算法技巧总结》及《JavaScript错误与调试技巧总结》

希望本文所述对大家JavaScript程序设计有所帮助。

(0)

相关推荐

  • JavaScript数据结构与算法之集合(Set)

    集合(Set) 说起集合,就想起刚进高中时,数学第一课讲的就是集合.因此在学习集合这种数据结构时,倍感亲切. 集合的基本性质有一条: 集合中元素是不重复的.因为这种性质,所以我们选用了对象来作为集合的容器,而非数组. 虽然数组也能做到所有不重复,但终究过于繁琐,不如集合. 集合的操作 集合的基本操作有交集.并集.差集等.这儿我们介绍JavaScipt集合中交集.并集.差集的实现. JavaScipt中集合的实现 首先,创建一个构造函数. /** * 集合的构造函数 */ function Set

  • JavaScript 处理树数据结构的方法示例

    JavaScript 处理树结构数据 场景 即便在前端,也有很多时候需要操作 树结构 的情况,最典型的场景莫过于 无限级分类.之前吾辈曾经遇到过这种场景,但当时没有多想直接手撕 JavaScript 列表转树了,并没有想到进行封装.后来遇到的场景多了,想到如何封装树结构操作,但考虑到不同场景的树节点结构的不同,就没有继续进行下去了. 直到吾辈开始经常运用了 ES6 Proxy 之后,吾辈想到了新的解决方案! 思考 问: 之前为什么停止封装树结构操作了? 答: 因为不同的树结构节点可能有不同的结构

  • JavaScript数据结构之链表的实现

    前面楼主分别讨论了数据结构栈与队列的实现,当时所用的数据结构都是用的数组来进行实现,但是数组有的时候并不是最佳的数据结构,比如在数组中新增删除元素的时候需要将其他元素进行移动,而在javascript中使用spit()方法不需要访问其他元素.如果你在使用数组的时候发现很慢,就可以考虑使用链表. 链表的概念 链表是一种常见的数据结构.它是动态地进行存储分配的一种结构.链表有一个"头指针"变量,以head表示,它存放一个地址,指向一个元素.每个结点都使用一个对象的引用指标它的后继,指向另一

  • js图数据结构处理 迪杰斯特拉算法代码实例

    这篇文章主要介绍了js图数据结构处理 迪杰斯特拉算法代码实例,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下 /*//1.确定数据结构, mapf[i][j] 为点i到点j的距离 [ Infinity 2 5 Infinity Infinity Infinity Infinity 2 6 Infinity Infinity Infinity Infinity 7 1 Infinity Infinity 2 Infinity 4 Infinity

  • 通过Jquery遍历Json的两种数据结构的实现代码

    在ajax交互中,我们从服务器端返回的数据类型有xml,html,script,json,jsonp,text,本文以json为例,讲述了在前台如何利用jquery遍历json的两种数据结构:"名称/值"对的集合,值的有序列表,以及值的有序列表里面包含"名称/值"对的集合,在服务器端,我们采用的Json.NET来序列化arraylist,hashTable,list<>等数据结构. 在开始之前,我们需要下载Json.net,下载完成后,在网站中添加引用,

  • ReactJs实现树形结构的数据显示的组件的示例

    本文介绍了ReactJs实现树形结构的数据显示的组件的示例,分享给大家,具体如下: 1.该组件树形显示数据 2.组件中数据的请求方式为fetch方式 3.点击对应的数据前面的小三角,fetch请求改数据下对应的子数据,并展开该节点. 4.将该组件的js.less文件放到kpiTree目录下,在kpiTree目录下创建images目录将组件需要的图片放入给目录,在kpiTree目录下创建json文件夹将该组件需要的json文件放入改文件夹中,组件便可正常运行. kpiTree.js文件 /** *

  • javascript数据结构之多叉树经典操作示例【创建、添加、遍历、移除等】

    本文实例讲述了javascript数据结构之多叉树经典操作.分享给大家供大家参考,具体如下: 多叉树可以实现复杂的数据结构的存储,通过遍历方法可以方便高效的查找数据,提高查找的效率,同时方便管理节点数据.javascript的DOM其实就是以多叉树的形式存储的.下面用javascript来实现多叉树的数据结构 1.创造一个节点 数据是以节点的形式存储的: class Node { constructor(data) { this.data = data; this.parent = null;

  • JavaScript数据结构之二叉树的删除算法示例

    本文实例讲述了JavaScript数据结构之二叉树的删除算法.分享给大家供大家参考,具体如下: 从二叉查找树上删除节点的操作复杂程度取决于删除哪个节点.如果删除没有子节点的节点就非常简单,如果节点只有一个子节点,不管是左子节点还是右子节点,就变得稍微有点复杂,如果节点包含两个子节点就最复杂. 如果待删除节点是叶子节点,那么只需要将从父节点指向它的链接指向null. 如果待删除节点只包含一个子节点,那么原本指向它的节点就得使其指向它的子节点. 如果待删除节点包含两个子节点,那么我们可以采用两种方式

  • JavaScript数据结构之数组的表示方法示例

    本文实例讲述了JavaScript数据结构之数组的表示方法.分享给大家供大家参考,具体如下: 数组类似于线性表.基本上每种语言都会讲数组作为固有类型.这里主要讲一下二维数组.我们可以把二维数组看成这样一个定长线性表:它的每个数据元素也是一个定长的线性表.数组一旦被定义,它的维数和维界就不再改变.因此,除了结构的初始化和销毁之外,数组只有存取元素和修改元素值的操作(这里注意和JavaScript中的array类型做出区分,这里说的是数据结构,而不是某一种单独语言的语法). 由于数组一般不作插入或者

  • JavaScript对JSON数组简单排序操作示例

    本文实例讲述了JavaScript对JSON数组简单排序操作.分享给大家供大家参考,具体如下: 我们经常回使用到数据格式 var arr=[{num:1},{num:3},{num:2}] 如何根据数组里面的JSON数据的某个key进行排序 javascript有一个sort()方法,直接通过 arr.sort()进行排序,默认只对数组的值进行排序,然而以上的数组的值却是个JSON格式的. 我们在看看sort方法的定义: 定义和用法 sort() 方法用于对数组的元素进行排序. 语法 array

  • JavaScript实现的反序列化json字符串操作示例

    本文实例讲述了JavaScript实现的反序列化json字符串操作.分享给大家供大家参考,具体如下: JavaScript中如何反序列化json字符串呢? 有如下两种方法: (1) 使用万能的eval var jsonText = '{"name":"acwong","age":23,"address":{"province":"GuangDong","city":&

  • JavaScript实现的简单加密解密操作示例

    本文实例讲述了JavaScript实现的简单加密解密操作.分享给大家供大家参考,具体如下: JavaScript实现对内容的加密和解密.加密,转成编码.解密则是编码转字符串. <html> <head> <meta charset="utf-8" /> <title>www.jb51.net JS加密解密</title> </head> <body> <h1> 加密解密 </h1>

  • JavaScript实现shuffle数组洗牌操作示例

    本文实例讲述了JavaScript实现shuffle数组洗牌操作.分享给大家供大家参考,具体如下: <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"> <html xmlns="http://www.w3.org/1999/xhtml"&g

  • JavaScript数据结构与算法之检索算法示例【二分查找法、计算重复次数】

    本文实例讲述了JavaScript数据结构与算法之检索算法.分享给大家供大家参考,具体如下: javascript数据结构与算法---检索算法(二分查找法.计算重复次数) /*只需要查找元素是否存在数组,可以先将数组排序,再使用二分查找法*/ function qSort(arr){ if (arr.length == 0) { return []; } var left = [];//存储小于基准值 var right = [];//存储大于基准值 var pivot = arr[0]; fo

  • JavaScript使用prototype属性实现继承操作示例

    本文实例讲述了JavaScript使用prototype属性实现继承操作.分享给大家供大家参考,具体如下: JS并没有显式的继承语法,在JS中所有的对象都是Object的子类实现, 因而对象之间是平等关系. 尽管如此我们可以通过特殊的方法达到继承的效果. 当然JS也不能直接定义类, 我们通过定义函数可以得到一个同名的类 , 同时这个函数就是这个类的构造器, 在定义函数时以this修饰的变量就是定义的 类的实例中的属性,当这个属性时函数时,  就可以认为这个属性变成了一个实例方法 //定义一个Pe

  • JavaScript数据结构之二叉树的查找算法示例

    本文实例讲述了JavaScript数据结构之二叉树的查找算法.分享给大家供大家参考,具体如下: 前面文章介绍了二叉树的遍历,现在谈谈在二叉树中进行查找.对二叉查找树来说,一般有以下三类查找:最大值,最小值和给定值. 查找最小值就是遍历左子树,直到找到最后一个结点,这是因为在二叉查找树中较小的值总是在左子节点上的. 代码如下: function getMin(){//查找最小值 var current=this.root;//指向根节点 while(current.left!=null){ cur

随机推荐