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 &amp;&amp; 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 &amp;&amp; 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 &amp;&amp; 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
作者
inksha
发布于
2024年09月14日
许可协议