JavaScript でバイナリ ツリーを実装するためのコードの紹介

この記事では、JavaScript でバイナリ ツリーを実装するためのコードを紹介します。必要な方は参考にしてください。

ツリーには特別なバイナリツリーがあり、ここではjsを使って簡単なバイナリツリーを実装します。ノード

2. ノードの最大値/最小値

4. 事前順序トラバーサル
6. 指定されたノードが存在するかどうかを確認します。は空のツリーです

あまり言うことはありません。コードに移りましょう。最初はツリーの基本ユニットノードクラスです

/**
*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 中国語 Web サイトの他の関連記事を参照してください。