Introduction au code pour implémenter un arbre binaire en javascript

Ce que cet article vous apporte est une introduction au code d'implémentation des arbres binaires en JavaScript. Il a une certaine valeur de référence. Les amis dans le besoin peuvent s'y référer.

L'arbre est le point de connaissance de base de la structure des données. Il y a un arbre binaire spécial dans l'arbre. Je n'expliquerai pas le concept d'arbre en détail ici, j'utilise simplement js pour implémenter un binaire simple. arbre

1 .Ajouter un nœud
2.Supprimer un nœud
3.Valeur maximale/minimale du nœud
4.Parcours dans l'ordre
5.Parcours en précommande
6.Parcours post-commande
7 .Trouver si le nœud spécifié existe
8. S'il s'agit d'un arbre vide

Sans plus tarder, parlons du code Le premier est l'unité de base. Classe de nœud de l'arbre

/**
*left:左子树
*right:右子树
*value:节点值
*/
export default class BinaryNode {
	constructor(val) {
		this.value = val;
		this.left = null;
		this.right = null;
	}
}

Le suivant est le code de classe de l'arbre binaire

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);
		}
	}
}

Les fonctions de chaque fonction sont dans les commentaires. La récursion est largement utilisée pour parcourir l'arbre. La récursivité ici est relativement simple et facile à comprendre. La recherche des valeurs maximales et minimales ici est paresseuse et il n'y a pas de recherche récursive. Au lieu de cela, les valeurs maximales et minimales sont directement récupérées dans le parcours dans l'ordre. sont des valeurs, pas des nœuds de l'arbre. En fait, le code pour trouver le nœud minimum est également écrit comme une fonction privée, mais il n'est pas utilisé pour rechercher les valeurs maximales et minimales

Bien sûr, c'est le cas. juste un simple arbre binaire, il peut également être mis à niveau vers un arbre AVL, etc., je n'entrerai pas dans les détails ici

Recommandations associées :

Explication détaillée de l'utilisation de l'arbre de recherche binaire JS

Explication détaillée de la traversée de l'arbre binaire dans les compétences JS_javascript

Méthodes de mise en œuvre de la précommande , parcours dans l'ordre et post-ordre des arbres binaires en JS

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!