算法- js 二叉树，二叉查找树的基本实现及递归与循环的版本
二叉树
二叉树是一种属性结构，它的特点是每个节点最多只有两个分支节点，一颗二叉树通常由根节点，分支节点，叶节点组成，而每个分支节点也常常被称作为一颗子树。
- 根节点：二叉树最顶层的节点
- 分支节点：除了根节点以外且拥有叶子节点
- 叶节点：除了自身没有其他节点
- 中节点：当前节点的父节点（中序遍历）
- 层
- 根的层次为0（一般来说），根的直接左右孩子层次为1，以此类推逐渐递增
- 度
- 二叉树节点的度数指该节点所含子树的个数
- 二叉树的深度是指所有节点中最深节点（叶节点）所在层数
常用术语： 在二叉树中，我们常常用父节点和子节点来描述，你如图中的2为6和3的父节点，反之6和3是2的子节点
二叉树的三个性质
- 在二叉树的第 i 层上，之多有 2 ^ (i - 1) 个节点
- i=1时，只有一个根节点，2^(i-1) = 2^0 = 1
深度为k的二叉树至多有2^k-1个节点. - i=2时，2^k-1 = 2^2 - 1 = 3个节点
对任何一棵二叉树T，如果总结点数为n0，度为2(子树数目为2)的节点数为n2,则n0=n2+1
树和二叉树的三个主要区别
- 树的节点个数至少为1，而二叉树的节点个数可以为0
- 树中节点的最大度数（节点数量）没有限制，而二叉树的节点最大度为 2
- 树的节点没有左右之分
二叉树分为完全二叉树（complete binary tree）和 满二叉树
- 二叉查找树 或 二叉搜索树
- 满二叉树：一颗深度为 k 且有 2 ^ k - 1个节点二叉树称为满二叉树
- 完全二叉树：最后一层左边是满的，右边可能满也可能不满，然后其余层都是满的二叉树称为完全二叉树（满二叉树也是一种完全二叉树）
二叉树的数组展示
用一个数组来展示二叉树的结构，将一组数组从根节点开始从上到下，从左到右一次填入一颗完全二叉树中
通过上图可以分析得到数组表示的完全二叉树有以下几个性质
left = index * 2 + 1，例如：根节点的下标为 0，则左节点的值为下标：arrary[0 * 2 + 1] = 1right = idnex * 2 + 2，例如：根节点的下标为 0，则有节点的值为下标：array[index * 2 + 2]- 序数 >= floor(N / 2) 都是叶节点，例如：floor(9 / 2) = 4
二叉搜索树
- 若左子树不为空，则左子树上所有的节点值均小于它的根节点的值；
- 若有子树不为空，则右子树上所有节点的值均大于它的根节点的值
- 左右子树也分别为二叉排序树
- 没有键相等的节点
根据上图首先定义相关方法
class BinaryTree {
}
const data = [6, 2, 3, 4, 9, 8, 7, 12, 1, 22];
const tree = new BinaryTree({data});添加节点
根据上面的特性添加节点
class BinaryTree {
// 定义基础节点
static Node = key => {
return {
key,
left: null,
right: null
}
}
constructor({data = []} = {}) {
this.root = null;
if (data.length) {
data.forEach(key => {
this.insertNode(key);
})
}
}
// 插入节点, 首次判断是否为根节点
insertNode(key) {
const node = BinaryTree.Node(key);
if (this.root === null) {
this.root = node;
} else {
this.insertNodeInTree(this.root, node)
}
}
// 往树中插入节点
// 并约定右子树的值永远大于左子树
insertNodeInTree(node, newNode) {
// 往当前节点的右子树插入
if (newNode.key > node.key) {
// 当前没有右子树
if (node.right === null) {
node.right = newNode
} else {
this.insertNodeInTree(node.right, newNode);
}
} else { // 左边做相同的操作
// 当前没有左子树
if (node.left === null) {
node.left = newNode
} else {
this.insertNodeInTree(node.left, newNode);
}
}
}
}二叉树的遍历算法
- 图中中序遍历结果：1 2 3 4 6 7 8 9 12 22
- 图中前序遍历结果：6 2 1 3 4 9 8 7 12 22
- 图中后序遍历结果：1 4 3 2 7 8 22 12 9 6
中序遍历（递归和循环）
先处理左节点（左子树），在处理中节点（父节点），最后处理右节点
class BinaryTree {
// 中序遍历
// 先处理左节点（左子树），在处理中节点（当前节点的父节点），最后处理有节点（右子树），递归遍历所有节点
static traverseNodesLDR(node, callback) {
if (node !== null) {
BinaryTree.traverseNodesLDR(node.left, callback);
callback?.(node);
BinaryTree.traverseNodesLDR(node.right, callback)
}
}
// 中序遍历 循环版
static traverseNodesLDRforWhile(node, callback) {
const stack = [];
let currentNode = node;
while (stack.length || currentNode) {
// 判断当前 node，存在就向 stack 中 push 当前的左子节点
if (currentNode) {
stack.push(currentNode);
currentNode = currentNode.left;
} else {
currentNode = stack.pop();
callback?.(currentNode)
currentNode = currentNode.right;
}
}
}
// 中序遍历，左 => 中 => 右
LDR(callback) {
// BinaryTree.traverseNodesLDR(this.root, callback)
BinaryTree.traverseNodesLDRforWhile(this.root, callback)
}
}
// 中序遍历
tree.LDR(function (node) {
console.log(node);
});前序遍历（先序遍历）
class BinaryTree {
// 前序遍历
// 先处理 中节点（父节点），在处理左节点（左子节点），最后处理右节点（右子节点）
static traverseNodesDLR(node, callback) {
if (node !== null) {
callback?.(node);
BinaryTree.traverseNodesDLR(node.left, callback);
BinaryTree.traverseNodesDLR(node.right, callback);
}
}
// 前序遍历 循环
static traverseNodesDLRforWhile(node, callback) {
let currentNode = node;
const stack = [currentNode];
while (stack.length) {
currentNode = stack.pop();
callback?.(currentNode);
// 先 push right，pop 取得时候 left 即可在前
if (currentNode.right) stack.push(currentNode.right);
if (currentNode.left) stack.push(currentNode.left);
}
}
// 前(先)序遍历 中 => 左 => 右
DLR(callback) {
// BinaryTree.traverseNodesDLR(this.root, callback)
BinaryTree.traverseNodesDLRforWhile(this.root, callback)
}
}
// 先序遍历
tree.DLR(function (node) {
console.log(node);
});后序遍历
左 => 右 => 中
class BinaryTree {
// 后序列遍历
// 先处理 左节点（右节点），在处理右节点（左节点）最后处理中节点
static traverseNodesLRD(node, callback) {
if (node !== null) {
BinaryTree.traverseNodesLRD(node.left, callback);
BinaryTree.traverseNodesLRD(node.right, callback);
callback?.(node);
}
}
// 后序遍历 左，右，中
static traverseNodesLRDForWhile(node, callback) {
// 标记叶节点，当遇到叶节点将返回他的父节点，标记下次循环时跳过当前叶节点
let currentNode = node;
const stack = [currentNode];
let fNode = null;
while (stack.length) {
fNode = stack[stack.length - 1];
if (fNode.left && currentNode !== fNode.left && currentNode !== fNode.right) {
stack.push(fNode.left);
} else if (fNode.right && currentNode !== fNode.right) {
stack.push(fNode.right)
} else {
callback?.(stack.pop());
currentNode = fNode;
}
}
}
// 后续遍历 左 => 右 => 中
LRD(callback) {
// BinaryTree.traverseNodesLRD(this.root, callback);
BinaryTree.traverseNodesLRDForWhile(this.root, callback);
}
}
// 后序遍历
tree.LRD(function (node) {
console.log(node);
});查找最大值
因为是搜索树，所以约定了右树是大的一边，所以找到右树中的叶节点即可（最小值同理）
class BinaryTree {
getMaxValue(callback) {
// this.traverseRight(this.root, callback)
this.traverseRightForWhile(this.root, callback)
}
traverseRight(node, callback) {
if (node !== null) {
// 如果有右节点则继续递归，没有那当前就是最大值
if (node.right !== null) {
this.traverseRight(node.right, callback);
} else callback?.(node)
} else {
callback?.('xxxx')
}
}
// 遍历右子树循环版
traverseRightForWhile(node, callback) {
let currentNode = node;
while (currentNode) {
if (currentNode.right) currentNode = currentNode.right;
else {
callback?.(currentNode);
currentNode = null;
}
}
}
}
tree.getMaxValue(function (node) {
console.log(node);
})查找最小值
class BinaryTree {
// 获取最小值
getMinValue(callback) {
return this.traverseLeft(this.root, callback)
}
traverseLeft(node, callback) {
!callback && console.log(node, 'node');
if (node !== null) {
if (node.left !== null) {
if (callback) this.traverseLeft(node.left, callback);
else return this.traverseLeft(node.left, callback);
}
else {
if (callback) callback?.(node)
else return node
}
} else callback?.('xxxx')
}
}
tree.getMinValue(function (node) {
console.log(node);
})查找指定的值
当传入的
key大于根节点则只需在右子树中寻找，反之同理
class BinaryTree {
// 查找指定 key
findNode(targetKey) {
// return this.traverseNode(this.root, targetKey);
return this.traverseNodeForWhile(this.root, targetKey);
}
// 遍历树，如果指定的 key 小于根节点则继续遍历左节点反之亦然
traverseNode(node, targetKey) {
if (node !== null) {
// 目标存在于 右子树
if (targetKey > node.key) {
return this.traverseNode(node.right, targetKey);
} else if (targetKey < node.key) {
return this.traverseNode(node.left, targetKey);
} else {
return node;
}
}
}
// 查找指定的值 循环版
traverseNodeForWhile(node, targetKey) {
let currentNode = node;
let resultNode = null;
while (currentNode) {
if (targetKey > currentNode.key) currentNode = currentNode.right;
else if (targetKey < currentNode.key) currentNode = currentNode.left;
else {
resultNode = currentNode;
currentNode = null;
}
}
return resultNode;
}
}
// 查找指定的值
const target = tree.findNode(22);删除节点
- 删除叶节点：把当前节点设为 null
- 删除仅包含 左子节点 的中节点：把当前节点赋值为左子节点即可（单右节点同理）
- 删除包含左右节点的值：为了让其继续维持约定，所以被替换的值最合适的为当前节点的右节点中最小的值，赋值的同时并删除右边最小的值
class BinaryTree {
// 删除节点
removeNode(key) {
this.removeNodeByKey(this.root, key)
}
removeNodeByKey(node, key) {
if (node === null) return node;
// 找到指定节点
if (key > node.key) {
node.right = this.removeNodeByKey(node.right, key);
return node;
} else if (key < node.key) {
node.left = this.removeNodeByKey(node.left, key);
return node;
}
// 叶节点处理
if (node.left === null && node.right === null) {
return node = null
}
// 删除只有右子树的节点
// 只要把右子树赋值上去即可
if (node.left === null) {
return node = node.right;
}
// 删除只有左子树的节点
// 操作同上
if (node.right === null) {
return node = node.left;
}
// 删除包含左右子节点的节点
// 为了让继续维持约定，所以被替换的值最合适的为当前节点的右节点中最小的值，赋值的同时并删除右边最小的值
const minValue = this.traverseLeft(node.right)
node.key = minValue.key;
node.right = this.removeNodeByKey(node.right, minValue.key)
return node
}
}
console.log(tree.removeNode(9));源码
class BinaryTree {
static Node = key => {
return {
key,
left: null,
right: null
}
}
// 中序遍历
// 先处理左节点（左子树），在处理中节点（当前节点的父节点），最后处理有节点（右子树），递归遍历所有节点
static traverseNodesLDR(node, callback) {
if (node !== null) {
BinaryTree.traverseNodesLDR(node.left, callback);
callback?.(node);
BinaryTree.traverseNodesLDR(node.right, callback)
}
}
// 中序遍历 循环版
// 左 => 中 => 右
// 6
// 2 9
// 1 3 8 12
// 4 7 22
//
static traverseNodesLDRforWhile(node, callback) {
const stack = [];
let currentNode = node;
while (stack.length || currentNode) {
// 判断当前 node，存在就向 stack 中 push 当前的左子节点
if (currentNode) {
stack.push(currentNode);
currentNode = currentNode.left;
} else {
currentNode = stack.pop();
callback?.(currentNode)
currentNode = currentNode.right;
}
}
}
// 前序遍历
// 先处理 中节点（父节点），在处理左节点（左子节点），最后处理右节点（右子节点）
static traverseNodesDLR(node, callback) {
if (node !== null) {
callback?.(node);
BinaryTree.traverseNodesDLR(node.left, callback);
BinaryTree.traverseNodesDLR(node.right, callback);
}
}
// 前序遍历 循环
// 中 左 右
// 6
// 2 9
// 1 3 8 12
// 4 7 22
static traverseNodesDLRforWhile(node, callback) {
let currentNode = node;
const stack = [currentNode];
while (stack.length) {
currentNode = stack.pop();
callback?.(currentNode);
// 先 push right，pop 取得时候 left 即可在前
if (currentNode.right) stack.push(currentNode.right);
if (currentNode.left) stack.push(currentNode.left);
}
}
// 后序列遍历
// 先处理 左节点（右节点），在处理右节点（左节点）最后处理中节点
static traverseNodesLRD(node, callback) {
if (node !== null) {
BinaryTree.traverseNodesLRD(node.left, callback);
BinaryTree.traverseNodesLRD(node.right, callback);
callback?.(node);
}
}
// 后序遍历 左，右，中
// 6
// 2 9
// 1 3 8 12
// 4 7 22
static traverseNodesLRDForWhile(node, callback) {
// 标记叶节点，当遇到叶节点将返回他的父节点，标记下次循环时跳过当前叶节点
let currentNode = node;
const stack = [currentNode];
let fNode = null;
while (stack.length) {
fNode = stack[stack.length - 1];
if (fNode.left && currentNode !== fNode.left && currentNode !== fNode.right) {
stack.push(fNode.left);
} else if (fNode.right && currentNode !== fNode.right) {
stack.push(fNode.right)
} else {
callback?.(stack.pop());
currentNode = fNode;
}
}
}
constructor({data = []} = {}) {
this.root = null;
if (data.length) {
data.forEach(key => {
this.insertNode(key);
})
}
}
// 插入节点, 首次判断是否为根节点
insertNode(key) {
const node = BinaryTree.Node(key);
if (this.root === null) {
this.root = node;
} else {
this.insertNodeInTree(this.root, node)
}
}
// 往树中插入节点
// 并预定右子树的值永远大于左子树
insertNodeInTree(node, newNode) {
// 往当前节点的右子树插入
if (newNode.key > node.key) {
// 当前没有右子树
if (node.right === null) {
node.right = newNode
} else {
this.insertNodeInTree(node.right, newNode);
}
} else { // 左边做相同的操作
// 当前没有右子树
if (node.left === null) {
node.left = newNode
} else {
this.insertNodeInTree(node.left, newNode);
}
}
}
// 中序遍历，左 => 中 => 右
LDR(callback) {
// BinaryTree.traverseNodesLDR(this.root, callback)
BinaryTree.traverseNodesLDRforWhile(this.root, callback)
}
// 前(先)序遍历 中 => 左 => 右
DLR(callback) {
// BinaryTree.traverseNodesDLR(this.root, callback)
BinaryTree.traverseNodesDLRforWhile(this.root, callback)
}
// 后续遍历 左 => 右 => 中
LRD(callback) {
// BinaryTree.traverseNodesLRD(this.root, callback);
BinaryTree.traverseNodesLRDForWhile(this.root, callback);
}
// 获取树中最大的节点，有限遍历右节点
getMaxValue(callback) {
// this.traverseRight(this.root, callback)
this.traverseRightForWhile(this.root, callback)
}
// 获取最小值
getMinValue(callback) {
return this.traverseLeft(this.root, callback)
}
// 遍历右子树
traverseRight(node, callback) {
if (node !== null) {
// 如果有右节点则继续递归，没有那当前就是最大值
if (node.right !== null) {
this.traverseRight(node.right, callback);
} else callback?.(node)
} else {
callback?.('xxxx')
}
}
// 遍历右子树循环版
traverseRightForWhile(node, callback) {
let currentNode = node;
while (currentNode) {
if (currentNode.right) currentNode = currentNode.right;
else {
callback?.(currentNode);
currentNode = null;
}
}
}
// 遍历左子树
traverseLeft(node, callback) {
!callback && console.log(node, 'node');
if (node !== null) {
if (node.left !== null) {
if (callback) this.traverseLeft(node.left, callback);
else return this.traverseLeft(node.left, callback);
}
else {
if (callback) callback?.(node)
else return node
}
} else callback?.('xxxx')
}
// 查找指定 key
findNode(targetKey) {
// return this.traverseNode(this.root, targetKey);
return this.traverseNodeForWhile(this.root, targetKey);
}
// 遍历树，如果指定的 key 小于根节点则继续遍历左节点反之亦然
traverseNode(node, targetKey) {
if (node !== null) {
// 目标存在于 右子树
if (targetKey > node.key) {
return this.traverseNode(node.right, targetKey);
} else if (targetKey < node.key) {
return this.traverseNode(node.left, targetKey);
} else {
return node;
}
}
}
// 查找指定的值 循环版
traverseNodeForWhile(node, targetKey) {
let currentNode = node;
let resultNode = null;
while (currentNode) {
if (targetKey > currentNode.key) currentNode = currentNode.right;
else if (targetKey < currentNode.key) currentNode = currentNode.left;
else {
resultNode = currentNode;
currentNode = null;
}
}
return resultNode;
}
// 删除节点
removeNode(key) {
this.removeNodeByKey(this.root, key)
}
/**
* 1. 删除的节点为 叶节点：直接指向 null
* 2. 删除的节点仅包含一个子节点：
*/
removeNodeByKey(node, key) {
if (node === null) return node;
// 找到指定节点
if (key > node.key) {
node.right = this.removeNodeByKey(node.right, key);
return node;
} else if (key < node.key) {
node.left = this.removeNodeByKey(node.left, key);
return node;
}
// 叶节点处理
if (node.left === null && node.right === null) {
return node = null
}
// 删除只有右子树的节点
// 只要把右子树赋值上去即可
if (node.left === null) {
return node = node.right;
}
// 删除只有左子树的节点
// 操作同上
if (node.right === null) {
return node = node.left;
}
// 删除包含左右子节点的节点
// 为了让继续维持约定，所以被替换的值最合适的为当前节点的右节点中最小的值，赋值的同时并删除右边最小的值
const minValue = this.traverseLeft(node.right)
node.key = minValue.key;
node.right = this.removeNodeByKey(node.right, minValue.key)
return node
}
}
// 6
// 2 9
// 1 3 8 12
// 4 7 11 22
// 21
//
const data = [6, 2, 3, 4, 9, 8, 7, 12, 1, 22, 21, 11];
const tree = new BinaryTree({data});
console.log(tree);
// 中序遍历
tree.LDR(function (node) {
// console.log(node);
});
// 先序遍历
tree.DLR(function (node) {
// console.log(node);
});
// 后序遍历
tree.LRD(function (node) {
// console.log(node);
});
// 查找最大值
tree.getMaxValue(function (node) {
// console.log(node);
})
// 查找 最小值
tree.getMinValue(function (node) {
// console.log(node);
})
// 查找指定的值
const target = tree.findNode(22);
// 删除指定值
console.log(tree.removeNode(9));本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 kshao-blog-前端知识记录！
- 微信
- 支付宝
评论
最新文章
