javascript實(shí)現(xiàn)二叉樹(shù)的代碼介紹

/**
*left:左子樹(shù)
*right:右子樹(shù)
*value:節(jié)點(diǎn)值
*/
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 插入節(jié)點(diǎn)]
	 * @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 [目標(biāo)值]
	 * @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 是否為空二叉樹(shù)]
	 * @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 在指定節(jié)點(diǎn)插入節(jié)點(diǎn)]
	 * @param {[BinaryNode]} node [目標(biāo)節(jié)點(diǎn)]
	 * @param {[BinaryNode]} newNode [待插入節(jié)點(diǎn)]
	 */
	_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 移除節(jié)點(diǎn)遞歸]
	 * @param {[BinaryNode]} node [當(dāng)前節(jié)點(diǎn)]
	 * @param {[*]} val [要移的除節(jié)點(diǎn)值]
	 * @return {[BinaryNode]} [當(dāng)前節(jié)點(diǎn)]
	 */
	_removeNode(node, val) {
	if (node === null) {
	return node;
	}
	//遞歸尋找目標(biāo)節(jié)點(diǎn)
	if (val < node.value) {
	this._removeNode(node.left, val);
	return node;
	}

	if (val > node.value) {
	this._removeNode(node.right, val);
	return node;
	}
	//找到目標(biāo)節(jié)點(diǎn)
	if (val === node.value) {
	//為葉子節(jié)點(diǎn)
	if (node.left === null && node.right === null) {
	node = null;
	return node;
	}
	//只有一個(gè)子節(jié)點(diǎn)
	if (node.left === null) {
	node = node.right;
	return node;
	}else if (node.right === null) {
	node = node.left;
	return node;
	}
	//有兩個(gè)子節(jié)點(diǎn)
	let min_node = this._findMinNode(node);
	node.value = min_node.value;
	node.right = this._removeNode(node.right, min_node.value);
	return node;
	}
	}

	/**
	 * [_findMinNode 查找最小節(jié)點(diǎn)]
	 * @param {[BinaryNode]} node [當(dāng)前節(jié)點(diǎn)]
	 * @return {[BinaryNode]} [最小的節(jié)點(diǎn)]
	 */
	_findMinNode(node) {
	while(node && node.left) {
	node = node.left;
	}
	return node;
	}

	/**
	 * [_inOrderTraverseNode 中序遍歷遞歸]
	 * @param {[BinaryNode]} node [當(dāng)前節(jié)點(diǎn)]
	 * @param {Function} callback [回調(diào)函數(shù)]
	 * @return {[type]} [description]
	 */
	_inOrderTraverseNode(node, callback) {
	if (node) {
	this._inOrderTraverseNode(node.left, callback);
	callback(node);
	this._inOrderTraverseNode(node.right, callback);
	}
	}

	/**
	 * [_preOrderTraverseNode 先序遍歷遞歸]
	 * @param {[BinaryNode]} node [當(dāng)前節(jié)點(diǎn)]
	 * @param {Function} callback [回調(diào)函數(shù)]
	 * @return {[type]} [description]
	 */
	_preOrderTraverseNode(node, callback) {
	if (node) {
	callback(node);
	this._preOrderTraverseNode(node.left, callback);
	this._preOrderTraverseNode(node.right, callback);
	}
	}

	/**
	 * [_postOrderTraverseNode 后序遍歷遞歸]
	 * @param {[BinaryNode]} node [當(dāng)前節(jié)點(diǎn)]
	 * @param {Function} callback [回調(diào)函數(shù)]
	 * @return {[type]} [description]
	 */
	_postOrderTraverseNode(node, callback) {
	if (node) {
	this._postOrderTraverseNode(node.left, callback);
	this._postOrderTraverseNode(node.right, callback);
	callback(node);
	}
	}
}