本篇文章给大家带来的内容是关于javascript实现二叉树的代码介绍,有一定的参考价值,有需要的朋友可以参考一下,希望对你有所帮助。
树是数据结构基本的知识点,树里面有比较特殊的二叉树,这里就不详细讲解树的概念了,只是用js实现简易的二叉树
1.新增节点
2.移除节点
3.节点最大/最小值
4.中序遍历
5.先序遍历
6.后序遍历
7.查找是否存在指定节点
8.是否为空树
话不多说,上代码,首先是树的基本单元节点类
/** *left:左子树 *right:右子树 *value:节点值 */ export default class BinaryNode { constructor(val) { this.value = val; this.left = null; this.right = null; } }
接下来是二叉树类代码
import BinaryNode from './BinaryNode' export default class BinarySearchTree { constructor() { this.root = null; this.values = new Array(); } /** * [insert 插入节点] * @param {[type]} val [description] * @return {[type]} [description] */ insert(val) { this.values.push(val); let node = new BinaryNode(val); if (!this.root) { this.root = node; }else { this._insertNode(this.root, node); } } /** * [remove 移除指定值] * @param {[*]} val [目标值] * @return {[type]} [description] */ remove(val) { this.root = this._removeNode(this.root, val); } /** * [search 检索] * @param {[*]} val [被检索值] * @return {[Boolean]} [表示是否存在] */ search(val) { let values = this.inOrderTraverse(); return values.includes(val); } /** * [min 返回最小值] * @return {[type]} [description] */ min() { let values = this.inOrderTraverse(); return values[0]; } /** * [max 返回最大值] * @return {[type]} [description] */ max() { let values = this.inOrderTraverse(); return values[values.length - 1]; } /** * [isEmpty 是否为空二叉树] * @return {Boolean} */ isEmpty() { return this.root === null; } /** * [inOrderTraverse 中序遍历] * @return {[Array]} [description] */ inOrderTraverse() { let result = new Array(); this._inOrderTraverseNode(this.root, function(node) { result.push(node.value); }) return result; } /** * [preOrderTraverse 先序遍历] * @return {[Array]} [description] */ preOrderTraverse() { let result = new Array(); this._preOrderTraverseNode(this.root, function(node) { result.push(node.value); }) return result; } /** * [postOrderTraverse 后序遍历] * @return {[Array]} [description] */ postOrderTraverse() { let result = new Array(); this._postOrderTraverseNode(this.root, function(node) { result.push(node.value); }) return result; } /** * [_insertNode 在指定节点插入节点] * @param {[BinaryNode]} node [目标节点] * @param {[BinaryNode]} newNode [待插入节点] */ _insertNode(node, newNode) { if (node.value > newNode.value) { if (node.left) { this._insertNode(node.left, newNode); }else { node.left = newNode; } }else { if (node.right) { this._insertNode(node.right, newNode); }else { node.right = newNode; } } } /** * [_removeNode 移除节点递归] * @param {[BinaryNode]} node [当前节点] * @param {[*]} val [要移的除节点值] * @return {[BinaryNode]} [当前节点] */ _removeNode(node, val) { if (node === null) { return node; } //递归寻找目标节点 if (val < node.value) { this._removeNode(node.left, val); return node; } if (val > node.value) { this._removeNode(node.right, val); return node; } //找到目标节点 if (val === node.value) { //为叶子节点 if (node.left === null && node.right === null) { node = null; return node; } //只有一个子节点 if (node.left === null) { node = node.right; return node; }else if (node.right === null) { node = node.left; return node; } //有两个子节点 let min_node = this._findMinNode(node); node.value = min_node.value; node.right = this._removeNode(node.right, min_node.value); return node; } } /** * [_findMinNode 查找最小节点] * @param {[BinaryNode]} node [当前节点] * @return {[BinaryNode]} [最小的节点] */ _findMinNode(node) { while(node && node.left) { node = node.left; } return node; } /** * [_inOrderTraverseNode 中序遍历递归] * @param {[BinaryNode]} node [当前节点] * @param {Function} callback [回调函数] * @return {[type]} [description] */ _inOrderTraverseNode(node, callback) { if (node) { this._inOrderTraverseNode(node.left, callback); callback(node); this._inOrderTraverseNode(node.right, callback); } } /** * [_preOrderTraverseNode 先序遍历递归] * @param {[BinaryNode]} node [当前节点] * @param {Function} callback [回调函数] * @return {[type]} [description] */ _preOrderTraverseNode(node, callback) { if (node) { callback(node); this._preOrderTraverseNode(node.left, callback); this._preOrderTraverseNode(node.right, callback); } } /** * [_postOrderTraverseNode 后序遍历递归] * @param {[BinaryNode]} node [当前节点] * @param {Function} callback [回调函数] * @return {[type]} [description] */ _postOrderTraverseNode(node, callback) { if (node) { this._postOrderTraverseNode(node.left, callback); this._postOrderTraverseNode(node.right, callback); callback(node); } } }
每个函数的功能都在注释中,其中这里对树的遍历大量的使用的递归,这里递归相对简单易懂,这里查找最大最小值偷懒没有递归查找,而是在中序遍历里直接取出最大最小值,注意这里是值,并不是树的节点,实际上查找最小节点的代码也作为私有函数写出来了,只是没用在最大最小值查找而已
当然这只是简单的二叉树,还可以升级成AVL树等,这里不再赘述
相关推荐:
以上就是javascript实现二叉树的代码介绍的详细内容,更多请关注php中文网其它相关文章!
已抢65056个
抢已抢28189个
抢已抢15215个
抢已抢7629个
抢已抢9519个
抢已抢19303个
抢