二叉树-1.png
function BinaryTree() {
//构建二叉树结构
let Node = function(key){
this.key = key;
this.left = null;
this.right = null;
}
//创建二叉树根节点
let root = null;
/**
* [insertNode description]插入数据方法
* @param {[type]} node [description]
* @param {[type]} newNode [description]
* @return {[type]} [description]
*/
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);
}
}
}
/**
* [insert description]插入数据操作
* @param {[type]} key [description]
* @return {[type]} [description]
*/
this.insert = function(key){
let newNode = new Node(key);
if(root === null){
//根节点为空时，直接将此数据作为根节点
root = newNode;
}else{
//否则排序插入数据
insertNode(root, newNode);
}
}
/**
* [inOrderTraverseNode description]中序遍历排序方法（顺序：左-父-右），遇到父节点，先进入左子树，再进入右子树，当右子树遍历完成时，返回父节点
* @param {[type]} node [description]
* @param {Function} callback [description]
* @return {[type]} [description]
*/
let inOrderTraverseNode = function(node, callback){
if(node !== null){
inOrderTraverseNode(node.left, callback);
callback(node.key);
inOrderTraverseNode(node.right, callback);
}
}
/**
* [inOrderTraverse description]中序遍历排序
* @param {Function} callback [description]
* @return {[type]} [description]
*/
this.inOrderTraverse = function(callback){
inOrderTraverseNode(root, callback);
}
/**
* [preOrderTraverseNode description]前序遍历方法（顺序：父-左-右）,先打印当前父节点，然后进入父节点的左子树进行打印，当左子树没有下层左子树时，再进入右子树进行打印，右子树没有下层左子树和右子树时，返回父节点
* @param {[type]} node [description]
* @param {Function} callback [description]
* @return {[type]} [description]
*/
let preOrderTraverseNode = function(node, callback){
if(node !== null){
callback(node.key);
preOrderTraverseNode(node.left, callback);
preOrderTraverseNode(node.right, callback);
}
}
/**
* [preOrderTraverse description]前序遍历
* @param {Function} callback [description]
* @return {[type]} [description]
*/
this.preOrderTraverse = function(callback){
preOrderTraverseNode(root, callback);
}
/**
* [postOrderTraverseNode description]后序遍历方法（顺序：左-右-父）
* @param {[type]} node [description]
* @param {Function} callback [description]
* @return {[type]} [description]
*/
let postOrderTraverseNode = function(node, callback){
if(node !== null){
postOrderTraverseNode(node.left, callback);
postOrderTraverseNode(node.right, callback);
callback(node.key);
}
}
/**
* [postOrderTracerse description]后序遍历
* @param {Function} callback [description]
* @return {[type]} [description]
*/
this.postOrderTracerse = function(callback){
postOrderTraverseNode(root, callback);
}
/**
* [minNode description]查找最小值方法
* @param {[type]} node [description]
* @return {[type]} [description]
*/
let minNode = function(node){
if(node) {
while(node && node.left !== null){
node = node.left;
}
return node.key;
}
}
/**
* [min description]查找最小值
* @return {[type]} [description]
*/
this.min = function(){
return minNode(root);
}
/**
* [maxNode description]查找最大值方法
* @param {[type]} node [description]
* @return {[type]} [description]
*/
let maxNode = function(node) {
if(node){
while(node && node.right !== null){
node = node.right;
}
return node.key;
}
}
/**
* [max description]查找最大值
* @return {[type]} [description]
*/
this.max = function() {
return maxNode(root);
}
/**
* [searchNode description]查找值方法
* @param {[type]} node [description]
* @param {[type]} key [description]
* @return {[type]} [description]
*/
let searchNode = function(node, key){
if(node == null){
return false;
}
if(key < node.key){
return searchNode(node.left, key);
}else if(key > node.key){
return searchNode(node.right, key);
}else{
return true;
}
}
/**
* [search description]查找对应值
* @param {[type]} key [description]
* @return {[type]} [description]
*/
this.search = function(key){
return searchNode(root, key);
}
/**
* [findMinNode description]查找最小值并返回该对象（上面的查找最小值返回的是数值）
* @param {[type]} node [description]
* @return {[type]} [description]
*/
let findMinNode = function(node){
if(node){
while(node && node.left !== null){
node = node.left;
}
return node;
}
return null;
}
/**
* [removeNode description]删除方法
* @param {[type]} node [description]
* @param {[type]} key [description]
* @return {[type]} [description]
*/
let removeNode = function(node, key){
//情况一：删除最底层节点。判断在根节点左子树还是右子树，再依次对节点的左子树或右子树进行对比，找到对应节点后删除并返回删除后的二叉树，找不到就返回null。如删除1，1先跟根节点8对比，比8小（key < node.key），进入左子树中，此时再将3当做父节点再次调用removeNode方法，直到找到节点为1的值进行匹配。如果找到匹配值，就进入if(node.left === null && node.right === null)判断中，通过设置当前节点node为null删除该节点，return node将删除的节点null return给父节点3，,父节点3再将自身的节点情况通过return node return给跟父节点8（return node在递归调用removeNode的之后，也是递归返回的，如不理解，可以将注释的node节点打印放开，断点调试即可），这样，就将整个删除节点后的二叉树都返回回去了。
//情况二：删除的节点是含有单侧子节点的父节点。左子树节点（只有左子树子节点）：删除该节点后，将该节点下的左子树节点指针替换为该节点指针；右子树节点（只有右子树子节点）：删除该节点后，将该节点的右子树节点指针替换为该节点指针
//情况三：删除的节点有左右两个子节点父节点。找到该父节点下右子树中的最小值节点，将该父节点的值更新为最小值节点的值，最后删除最小值节点并返回删除后的二叉树
if(node === null)return null;
if(key < node.key) {
node.left = removeNode(node.left, key);
// console.log('node-- ',node)
return node;
}else if(key > node.key) {
node.right = removeNode(node.right, key);
// console.log('node-- ',node)
return node;
}else {
if(node.left === null && node.right === null){
node = null;
// console.log('node-- ',node)
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;
}
}
/**
* [remove description]删除
* @param {[type]} key [description]
* @return {[type]} [description]
*/
this.remove = function(key){
root = removeNode(root, key);
}
}
let nodes = [8, 3, 10, 1, 6, 14, 4, 7, 13];
let binaryTree = new BinaryTree();
nodes.forEach(function(key) {
binaryTree.insert(key);
})
let callback = function(key){
console.log(key);
}
// binaryTree.inOrderTraverse(callback);
// binaryTree.preOrderTraverse(callback);
binaryTree.postOrderTracerse(callback);
console.log('min is ', binaryTree.min());
console.log('max is ', binaryTree.max());
console.log('search 7', binaryTree.search(7));
console.log('search 100', binaryTree.search(100));
binaryTree.remove(1) //删除情况一
binaryTree.remove(10) //删除情况二
binaryTree.remove(4) //删除情况三
网友评论