Introduction to code for implementing binary tree in javascript

This article brings you an introduction to the code for implementing binary trees in JavaScript. It has certain reference value. Friends in need can refer to it. I hope it will be helpful to you.

Tree is the basic knowledge point of data structure. There is a special binary tree in the tree. I will not explain the concept of tree in detail here. I just use js to implement a simple binary tree

1 .Add node
2.Remove node
3.Maximum/minimum value of node
4.In-order traversal
5.Pre-order traversal
6.Post-order traversal
7 .Find whether the specified node exists
8. Whether it is an empty tree

Without further ado, let’s talk about the code. The first is the basic unit node class of the tree

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

The next is the binary tree class code

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

The functions of each function are in the comments. Recursion is used extensively to traverse the tree. The recursion here is relatively simple and easy to understand. Finding the maximum and minimum values ​​here is lazy without recursive search, but in The maximum and minimum values ​​are directly retrieved during sequential traversal. Note that these are values, not nodes of the tree. In fact, the code for finding the minimum node is also written as a private function, but it is not used for searching for the maximum and minimum values.

Of course, this is just a simple binary tree, and it can also be upgraded to an AVL tree, etc. I won’t go into details here

Related recommendations:

Detailed explanation of the use of JS binary search tree

Detailed explanation of binary tree traversal in JS_javascript skills

Implementation methods of pre-order, in-order and post-order traversal of binary trees in JS

The above is the detailed content of Introduction to code for implementing binary tree in javascript. For more information, please follow other related articles on the PHP Chinese website!