javaScript实现二叉搜索数

我心飞翔 分类:javascript

javaScript实现二叉搜索数

二叉搜索数是二叉树的一种,只允许左子节点比父节点小,右侧子节点比父节点大或者相等

  1. 创建一个节点构造函数Node,用于新建节点
function Node(val) {
	this.val = val;//该节点的值
	this.left = null;//该节点的左侧子节点
	this.right = null;//该节点的右侧子节点
}
 
  1. 创建一个搜索树构造函数
function SearchTree() {
	this.root = null;//根节点
	this.length = 0;//该树中所有节点的个数,包括根节点
}
 
  1. 给SearchTreet添加insertTree方法,用于向树中插入新的节点。首先我们需要判断根节点是否为空,然后从根节点进行迭代,如果待插入节点的值比父节点小,则作为父节点的左侧子节点,反之 作为右侧子节点。最后插入完毕之后返回该节点,并且将length加一
SearchTree.prototype.insertTree = function(val) {
		//新建一个节点
		let node = new Node(val);
		if (this.root === null) {
		//如果我们的根节点为null,则需要初始搜索树
			this.root = node;
			this.length++;
			return this.root;
		} else {
			let curr = this.root;
			while (true) {
				//迭代二叉树,将比根节点小的放在节点的左边,反之放在右边
				if (val < curr.val) {
					if (curr.left !== null) {
					//如果left不为空则继续迭代
						curr = curr.left;
					} else {
						curr.left = node;
						//退出while循环
						break;
					}
				} else {
					if (curr.right !== null) {
						curr = curr.right;
					} else {
						curr.right = node;
						break;
					}
				}
			}
		}
		this.length++;
		return node;
	},
 
  1. 前序遍历
SearchTree.prototype.prevErgodic  = function(node, arr = []) {
		if (node !== null) {
			arr.push(node.val)
			this.prevErgodic  (node.left, arr);
			this.prevErgodic  (node.right, arr)
		}
		return arr
	}
 
  1. 中序遍历
SearchTree.prototype.centerErgodic = function(node, arr = []) { 
		if (node !== null) {
			//升序排序
			this.centerErgodic (node.left, arr);
			arr.push(node.val);
			this.centerErgodic (node.right, arr);
			//降序排序
			//this.centerErgodic (node.right, arr);
			//arr.push(node.val);
			//this.centerErgodic (node.left, arr);
		}
		return arr;
	}
 
  1. 后序遍历
SearchTree.prototype.nextErgodic.function(node, arr = []) { 
		if (node !== null) {
			this.nextErgodic(node.left, arr);
			this.nextErgodic(node.right, arr);
			arr.push(node.val);
		}
		return arr;
	}
 
  1. 获得最小值,从根节点一直遍历左节点到叶子节点,该叶子节点即为最小值
SearchTree.prototype.getMin = function(node) {
		let curr = node || this.root;
		if (curr === null) {
			return false;
		} else {
			while (curr.left !== null) {
				curr = curr.left
			}
			return curr.val
		}
	}
 
  1. 获得最大值,从根节点一直遍历右节点到叶子节点,该叶子节点即为最大值
SearchTree.prototype.getMax = function(node) {
		let curr = node || this.root;
		if (curr === null) {
			return false;
		} else {
			while (curr.right!== null) {
				curr = curr.right
			}
			return curr.val
		}
	}
 
  1. 判断值是否存在,如果存在返回该节点,否则返回false
SearchTree.prototype.getItem = function(node, item) {
		if (this.root === null) {
			return false
		} else {
			let curr = node;
			if (curr === null) {
				return false;
			} else {
				if (item < curr.val) {
					return this.getItem(curr.left, item);
				} else if (item === curr.val) {
					return curr;
				} else if (item > curr.val) {
					return this.getItem(curr.right, item);
				}
			}
		}
	}
 

测试代码

//创建实例
const searchTree = new SearchTree();
//创建数组,循环给searchTree 插入节点
let max = 100;
let arr = [];
for (let index = 0; index < max; index++) {
	let item = Math.floor(Math.random() * max);
	arr.push(item);
	searchTree.insertTree(item)
}
console.log(searchTree)
//打印原数组
console.log(arr)
//打印前序遍历的数组
console.log(searchTree.prevErgodic(searchTree.root))
//打印中序遍历的数组
console.log(searchTree.centerErgodic(searchTree.root))
//打印升序排列后的数组,与中序遍历的数组比较
console.log(arr.sort((a,b)=>a - b))
//打印后序遍历的数组
console.log(searchTree.nextErgodic(searchTree.root))
//获取最小值
console.log(searchTree.getMin())
//获取最大值
console.log(searchTree.getMax())
//获取指定值节点
console.log(searchTree.getItem(searchTree.root, searchTree.getMax()))
 

回复

我来回复
  • 暂无回复内容