登录  /  注册
首页 > web前端 > js教程 > 正文

javascript实现二叉树的代码介绍

不言
发布: 2018-08-22 11:17:04
原创
1308人浏览过

本篇文章给大家带来的内容是关于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树等,这里不再赘述

相关推荐:

JS二叉搜索树使用详解

JS中的二叉树遍历详解_javascript技巧

JS二叉树的先序中序及后序遍历实现方法

以上就是javascript实现二叉树的代码介绍的详细内容,更多请关注php中文网其它相关文章!

智能AI问答
PHP中文网智能助手能迅速回答你的编程问题,提供实时的代码和解决方案,帮助你解决各种难题。不仅如此,它还能提供编程资源和学习指导,帮助你快速提升编程技能。无论你是初学者还是专业人士,AI智能助手都能成为你的可靠助手,助力你在编程领域取得更大的成就。
相关标签:
来源:php中文网
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系admin@php.cn
最新问题
热门教程
更多>
最新下载
更多>
网站特效
网站源码
网站素材
前端模板
关于我们 免责申明 意见反馈 讲师合作 广告合作 最新更新
php中文网:公益在线php培训,帮助PHP学习者快速成长!
关注服务号 技术交流群
PHP中文网订阅号
每天精选资源文章推送
PHP中文网APP
随时随地碎片化学习
PHP中文网抖音号
发现有趣的

Copyright 2014-2024 https://www.php.cn/ All Rights Reserved | php.cn | 湘ICP备2023035733号