js实现二叉树

二叉树

• 二叉树排序是一种数据结构、根据左孩子小于根节点、右孩子大于根节点的顺序进行构造
• 任意给一个数组，对其进行二叉树排序。

function BinaryTree() {
	
	// 二叉树的节点  
	let Node = function (key) {
		this.key = key; //当前节点的值
		this.left = null; // 左孩子
		this.right = null; // 右孩子
	}

	// 插入子节点
	let insertNode = function (node,newNode) {
		// 插入的值小于父节点，将其插入在父节点的左侧
		if(newNode.key < node.key){
			// 是否拥有左孩子，有则递归进行判断、无则直接插入
			if(node.left === null){
				node.left = newNode;
			}else{
				insertNode(node.left,newNode);
			}
		}else{
			if(node.right === null){
				node.right = newNode;
			}else{
				insertNode(node.right,newNode);
			}
		}
	}

	// 初始化根节点、就是一个数组的第一个元素当做二叉树的根节点
	let root = null; 

	this.insert = function (key) {
		let newNode = new Node(key);
		if(root === null){
			root = newNode;
		}else{
			insertNode(root,newNode)
		}
	};

	// 查看二叉树结构
	this.show = function () {
		console.log(root);
	}

	// 中序遍历
	let inOrderTraverseNode = function (node,callback) {
		if(node !== null){
			inOrderTraverseNode(node.left,callback);
			callback(node.key);
			inOrderTraverseNode(node.right,callback)
		}
	}

	this.inOrderTraverse = function (callback) {
		inOrderTraverseNode(root,callback)
	}

	// 前序遍历
	let preOrderTraverseNode = function (node,callback) {
		if(node !== null){
			callback(node.key);
			preOrderTraverseNode(node.left,callback);
			preOrderTraverseNode(node.right,callback);
		}
	}

	this.preOrderTraverse = function (callback) {
		preOrderTraverseNode(root,callback)
	}

	// 后序遍历
	let nextOrderTraverseNode = function (node,callback) {
		if(node !== null){
			nextOrderTraverseNode(node.left,callback);
			nextOrderTraverseNode(node.right,callback);
			callback(node.key);
		}
	}

	this.nextOrderTraverse = function (callback) {
		nextOrderTraverseNode(root,callback);
	}

}

• 调用

let nodes  =  [18,13,102,11,6,14,4,7,131];
const bt = new BinaryTree();

nodes.forEach( key => {
	bt.insert(key)
})

bt.show()

// 中序遍历
// bt.inOrderTraverse((key) => {
// 	console.log(key);
// })

// 前序遍历
// bt.preOrderTraverse((key) => {
// 	console.log(key);
// })

// 后序遍历
bt.nextOrderTraverse((key) => {
	console.log(key);
})

• 二叉树遍历

1. 中序遍历

   1. 首先遍历左子树、然后遍历根节点、最后遍历右子树 -- 左-根-右
   2. 作用: 将一个二叉树进行升序排序输出

2. 前序遍历

   1. 首先遍历根节点、然后遍历左子树、最后遍历右子树 -- 根-左-右
   2. 作用: 复制一个二叉树、复制一个二叉树比重新生成一个二叉树的效率高10倍左右

3. 后序遍历

   1. 首先遍历左子树、然后遍历右子树、最后遍历根节点 -- 左-右-根
   2. 适用于操作系统的文件遍历

• 二叉树查找

1. 查找最小值
2. 查找最大值
3. 查找某一个值

// 查找最小值
let minNode = function (node) {
	if(node){
		while(node && node.left !== null){
			node = node.left;
		}

		return node.key;
	}

	return null;
}

this.min = function () {
	return minNode(root);
}

// 查找最大值
let maxNode = function (node) {
	if(node){

		while(node && node.right !== null){
			node = node.right;
		}

		return node.key;
	}

	return null;
}

this.max = function () {
	return maxNode(root);
}

// 查找某个具体的值
let findNode = function (node,key) {
	if(node === null){
		return false;
	}

	// 若是查找的值小于当前节点的值，那么就去其左子树进行查找
	// 若是大于,就去右子树进行查找
	// 若是相等 则返回true 代表存在
	if(key < node.key){
		return findNode(node.left,key)
	}else if(key > node.key){
		return findNode(node.right, key)
	}else{
		return true;
	}
}

this.find = function (key) {
	return findNode(root,key);
}

• 调用

// 最小值
// console.log(bt.min());

// 最大值
// console.log(bt.max());

// 查找某一个值是否存在二叉树中
console.log(bt.find(12)); // false
console.log(bt.find(14)); // true

• 删除子节点

// 删除子节点
let removeNode = function (node,key) {
	if(node === null) {
		return null;
	}

	if(key < node.key){
		node.left = removeNode(node.left, key)
		return node;
	}else if(key > node.key){
		node.right = removeNode(node.right, key)
		return node
	}else{
		// 是叶子节点
		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 aux = findMinNode(node.right);
		node.key = aux.key;
		node.right = removeNode(node.right,aux.key);
		return node;
	}
}

this.remove = function (key) {
	root = removeNode(root,key);
}

• 调用

// 删除叶子节点
bt.inOrderTraverse((key) => {
	console.log(key);
})
console.log('-----');
bt.remove(4)
bt.inOrderTraverse((key) => {
	console.log(key);
})

• 全部代码

function BinaryTree() {
	
	// 二叉树的节点  
	let Node = function (key) {
		this.key = key; //当前节点的值
		this.left = null; // 左孩子
		this.right = null; // 右孩子
	}

	// 插入子节点
	let insertNode = function (node,newNode) {
		// 插入的值小于父节点，将其插入在父节点的左侧
		if(newNode.key < node.key){
			// 是否拥有左孩子，有则递归进行判断、无则直接插入
			if(node.left === null){
				node.left = newNode;
			}else{
				insertNode(node.left,newNode);
			}
		}else{
			if(node.right === null){
				node.right = newNode;
			}else{
				insertNode(node.right,newNode);
			}
		}
	}

	// 初始化根节点、就是一个数组的第一个元素当做二叉树的根节点
	let root = null; 

	this.insert = function (key) {
		let newNode = new Node(key);
		if(root === null){
			root = newNode;
		}else{
			insertNode(root,newNode)
		}
	};

	// 查看二叉树结构
	this.show = function () {
		console.log(root);
	}

	// 中序遍历
	let inOrderTraverseNode = function (node,callback) {
		if(node !== null){
			inOrderTraverseNode(node.left,callback);
			callback(node.key);
			inOrderTraverseNode(node.right,callback)
		}
	}

	this.inOrderTraverse = function (callback) {
		inOrderTraverseNode(root,callback)
	}

	// 前序遍历
	let preOrderTraverseNode = function (node,callback) {
		if(node !== null){
			callback(node.key);
			preOrderTraverseNode(node.left,callback);
			preOrderTraverseNode(node.right,callback);
		}
	}

	this.preOrderTraverse = function (callback) {
		preOrderTraverseNode(root,callback)
	}

	// 后序遍历
	let nextOrderTraverseNode = function (node,callback) {
		if(node !== null){
			nextOrderTraverseNode(node.left,callback);
			nextOrderTraverseNode(node.right,callback);
			callback(node.key);
		}
	}

	this.nextOrderTraverse = function (callback) {
		nextOrderTraverseNode(root,callback);
	}

	// 查找最小值
	let minNode = function (node) {
		if(node){
			while(node && node.left !== null){
				node = node.left;
			}

			return node.key;
		}

		return null;
	}

	this.min = function () {
		return minNode(root);
	}

	// 查找最大值
	let maxNode = function (node) {
		if(node){

			while(node && node.right !== null){
				node = node.right;
			}

			return node.key;
		}

		return null;
	}

	this.max = function () {
		return maxNode(root);
	}

	// 查找某个具体的值
	let findNode = function (node,key) {
		if(node === null){
			return false;
		}

		// 若是查找的值小于当前节点的值，那么就去其左子树进行查找
		// 若是大于,就去右子树进行查找
		// 若是相等 则返回true 代表存在
		if(key < node.key){
			return findNode(node.left,key)
		}else if(key > node.key){
			return findNode(node.right, key)
		}else{
			return true;
		}
	}

	this.find = function (key) {
		return findNode(root,key);
	}

	// 查找最小子节点
	let findMinNode = function (node) {
		if(node){
			while(node && node.left !== null){
				return node
			}
		}

		return null;
	}

	// 删除叶子节点
	let removeNode = function (node,key) {
		if(node === null) {
			return null;
		}

		if(key < node.key){
			node.left = removeNode(node.left, key)
			return node;
		}else if(key > node.key){
			node.right = removeNode(node.right, key)
			return node
		}else{
			// 是叶子节点
			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 aux = findMinNode(node.right);
			node.key = aux.key;
			node.right = removeNode(node.right,aux.key);
			return node;
		}
	}

	this.remove = function (key) {
		root = removeNode(root,key);
	}

}

let nodes  =  [18,13,102,11,6,14,4,7,131];
const bt = new BinaryTree();

nodes.forEach( key => {
	bt.insert(key)
})

// bt.show()

// 中序遍历
// bt.inOrderTraverse((key) => {
// 	console.log(key);
// })

// 前序遍历
// bt.preOrderTraverse((key) => {
// 	console.log(key);
// })

// 后序遍历
// bt.nextOrderTraverse((key) => {
// 	console.log(key);
// })

// 最小值
// console.log(bt.min());

// 最大值
// console.log(bt.max());

// 查找某一个值是否存在二叉树中
// console.log(bt.find(12)); // false
// console.log(bt.find(14)); // true

// 删除叶子节点
bt.inOrderTraverse((key) => {
	console.log(key);
})
console.log('-----');
bt.remove(4)
bt.inOrderTraverse((key) => {
	console.log(key);
})