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树等，这里不再赘述