6-树

认识

树（Tree）是一种常用的数据结构，它由节点（node）和连接节点的边（edge）组成，具有层次性和递归结构。树的特点是每个节点有一个父节点，除了根节点没有父节点，每个节点可以有多个子节点。

树是一种分层的数据模型。前端常见的树包括：DOM、树、级联选择、树形控件……。JavaScript中没有树，但是可以通过Object和Array构建树。树的常用操作：深度/广度优先遍历、先中后序遍历。

TS实现

 /**
 * 前序遍历：root -> left -> right
 * 中序遍历：left -> root -> right
 * 后序遍历：left -> right -> root
 * 问1：为什么二叉树很重要，而不是三叉树、四叉树？
 * 答：
 * （1）数组、链表各有缺点
 * （2）特定的二叉树（BBST，平衡二叉树）可以结合数组 & 链表的优点，让整体查找效果最优（可用二分法）
 * （3）各种高级二叉树（红黑数、B树），继续优化，满足不同场景
 * 问2：堆特点？和二叉树的关系？
 * 答：
 * （1）逻辑结构是一棵二叉树
 * （2）物理结构是一个数组
 * （3）数组：连续内存 + 节省空间
 * （4）查询比 BST 慢
 * （5）增删比 BST 快，维持平衡更快
 * （6）整体时间复杂度都在 O(logn) 级别，与树一致
 * @description 二叉搜索树
 * @author hovinghuang
 */

interface ITreeNode {
    value: number
    left: ITreeNode | null
    right: ITreeNode | null
}

const treeArr: number[] = []

/**
 * 前序遍历
 * @param node 
 * @returns 
 */
function preOrderTraverse(node: ITreeNode | null): void {
    if (node == null) return
    console.info(node.value)
    treeArr.push(node.value)
    preOrderTraverse(node.left)
    preOrderTraverse(node.right)
}

/**
 * 中序遍历
 * @param node 
 * @returns 
 */
function inOrderTraverse(node: ITreeNode | null): void {
    if (node == null) return
    inOrderTraverse(node.left)
    console.info(node.value)
    treeArr.push(node.value)
    inOrderTraverse(node.right)
}

/**
 * 后序遍历
 * @param node 
 * @returns 
 */
function postOrderTraverse(node: ITreeNode | null): void {
    if (node == null) return
    postOrderTraverse(node.left)
    postOrderTraverse(node.right)
    console.info(node.value)
    treeArr.push(node.value)
}

function getKthValue(node: ITreeNode, k: number): number | null {
    inOrderTraverse(bst)
    return treeArr[k - 1] || null
}

const bst: ITreeNode = {
    value: 5,
    left: {
        value: 3,
        left: {
            value: 2,
            left: null,
            right: null
        },
        right: {
            value: 4,
            left: null,
            right: null,
        }
    },
    right: {
        value: 7,
        left: {
            value: 6,
            left: null,
            right: null
        },
        right: {
            value: 8,
            left: null,
            right: null
        }
    }
}

// 功能测试
// preOrderTraverse(bst)
// inOrderTraverse(bst)
// postOrderTraverse(bst)
// console.info('第3小值', getKthValue(bst, 3))

使用场景

• 场景一：DOM树
• 场景二：级联选择器

LeetCode题目

● 104. 二叉树的最大深度
● 111. 二叉树的最小深度
● 102. 二叉树的层序遍历
● 94. 二叉树的中序遍历
● 112. 路径总和

树的基本概念

• 节点（Node）：树中的基本元素，包含值或数据。每个节点由数据部分和指向子节点的指针（或者引用）组成。
• 根节点（Root）：树的顶端节点，没有父节点。
• 父节点（Parent）：某个节点的直接上级节点。
• 子节点（Child）：某个节点的直接下级节点。
• 叶子节点（Leaf）：没有子节点的节点。
• 子树（Subtree）：树的某个节点及其所有后代节点。
• 深度（Depth）：从根节点到该节点的路径长度。
• 高度（Height）：从该节点到最远叶子节点的路径长度。
• 度（Degree）：节点的子节点个数。

分类

根据不同的结构和用途，树可以有许多不同的类型，常见的包括：

• 二叉树（Binary Tree）：每个节点最多有两个子节点，通常称为左子节点和右子节点。
  • 满二叉树（Full Binary Tree）：每个节点要么是叶子节点，要么有两个子节点。
  • 完全二叉树（Complete Binary Tree）：除了最后一层，其他层的节点都达到最大，且最后一层的节点从左到右依次排列。
• 二叉搜索树（Binary Search Tree，BST）：对于每个节点，左子树的值小于节点的值，右子树的值大于节点的值。
• 平衡树（Balanced Tree）：为了保证高效的查询、插入和删除操作，树的高度尽量保持平衡。
  • AVL树：一种高度平衡的二叉搜索树，任何一个节点的两个子树的高度差的绝对值不超过1。
  • 红黑树：一种自平衡的二叉搜索树，每个节点都有额外的颜色属性（红色或黑色），通过颜色规则保持平衡。
• B树和B+树：用于数据库和文件系统，支持大规模数据的高效插入、删除、查找等操作。

树的常见操作

3.1 插入节点

• 在树中插入一个节点通常依赖于树的类型。例如，在二叉搜索树中，新的节点会插入到合适的位置，遵循左小右大的规则。

3.2 删除节点

• 删除树中的节点时需要考虑该节点的子节点。如果节点是叶子节点，直接删除；如果有一个子节点，删除节点并将子节点提升；如果有两个子节点，通常选择右子树中的最小节点或左子树中的最大节点来替代删除节点。

3.3 查找节点

• 查找操作在二叉搜索树中非常高效，因为它利用树的排序特性，可以在O(log n)的时间复杂度内完成查找。

3.4 遍历树

树的遍历是树结构的基本操作，常见的遍历方式有：

• 前序遍历（Preorder Traversal）：先访问根节点，然后访问左子树，再访问右子树。

textCopy Code根 → 左 → 右

• 中序遍历（Inorder Traversal）：先访问左子树，然后访问根节点，再访问右子树。

textCopy Code左 → 根 → 右

• 后序遍历（Postorder Traversal）：先访问左子树，然后访问右子树，最后访问根节点。

textCopy Code左 → 右 → 根

• 层次遍历（Level Order Traversal）：按层级顺序访问树的节点，通常使用队列实现。

实现

在实际编程中，树通常通过类（class）或结构体（struct）来实现。以下是一个简单的二叉树实现示例：

4.1 二叉树节点的定义

class TreeNode {
  constructor(value) {
    this.value = value;
    this.left = null;
    this.right = null;
  }
}

4.2 二叉搜索树的插入操作

class BinarySearchTree {
  constructor() {
    this.root = null;
  }

  insert(value) {
    const newNode = new TreeNode(value);
    if (this.root === null) {
      this.root = newNode;
    } else {
      this._insertNode(this.root, newNode);
    }
  }

  _insertNode(node, newNode) {
    if (newNode.value < node.value) {
      if (node.left === null) {
        node.left = newNode;
      } else {
        this._insertNode(node.left, newNode);
      }
    } else {
      if (node.right === null) {
        node.right = newNode;
      } else {
        this._insertNode(node.right, newNode);
      }
    }
  }
}

4.3 二叉树的前序遍历

 class BinaryTree {
    constructor() {
        this.root = null;
    }

    preorderTraversal(node) {
        if (node !== null) {
            console.log(node.value); // 访问节点
            this.preorderTraversal(node.left); // 访问左子树
            this.preorderTraversal(node.right); // 访问右子树
        }
    }
}

应用场景

• 数据库索引：B树和B+树广泛用于数据库索引中，支持高效的数据查找、插入、删除操作。
• 文件系统：目录结构通常用树来表示，文件夹是父节点，文件是子节点。
• 编译器：语法树用于表示程序的语法结构。
• 搜索引擎：倒排索引结构常使用树来表示。
• 人工智能：决策树用于机器学习中的分类任务。