JS 数据结构 – 二叉树
二叉树
二叉树（Binary tree）是树形结构的一个重要类型。许多实际问题抽象出来的数据结构往往是二叉树形式，即使是一般的树也能简单地转换为二叉树，而且二叉树的存储结构及其算法都较为简单，因此二叉树显得特别重要。二叉树特点是每个节点最多只能有两棵子树，且有左右之分。
二叉树是n个有限元素的集合，该集合或者为空、或者由一个称为根（root）的元素及两个不相交的、被分别称为左子树和右子树的二叉树组成，是有序树。当集合为空时，称该二叉树为空二叉树。在二叉树中，一个元素也称作一个节点。
因此，在此之前，需要先定义节点。
// node.ts
/**
* @description 二叉搜索树节点命名空间
* @namespace binarySearchTreeNode
*/
export namespace binarySearchTreeNode {
export class Node<T> {
public left: Node<T> | undefined
public right: Node<T> | undefined
constructor (public element: T) {}
toString () {
return `${this.element}`
}
}
}
二叉搜索树
import { binarySearchTreeNode } from '../Node'
/**
* @description 抽象二叉搜索树命名空间
* @namespace abstract_BinarySearchTree
*/
export namespace abstract_BinarySearchTree {
export abstract class BinarySearchTree<T> {
protected root!: binarySearchTreeNode.Node<T>
/** 返回根节点 */
abstract getRoot (): binarySearchTreeNode.Node<T>
/** 返回最小元素 */
abstract min (): binarySearchTreeNode.Node<T>
/** 返回最大元素 */
abstract max (): binarySearchTreeNode.Node<T>
/** 指定子树下的最小元素 */
protected abstract minNode (node: binarySearchTreeNode.Node<T>): binarySearchTreeNode.Node<T>
/** 指定子树下的最大元素 */
protected abstract maxNode (node: binarySearchTreeNode.Node<T>): binarySearchTreeNode.Node<T>
/**
* 先序遍历 \
* 执行回调 -> 左 -> 右\
* 访问顺序为 父节点优先\
* 适合打印结构化文档
*/
abstract preOrderTraverse (callback: Function): void
/** 先序遍历调用方法 */
protected abstract preOrderTraverseNode (node: binarySearchTreeNode.Node<T>, callBack: Function): void
/**
* 中序遍历 \
* 左 -> 执行回调 -> 右\
* 访问顺序为 从小到大\
* 适合打印排序后结果
*/
abstract inOrderTraverse (callback: Function): void
/** 中序遍历调用方法 */
protected abstract inOrderTraverseNode (node: binarySearchTreeNode.Node<T>, callback: Function): void
/**
* 后序遍历\
* 左 -> 右 -> 执行回调\
* 访问顺序为 子节点优先\
* 适合应用于计算大小
*/
abstract postOrderTraverse (callback: Function): void
/** 后续遍历调用方法 */
protected abstract postOrderTraverseNode (node: binarySearchTreeNode.Node<T>, callback: Function): void
/**
* 搜索元素 \
* 当 element 比 node.element 小时向左查 否则向右 直到找到或为 null
*/
abstract search (element: T): boolean
/** 搜索调用方法 */
protected abstract searchNode (node: binarySearchTreeNode.Node<T>, element: T): boolean
/**
* 增加元素 \
* 首先判断树是否为空，为空插入根节点\
* 否则通过递归判断大小插入
*/
abstract insert (element: T): void
/** 插入递归方法 */
protected abstract insertNode (node: binarySearchTreeNode.Node<T>, element: T): void
/**
* 删除元素\
* 二叉搜索树是有序的\
* 所以插入的时候会查到正确的位置，不会插入到树中间\
* 但是在删除时，会将树中的任何一个节点（包括树中间节点）删除\
* 因此必须重构树的结构\
* 删除可分为三种情况：
* - 删除叶子节点
* - 这是最简单的，因为叶子节点被删除后不涉及树结构的重构
*
* - 删除只有一个子节点的节点
* - 删除只有一个左侧或右侧子节点的节点后，子树就孤立了，需要将子树融入树中
* - 只需要将子节点夹带子树代替被删除的节点即可
*
* - 删除有两个子节点的节点
* - 需要被删除的节点的右子树中找到最小的节点，然后替代掉被删除节点的位置
* - 因为二叉搜索树的结构是 小 > 中 > 大 的
* - 在重新指向右侧子树建立结构
*/
abstract remove (element: T): binarySearchTreeNode.Node<T>
/** 删除元素调用方法 */
protected abstract removeNode (node: binarySearchTreeNode.Node<T>, element: T): binarySearchTreeNode.Node<T>
}
}
/**
* @description 实例二叉搜索树命名空间
* @namespace example_BinarySearchTree
*/
export namespace example_BinarySearchTree {
class BinarySearchTree<T> extends abstract_BinarySearchTree.BinarySearchTree<T> {
getRoot (): binarySearchTreeNode.Node<T> {
return this.root
}
min (): binarySearchTreeNode.Node<T> {
return this.minNode(this.root)
}
protected minNode (node: binarySearchTreeNode.Node<T>): binarySearchTreeNode.Node<T> {
/** 指向当前节点的指针 */
let current: binarySearchTreeNode.Node<T> = node
// 不断向左查
// 直到左子节点为空
// 只有循环执行， 则证明左子节点不为空
while (current !== null && current.left !== null) {
// 感叹号表示没问题，否则提示类型错误
current = current.left!
}
return current
}
max (): binarySearchTreeNode.Node<T> {
return this.maxNode(this.root)
}
protected maxNode (node: binarySearchTreeNode.Node<T>): binarySearchTreeNode.Node<T> {
/** 指向当前节点的指针 */
let current: binarySearchTreeNode.Node<T> = node
// 不断向右查
while (current !== null && current.right !== null) {
current = current.right!
}
return current
}
preOrderTraverse (callback: Function): void {
this.preOrderTraverseNode(this.root, callback)
}
protected preOrderTraverseNode (node: binarySearchTreeNode.Node<T>, callBack: Function): void {
// 基线条件
if (node !== null) {
// 先序遍历的指向顺序是 执行回调 -> 左 -> 右
callBack(node.element)
this.preOrderTraverseNode(node.left!, callBack)
this.preOrderTraverseNode(node.right!, callBack)
}
}
inOrderTraverse (callback: Function): void {
// 调用中序遍历迭代方法
this.inOrderTraverseNode(this.root, callback)
}
protected inOrderTraverseNode (node: binarySearchTreeNode.Node<T>, callback: Function): void {
// 基线条件
if (node !== null) {
// 中序遍历的顺序是 左 -> 执行回调 -> 右
this.inOrderTraverseNode(node.left!, callback)
callback(node.element)
this.inOrderTraverseNode(node.right!, callback)
}
}
postOrderTraverse (callback: Function): void {
// 调用后序遍历迭代方法
this.postOrderTraverseNode(this.root, callback)
}
protected postOrderTraverseNode (node: binarySearchTreeNode.Node<T>, callback: Function): void {
// 基线条件
if (node !== null) {
// 后序遍历的执行顺序是 左 -> 右 -> 执行回调
this.postOrderTraverseNode(node.left!, callback)
this.postOrderTraverseNode(node.right!, callback)
callback(node.element)
}
}
search (element: T): boolean {
// 调用递归方法
return this.searchNode(this.root, element)
}
protected searchNode (node: binarySearchTreeNode.Node<T>, element: T): boolean {
// 基线条件： 查到尽头返回 false
if (node === null) return false
// 如果 需要搜索的元素 大于 当前节点值
// 向右查找
if (element > node.element) {
return this.searchNode(node.right!, element)
}
// 如果 需要搜索的元素 小于 当前节点值
// 向左查找
else if (element < node.element) {
return this.searchNode(node.left!, element)
}
// 否则为等于， 找到了需要搜索的元素
else return true
}
insert (element: T): void {
if (this.root === null) {
// 边界情况： 插入到节点
this.root = new binarySearchTreeNode.Node<T>(element)
} else {
// 递归找到插入位置
this.insertNode(this.root, element)
}
}
protected insertNode (node: binarySearchTreeNode.Node<T>, element: T) {
// 如果需要 插入的元素 比 当前节点元素 小
// 向左查
if (element < node.element) {
if (node.left === null) {
// 基线条件： 左节点为空直接赋值
node.left = new binarySearchTreeNode.Node<T>(element)
} else {
// 否则接着递归
this.insertNode(node.left!, element)
}
// 否则比 当前节点大
// 向右查
} else if (element > node.element) {
if (node.right === null) {
// 基线条件：右节点为空直接赋值
node.right = new binarySearchTreeNode.Node<T>(element)
} else {
// 否则接着递归
this.insertNode(node.right!, element)
}
}
// 否则等于
}
remove (element: T): binarySearchTreeNode.Node<T> {
// 调用递归方法，将删除后的树返回替换当前树
return this.root = this.removeNode(this.root, element)
}
protected removeNode (node: binarySearchTreeNode.Node<T>, element: T): binarySearchTreeNode.Node<T> {
// 基线条件
if (node === null) return node
// 当 需要删除的值 比 当前节点值 小
// 向左查
if (element < node.element) {
node.left = this.removeNode(node.left!, element)
return node
}
// 当 需要删除的值 比 当前节点值 大
// 向右查
else if (element > node.element) {
node.right = this.removeNode(node.right!, element)
return node
}
// 此时已查到需要删除的节点
else {
// 如果是叶子节点
if (node.left === null && node.right === null) {
node = null!
return node
}
// 当只有一个叶子节点时
else if (node.left === null) {
node = node.right!
return node
}
// 当只有一个叶子节点时
else if (node.right === null) {
node = node.left!
return node
}
// 否则有两个子节点
else {
const aux = this.minNode(node.right!)
node.element = aux.element
node.right = this.removeNode(node.right!, aux.element)
return node
}
}
}
}
平衡二叉树
在AVL树中，任一节点对应的两棵子树的最大高度差为1，因此它也被称为高度平衡树。
二叉搜索树一定程度上可以提高搜索效率，但是当原序列有序时，例如序列 A = {1，2，3，4，5，6}，构造二叉搜索树如图 1.1。依据此序列构造的二叉搜索树为右斜树，同时二叉树退化成单链表，搜索效率降低为 O(n)。
import { binarySearchTreeNode } from '../Node';
import { example_BinarySearchTree } from './BinarySearchTree';
/**
* @namespace AVLTree_utils
* @description AVL树工具命名空间
*/
export namespace AVLTree_utils {
/**
* 平衡因子枚举
*/
export enum BalanceFactor {
/** 右重 */
UNBALANCED_RIGHT = -2,
/** 轻微右重 */
SLIGHTLY_UNBALANCED_RIGHT = -1,
/** 平衡 */
BALANCED = 0,
/** 轻微左重 */
SLIGHTLY_UNBALANCED_LEFT = 1,
/** 左重 */
UNBALANCED_LEFT = 2
}
/**
* 获取节点高度
*/
export type getNodeHeight<T> = (node: binarySearchTreeNode.Node<T>) => number
/**
* 获取节点平衡因子
*/
export type getBalanceFActor<T> = (node: binarySearchTreeNode.Node<T>) => number
}
class AVLTree<T> extends example_BinarySearchTree.BinarySearchTree<T> {
constructor() { super() }
/** 获取节点高度 */
protected getNodeHeight(node: binarySearchTreeNode.Node<T>): number {
// 基线条件
if (node === null) return -1
// 递归计算
// Math.max 会选出最大数
// 节点高度为取最大高度
return Math.max(this.getNodeHeight(node.left!), this.getNodeHeight(node.right!)) + 1
}
/** 获取节点平衡因子 */
protected getBalanceFactor(node: binarySearchTreeNode.Node<T>): AVLTree_utils.BalanceFactor {
// 左子树重 减去 右子树重
const heightDifference = this.getNodeHeight(node.left!) - this.getNodeHeight(node.right!)
// 再返回对应的枚举值
switch (heightDifference) {
case -2:
return AVLTree_utils.BalanceFactor.UNBALANCED_RIGHT;
case -1:
return AVLTree_utils.BalanceFactor.SLIGHTLY_UNBALANCED_RIGHT;
case 1:
return AVLTree_utils.BalanceFactor.SLIGHTLY_UNBALANCED_LEFT;
case 2:
return AVLTree_utils.BalanceFactor.UNBALANCED_LEFT;
default:
return AVLTree_utils.BalanceFactor.BALANCED;
}
}
/**
* 左左情况：向右单旋转
* 左侧子节点的高度大于右侧子节点的高度时
* 且左侧子节点也是平衡或左侧较重的，为左左情况
*
* a b
* /\ /\
* b c -> rotationLL(a) -> d a
* /\ /\
* d e e c
*
* @param root Node<T> 旋转前的root节点
* @returns pivot Node<T> 返回旋转后的root节点(也就是旋转前的pivot)
*/
protected rotationLL(root: binarySearchTreeNode.Node<T>): binarySearchTreeNode.Node<T> {
// 先将 pivot 取出
const pivot = root.left
// root 左侧指向 pivot 的右子节点
root.left = pivot?.right
// pivot 右侧指向 root
pivot!.right = root
// 返回 pivot
return pivot!
}
/**
* 右右情况: 向左单旋转
* 右侧子节点的高度大于左侧子节点的高度，并且右侧子节点也是平衡或右侧较重的，为右右情况
*
* a c
* /\ /\
* b c -> rotationRR(a) -> a e
* /\ /\
* d e b d
*
* @param root Node<T> 旋转前的root节点
* @returns pivot Node<T> 返回旋转后的root节点(也就是旋转前的pivot)
*/
protected rotationRR(root: binarySearchTreeNode.Node<T>): binarySearchTreeNode.Node<T> {
// 先把pivot拿出来
const pivot = root.right
// root 右侧指向 pivot 的左子
root.right = pivot?.left
// pivot 左侧指向 root
pivot!.left = root
// 返回 pivot
return pivot!
}
/**
* 左右情况: 先左转子节点后右转
* 左侧子节点的高度大于右侧子节点的高度，并且左侧子节点右侧较重
*
* a a e
* /\ /\ /\
* b c -> rotationRR(b) -> e c -> rotationLL(a) -> b a
* /\ /\ /\ /\
* d e b g d f g c
* /\ /\
* f g d f
*
*/
protected rotationLR(node: binarySearchTreeNode.Node<T>): binarySearchTreeNode.Node<T> {
// 先把节点左子左转
node.left = this.rotationRR(node.left!)
// 再把节点本身右转
return this.rotationLL(node)
}
/**
* 右左情况: 先右转子节点后左转
* 右侧子节点的高度大于左侧子节点的高度，并且右侧子节点左侧较重
*
* a a d
* /\ /\ /\
* b c -> rotationLL(c) -> b d -> rotationRR(a) -> a c
* /\ /\ /\ /\
* d e f c b f g e
* /\ /\
* f g g e
*
*/
protected rotationRL(node: binarySearchTreeNode.Node<T>): binarySearchTreeNode.Node<T> {
// 先把节点右子右转
node.right = this.rotationLL(node.right!)
// 再把节点本身左转
return this.rotationRR(node)
}
/**
* 对节点为根的树进行两层平衡
*/
keepBalance(node: binarySearchTreeNode.Node<T>): binarySearchTreeNode.Node<T> {
// 先验证是否平衡 只有 左重 和 右重 时才需要重新平衡
if (node === null) return node
// 验证树是否平衡
const balanceState = this.getBalanceFactor(node)
//================================================================================
// 左重
//================================================================================
if (balanceState === AVLTree_utils.BalanceFactor.UNBALANCED_LEFT) {
// 左左情况
if (
this.getBalanceFactor(node.left!) ===
AVLTree_utils.BalanceFactor.BALANCED ||
this.getBalanceFactor(node.left!) ===
AVLTree_utils.BalanceFactor.SLIGHTLY_UNBALANCED_LEFT
) return this.rotationLL(node)
// 左右情况
else if (
this.getBalanceFactor(node.left!) ===
AVLTree_utils.BalanceFactor.SLIGHTLY_UNBALANCED_RIGHT
) return this.rotationLR(node)
//================================================================================
// 右重
//================================================================================
} else if (balanceState === AVLTree_utils.BalanceFactor.UNBALANCED_RIGHT) {
// 右右情况
if (
this.getBalanceFactor(node.right!) ===
AVLTree_utils.BalanceFactor.BALANCED ||
this.getBalanceFactor(node.right!) ===
AVLTree_utils.BalanceFactor.SLIGHTLY_UNBALANCED_RIGHT
) return this.rotationRR(node)
// 右左情况
else if (
this.getBalanceFactor(node.right!) ===
AVLTree_utils.BalanceFactor.SLIGHTLY_UNBALANCED_LEFT
) return this.rotationRL(node)
}
// “轻微左重”、“轻微右重”、“平衡”的三种状态不需要再平衡，直接返回
return node
}
/**
* 插入之后需要进行平衡
*/
protected insertNode(node: binarySearchTreeNode.Node<T>, element: T): binarySearchTreeNode.Node<T> {
super.insertNode(node, element)
return this.keepBalance(node)
}
/**
* 删除节点之后进行平衡
*/
protected removeNode(node: binarySearchTreeNode.Node<T>, element: T): binarySearchTreeNode.Node<T> {
super.removeNode(node, element)
return this.keepBalance(node)
}
}
JS 数据结构 – 二叉树
http://localhost:8080/archives/e7619ae7-f9a6-4a4a-9feb-24504e900e93