二叉树(BinaryTree)

每个节点的度，最大为 2 的树
有序树

性质

非空二叉树的第 i 层,最多有 2^i-1个节点(i>=1)
在高度为 h 的二叉树上最多有 2^h-1 个节点(h>=1)
对于任何一棵非空二叉树，如果叶子节点个数 n0,度为 2 的节点个数为 n2，则 n0=n2+1
- 校验
- 二叉树节点总个数为 n=n0+n1+n2
- 二叉树边的个数 2 为 t=n1+2*n2
- 节点数=边数+1,n0+n1+n2 = n1+2*n2+1
- 因此 n0=n2+1

真二叉树

没有度为 1 的二叉树

满二叉树

最后一层节点度都为 0，其他节点的度为 2 的二叉树，满二叉树一定是真二叉树，真二叉树不一定是满二叉树

假设高度为 h,总节点数为 n，那么
第 i 层节点数为 2^i-1
叶子节点数为 2^h-1
总结点数 n=2^h-1=2⁰+2²+2³+...+2^h-1
高度为 h=log₂(n+1)

完全二叉树

对节点从上至下、从左至右开始编号，其所有编号都能与相同高度的满二叉树中的编号对应

叶子节点只会出现在最后 2 层，最后 1 层的叶子节点都靠左对齐
完全二叉树从根节点至倒数第 2 层是一棵满二叉树
满二叉树一定是完全二叉树，完全二叉树不一定是满二叉树

前驱节点

对于一棵树进行中序遍历后，一个节点的前一个节点即为前驱节点

后驱节点

对于一棵树进行中序遍历后，一个节点的后一个节点即为后驱节点

性质

度为 1 的节点只有左子树
度为 1 的节点要么是 1 个，要么是 0 个
同样节点数量的二叉树，完全二叉树的高度最小
假设完全二叉树高度为 h 那么
- 至少有 2^h-1个节点(2⁰+2²+2³+...+2^h-2+1)
- 至多有 2^h-1 个节点(2⁰+2²+2³+...+2^h-1,满二叉树)
总结点数为 n
- 2^h-1<=n<^h
- h-1<=log₂n<h
- h=Math.floor(log₂n)+1
一棵有 n 个节点的完全二叉树(n>0),从上到下、从左到右节点从 1 开始编号，对任意第 i 个节点
- 如果 i=1，则它是根节点
- 如果 i>1,它的父节点为 Math.floor(i/2)
- 如果 2*i<=n,它的左子节点编号为 2*i
- 如果 2*i>n,它无左子节点
- 如果 2*i+1<=n,它的右子节点编号为 2*i+1
- 如果 2*i+1>n,它无右子节点
一棵有 n 个节点的完全二叉树(n>0),从上到下、从左到右节点从 0 开始编号，对任意第 i 个节点
- 如果 i=0，则它是根节点
- 如果 i>0,它的父节点为 Math.floor((i-1)/2)
- 如果 2*i+1<=n-1,它的左子节点编号为 2*i+1
- 如果 2*i+1>n-1,它无左子节点
- 如果 2*i+2<=n-1,它的右子节点编号为 2*i+2
- 如果 2*i+2>n-1,它无右子节点

核心代码

import { Comparator } from '@/shared';
import { repeat } from 'lodash';
/** 节点的度 */
export type BinaryTreeNodeDegree = 0 | 1 | 2;
/** 节点是父节点的左右子树 */
export enum BinaryTreeNodeChildPosition {
  LEFT = 'left',
  RIGHT = 'right',
}
export const reverseBinaryTreeNodeChildPosition = (pos: BinaryTreeNodeChildPosition) =>
  pos === BinaryTreeNodeChildPosition.LEFT
    ? BinaryTreeNodeChildPosition.RIGHT
    : BinaryTreeNodeChildPosition.LEFT;
/** 二叉树节点 */
export class BinaryTreeNode<T> {
  /** 树的度 */
  get degree(): BinaryTreeNodeDegree {
    if (this.left !== null && this.right !== null) return 2;
    else if (this.left !== null || this.right !== null) return 1;
    else return 0;
  }
  /** 是父节点的左子节点 */
  get isLeftChild(): boolean {
    return !!(this.parent?.left === this);
  }
  /** 是父节点的右子节点 */
  get isRightChild(): boolean {
    return !!(this.parent?.right === this);
  }
  get childPosition(): BinaryTreeNodeChildPosition {
    return this.isLeftChild ? BinaryTreeNodeChildPosition.LEFT : BinaryTreeNodeChildPosition.RIGHT;
  }
  get sibling(): BinaryTreeNode<T> | null {
    return this.parent === null
      ? null
      : this.parent[reverseBinaryTreeNodeChildPosition(this.childPosition)];
  }
  constructor(
    /** 节点储存的值 */
    public val: T,
    /** 父节点 */
    public parent: BinaryTreeNode<T> | null = null,
    /** 左子节点 */
    public left: BinaryTreeNode<T> | null = null,
    /** 右子节点 */
    public right: BinaryTreeNode<T> | null = null
  ) {}
  /** 从父节点移除自己 */
  remove() {
    if (this.parent === null) return;
    this.parent[this.childPosition] = null;
  }
  /** 后驱节点 */
  successor(): BinaryTreeNode<T> | null {
    // 如果没有右节点时找是父节点左节点的祖先节点
    if (this.right === null) {
      let node: BinaryTreeNode<T> | null = this;
      while (node.parent !== null && node.isRightChild) node = node.parent;
      return node.parent;
    }
    let successor = this.right;
    while (successor.left !== null) successor = successor.left;
    return successor;
  }
  /** 前驱节点 */
  predecessor(): BinaryTreeNode<T> | null {
    // 如果没有左节点时找是父节点右节点的祖先节点
    if (this.left === null) {
      let node: BinaryTreeNode<T> | null = this;
      while (node.parent !== null && node.isLeftChild) node = node.parent;
      return node.parent;
    }
    let predecessor = this.left;
    while (predecessor.right !== null) predecessor = predecessor.right;
    return predecessor;
  }
  toString(): string {
    return `${this.val}`;
  }
}
export abstract class BinaryTree<T> {
  protected root: BinaryTreeNode<T> | null = null;
  protected _size = 0;
  get size() {
    return this._size;
  }
  get empty() {
    return this.size === 0;
  }
  constructor(protected compare: Comparator<T>) {}
  protected abstract createNode(
    val: T,
    parent: BinaryTreeNode<T> | null,
    left: BinaryTreeNode<T> | null,
    right: BinaryTreeNode<T> | null
  ): BinaryTreeNode<T>;
  clear() {
    this.root = null;
    this._size = 0;
  }
  /**
   * 前序遍历
   * 先读取val值，再遍历左节点，再遍历右节点
   */
  preorder(): T[] {
    return this._preorder(this.root, []);
  }
  protected _preorder(node: BinaryTreeNode<T> | null, queue: T[]): T[] {
    if (node === null) return queue;
    queue.push(node.val);
    this._preorder(node.left, queue);
    this._preorder(node.right, queue);
    return queue;
  }
  /**
   * 中序遍历
   * 先遍历左节点，再读取val值，再遍历右节点
   */
  inorder(): T[] {
    return this._inorder(this.root, []);
  }
  protected _inorder(node: BinaryTreeNode<T> | null, queue: T[]): T[] {
    if (node === null) return queue;
    this._inorder(node.left, queue);
    queue.push(node.val);
    this._inorder(node.right, queue);
    return queue;
  }
  /**
   * 后序遍历
   * 先遍历左节点，再遍历右节点，再读取val值
   */
  postorder(): T[] {
    return this._postorder(this.root, []);
  }
  protected _postorder(node: BinaryTreeNode<T> | null, queue: T[]): T[] {
    if (node === null) return queue;
    this._postorder(node.left, queue);
    this._postorder(node.right, queue);
    queue.push(node.val);
    return queue;
  }
  /**
   * 层序遍历
   * 按行遍历树
   */
  levelOrder(): T[] {
    const list: T[] = [];
    if (this.root === null) return list;
    const queue: BinaryTreeNode<T>[] = [this.root];
    while (queue.length !== 0) {
      const node = queue.shift()!;
      list.push(node.val);
      node.left && queue.push(node.left);
      node.right && queue.push(node.right);
    }
    return list;
  }
  //├│─└┌
  print(): string {
    return this.root === null ? '' : this._print(this.root);
  }
  private _print(node: BinaryTreeNode<T>, prefix = ''): string {
    const left = node.left;
    const right = node.right;
    const nodeStr = node.toString();
    const halfLength = (nodeStr.length + (prefix === '' ? 0 : 3)) >> 1;
    const blankStr = repeat(' ', halfLength);
    const lineStr = repeat('─', halfLength);
    prefix += blankStr;
    let str = nodeStr + `\n`;
    if (right !== null) {
      str +=
        prefix +
        (left === null ? '└' : '├') +
        lineStr +
        ' R ' +
        this._print(right, `${prefix}${left === null ? ' ' : '│'}${blankStr}`);
    }
    if (left !== null) {
      str += `${prefix}└${lineStr}` + ' L ' + this._print(left, `${prefix}${blankStr} `);
    }
    return str;
  }
}

性质​

真二叉树​

满二叉树​

完全二叉树​

前驱节点​

后驱节点​

性质​

核心代码​

性质

真二叉树

满二叉树

完全二叉树

前驱节点

后驱节点

性质

核心代码