原文参考我的公众号文章 梳理一波「二叉树
二叉树
二叉树，顾名思义，每个节点最多有两个“叉”，也就是两个子节点，别离是左子节点和右子节点。不过，二叉树并不要求每个节点都有两个子节点，有的节点只有左子节点，有的节点只有右子节点。
- 根节点：无父节点的节点
- 叶子结点：无子节点的节点
- 兄弟节点：有雷同根节点的节点
对于“树”，还有三个比拟类似的概念：高度（Height）、深度（Depth）、层（Level）。它们的定义是这样的：
二叉查找（排序）树
- 也叫二叉搜寻树，反对动态数据汇合的疾速插入、删除、查找操作；
- 有序二叉树：在树中的任意一个节点，其左子树中的每个节点的值，都要小于这个节点的值，而右子树节点的值都大于这个节点的值；
- 是一颗二叉树，每个节点最多两个子结点，即每一层最多 2^(level – 1)个节点；
树结构
/** 树节点 */
class BinaryNode {
constructor(data) {
this.data = data; //存储的数据
this.left = null; //左节点
this.right = null; //右节点
this.level = 1; //所属层级
this.count = 1; //反复数据次数
this.isDeleted = false; //是否被删除
}
}
/** 二叉树 */
class BinarySearchTree {
constructor() {
this.root = null; //根节点：在第一次insert时会被赋予值
this.nodes = 0; //节点数
this.list = []; //遍历二叉树时长期存储数据的数组
}
}插入节点
插入规定：新结点值与以后插入地位（从根节点开始）的节点值进行比拟
- 小于父节点值：插在父节点左节点上；
- 大于父节点值：插在父节点右节点上；
- 等于父节点值：父节点 count++；（这种形式看状况，如果结点还有其余数据而非只有一个 data，那能够。否则应合并到上一种状况，合并到右节点上）
- 插入过程可减少被插入的结点所属 level 的保护！
// class BinarySearchTree { ... }
/**
* 插入数据
* @param {*} data 结点的值
*/
insert(data) {
this.nodes++;
// 递归插入
// let newNode = new BinaryNode(data);
// if (this.root === null) {
// this.root = newNode;
// } else {
// this._insert(this.root, newNode);
// }
// 循环插入
this.loopInsert(data)
}
/**
* 递归的形式插入节点：新结点值与以后插入地位（从根节点开始）的节点值进行比拟
* 小于根节点值：插在根节点左节点上；
* 大于等于根节点值：插在根节点右节点上；
* 减少结点所属level的保护！
* @param {*} theRootNode 被插入地位节点（从根节点开始）
* @param {*} newNode 新插入的节点
*/
_sameValAsBigInsert(theRootNode, newNode) {
newNode.level++; //从根登程，每执行一次_sameValAsBigInsert，层级便主动+1
if (theRootNode.data > newNode.data) {
if (theRootNode.left === null) {
theRootNode.left = newNode;
} else {
// 阐明不是叶子结点，持续向上层插入判断
this._sameValAsBigInsert(theRootNode.left, newNode);
}
} else {
if (theRootNode.right === null) {
theRootNode.right = newNode;
} else {
// 阐明不是叶子结点，持续向上层插入判断
this._sameValAsBigInsert(theRootNode.right, newNode);
}
}
}
/**
* !!!值雷同，则合并到以后根节点
* @param {*} theRootNode 被插入地位节点（从根节点开始）
* @param {*} newNode 新插入的节点
*/
_sameValMergeInsert(theRootNode, newNode) {
newNode.level++; //从根登程，每执行一次_sameValMergeInsert，层级便主动+1
if (theRootNode.data > newNode.data) {
if (theRootNode.left === null) {
theRootNode.left = newNode;
} else {
// 阐明不是叶子结点，持续向上层插入判断
this._sameValMergeInsert(theRootNode.left, newNode);
}
} else if (theRootNode.data < newNode.data) {
if (theRootNode.right === null) {
theRootNode.right = newNode;
} else {
// 阐明不是叶子结点，持续向上层插入判断
this._sameValMergeInsert(theRootNode.right, newNode);
}
} else {
theRootNode.count++; // 值雷同，则合并到以后根节点
}
}
/**
* 循环的形式插入
* @param {*} data
* @returns
*/
loopInsert(data) {
if (this.root == null) {
this.root = new BinaryNode(data);
return;
}
let p = this.root;
while (p != null) {
if (data > p.data) {
if (p.right == null) {
p.right = new BinaryNode(data);
return;
}
p = p.right;
} else {
// data <= p.data
if (p.left == null) {
p.left = new BinaryNode(data);
return;
}
p = p.left;
}
}
}遍历树（前序、中序、后续）
遍历树采取递归的形式，出递归的条件是 node=null
/** 遍历树: [type] 遍历形式 */
print(type) {
this.list = [];
let callee = `${type}Order`;
this[callee](this.root);
}- 前序遍历
prevOrder(node){
if(node==null){
return
}
console.log(node.data)
this.prevOrder(node.left)
this.prevOrder(node.right)
}- 中序遍历（遍历后果正好是有序的）
inOrder(node){
if(node==null){
return
}
this.inOrder(node.left)
console.log(node.data)
this.inOrder(node.right)
}- 后序遍历
postOrder(node){
if(node==null){
return
}
this.postOrder(node.left)
this.postOrder(node.right)
console.log(node.data)
}查找节点
先取根节点，如果它等于咱们要查找的数据，那就返回。如果要查找的数据比根节点的值小，那就在左子树中递归查找；如果要查找的数据比根节点的值大，那就在右子树中递归查找。
/**
* 查找一个节点
* @param {*} data 要查找的值
* @returns
*/
find(data) {
let node = this.root;
while (node != null) {
if (data < node.data) {
node = node.left;
} else if (data > node.data) {
node = node.right;
} else {
return node;
}
}
return null;
}
删除节点
物理删除：删除操作比较复杂，个别要分以下三种状况别离解决。
- 被删除节点没有子节点：间接将父节点中，指向要删除节点的指针置为 null；
- 被删除节点只有一个子节点：只须要更新父节点中，指向要删除节点的指针，让它指向要删除节点的子节点（左或右）就能够了；
- 被删除节点右两个子节点（最简单）：咱们须要找到这个节点的右子树中的最小节点，把它替换到要删除的节点上。而后再删除掉这个最小节点，因为最小节点必定没有左子节点（如果有左子结点，那就不是最小节点了），所以，咱们能够利用下面两条规定来删除这个最小节点；
逻辑删除节点（简易版）
/**
* 删除节点（简易版）
* 对要删除的节点做标记，示意已删除
* @param {*} data
*/
delete(data){
let targetNode = this.find(data);
// 未找到要删除的数据
if(targetNode == null){
return null
}
// 标记为“已删除”
targetNode.isDeleted = true;
}
}逻辑删除对应的树遍历形式批改！
prevOrder(node) {
if (node == null) {
return;
}
/**+++ 此处减少判断，inOrder和postOrder同样解决！ */
if (node.isDeleted != true) {
this.list.push(node.data);
console.log(node.data);
}
this.prevOrder(node.left);
this.prevOrder(node.right);
}
测试有序二叉树
// 创立一颗有序二叉树
let bsTree = new BinarySearchTree();
// 插入数据
let arr = [6,8,7,6,3,5,9,4]
arr.map(item=>{
bsTree.insert(item)
})
// 二叉树构造
console.log(bsTree);
// 三种形式遍历整棵树！
console.log('前序遍历');
bsTree.prevOrder(bsTree.root)
console.log('\n\n')
console.log('中序遍历（有序输入）');
bsTree.inOrder(bsTree.root)
console.log('\n\n')
console.log('后序遍历');
bsTree.postOrder(bsTree.root)
console.log('\n\n')
// 查找某个节点
console.log("\n查找值6");
console.log(bsTree.find(6));
// 删除某个节点
console.log("\n删除6");
console.log(bsTree.delete(6));
console.log("\n\n");
console.log("删除后-前序遍历");
bsTree.print("prev");
总结（来自极客工夫课程总结，总归比我本人总结的好 🤷♂️）
这篇文章学习了一种非凡的二叉树，二叉查找树。它反对疾速地查找、插入、删除操作。
二叉查找树中，每个节点的值都大于左子树节点的值，小于右子树节点的值。不过，这只是针对没有反复数据的状况。对于存在反复数据的二叉查找树，我介绍了两种构建办法，
- 一种是让每个节点存储多个值雷同的数据；
- 另一种是，每个节点中存储一个数据。针对这种状况，只须要稍加革新原来的插入、删除、查找操作即可。
在二叉查找树中，查找、插入、删除等很多操作的工夫复杂度都跟树的高度成正比。两个极其状况的工夫复杂度别离是 O(n) 和 O(logn)，别离对应二叉树进化成链表的状况和齐全二叉树。
参考链接
js 二叉树
数据结构与算法之美-二叉树根底下
发表回复