欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

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

程序员文章站 2022-07-02 20:34:51
本文实例讲述了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错误与调试技巧总结

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