跳至主要內容

树结构

Kpsmart2025年3月7日大约 15 分钟

树结构

树是一种非线性数据结构，由节点和边组成，没有循环。本文将介绍如何使用JavaScript实现二叉树、二叉搜索树、AVL树等树结构，以及树的遍历、搜索和平衡操作。

树的基本概念

树的术语

  • 节点(Node): 树中的基本单位，包含数据和指向子节点的引用
  • 根节点(Root): 树的顶部节点，没有父节点
  • 父节点(Parent): 直接连接到子节点的节点
  • 子节点(Child): 直接连接到父节点的节点
  • 叶节点(Leaf): 没有子节点的节点
  • 边(Edge): 连接两个节点的线
  • 路径(Path): 从一个节点到另一个节点的节点序列
  • 高度(Height): 从节点到其最远叶节点的最长路径上的边数
  • 深度(Depth): 从根节点到指定节点的边数
  • 层级(Level): 节点的深度加1
  • 度(Degree): 节点的子节点数量

树的类型

  1. 二叉树(Binary Tree): 每个节点最多有两个子节点
  2. 二叉搜索树(Binary Search Tree): 左子节点的值小于父节点，右子节点的值大于父节点
  3. 平衡二叉树(Balanced Binary Tree): 左右子树高度差不超过1
  4. AVL树: 自平衡的二叉搜索树
  5. 红黑树(Red-Black Tree): 自平衡的二叉搜索树，具有特定的着色规则
  6. B树/B+树: 多路搜索树，常用于数据库和文件系统
  7. 堆(Heap): 完全二叉树，满足堆属性（最大堆或最小堆）

二叉树的实现

二叉树节点

首先，我们定义二叉树的节点结构：

class Node {
  constructor(data) {
    this.data = data;
    this.left = null;
    this.right = null;
  }
}

二叉树类

接下来，我们实现一个基本的二叉树类：

class BinaryTree {
  constructor() {
    this.root = null;
  }
  
  // 插入节点（层序插入）
  insert(data) {
    const newNode = new Node(data);
    
    if (this.root === null) {
      this.root = newNode;
      return;
    }
    
    // 使用队列进行层序遍历
    const queue = [];
    queue.push(this.root);
    
    while (queue.length > 0) {
      const node = queue.shift();
      
      // 如果左子节点为空，插入新节点
      if (node.left === null) {
        node.left = newNode;
        return;
      } else {
        queue.push(node.left);
      }
      
      // 如果右子节点为空，插入新节点
      if (node.right === null) {
        node.right = newNode;
        return;
      } else {
        queue.push(node.right);
      }
    }
  }
  
  // 前序遍历（根-左-右）
  preOrderTraversal(node = this.root, result = []) {
    if (node !== null) {
      // 访问根节点
      result.push(node.data);
      // 遍历左子树
      this.preOrderTraversal(node.left, result);
      // 遍历右子树
      this.preOrderTraversal(node.right, result);
    }
    return result;
  }
  
  // 中序遍历（左-根-右）
  inOrderTraversal(node = this.root, result = []) {
    if (node !== null) {
      // 遍历左子树
      this.inOrderTraversal(node.left, result);
      // 访问根节点
      result.push(node.data);
      // 遍历右子树
      this.inOrderTraversal(node.right, result);
    }
    return result;
  }
  
  // 后序遍历（左-右-根）
  postOrderTraversal(node = this.root, result = []) {
    if (node !== null) {
      // 遍历左子树
      this.postOrderTraversal(node.left, result);
      // 遍历右子树
      this.postOrderTraversal(node.right, result);
      // 访问根节点
      result.push(node.data);
    }
    return result;
  }
  
  // 层序遍历（广度优先）
  levelOrderTraversal() {
    if (this.root === null) {
      return [];
    }
    
    const result = [];
    const queue = [];
    queue.push(this.root);
    
    while (queue.length > 0) {
      const node = queue.shift();
      result.push(node.data);
      
      if (node.left !== null) {
        queue.push(node.left);
      }
      
      if (node.right !== null) {
        queue.push(node.right);
      }
    }
    
    return result;
  }
  
  // 计算树的高度
  height(node = this.root) {
    if (node === null) {
      return -1;
    }
    
    const leftHeight = this.height(node.left);
    const rightHeight = this.height(node.right);
    
    return Math.max(leftHeight, rightHeight) + 1;
  }
  
  // 查找节点
  search(data, node = this.root) {
    if (node === null) {
      return null;
    }
    
    if (node.data === data) {
      return node;
    }
    
    // 在左子树中查找
    const leftResult = this.search(data, node.left);
    if (leftResult !== null) {
      return leftResult;
    }
    
    // 在右子树中查找
    return this.search(data, node.right);
  }
}

二叉树使用示例

// 创建二叉树
const tree = new BinaryTree();
tree.insert(1);
tree.insert(2);
tree.insert(3);
tree.insert(4);
tree.insert(5);
tree.insert(6);
tree.insert(7);

// 遍历二叉树
console.log("前序遍历:", tree.preOrderTraversal());   // [1, 2, 4, 5, 3, 6, 7]
console.log("中序遍历:", tree.inOrderTraversal());    // [4, 2, 5, 1, 6, 3, 7]
console.log("后序遍历:", tree.postOrderTraversal());  // [4, 5, 2, 6, 7, 3, 1]
console.log("层序遍历:", tree.levelOrderTraversal()); // [1, 2, 3, 4, 5, 6, 7]

// 计算树的高度
console.log("树的高度:", tree.height()); // 2

// 查找节点
const node = tree.search(5);
console.log("查找节点5:", node ? node.data : "未找到"); // 5

二叉搜索树的实现

二叉搜索树(BST)是一种特殊的二叉树，其中每个节点的左子节点的值小于节点的值，右子节点的值大于节点的值。

二叉搜索树类

class BinarySearchTree {
  constructor() {
    this.root = null;
  }
  
  // 插入节点
  insert(data) {
    const newNode = new Node(data);
    
    if (this.root === null) {
      this.root = newNode;
      return;
    }
    
    this._insertNode(this.root, newNode);
  }
  
  // 辅助方法：递归插入节点
  _insertNode(node, newNode) {
    // 如果新节点的值小于当前节点的值，插入到左子树
    if (newNode.data < node.data) {
      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);
      }
    }
  }
  
  // 查找最小值
  min(node = this.root) {
    if (node === null) {
      return null;
    }
    
    while (node.left !== null) {
      node = node.left;
    }
    
    return node.data;
  }
  
  // 查找最大值
  max(node = this.root) {
    if (node === null) {
      return null;
    }
    
    while (node.right !== null) {
      node = node.right;
    }
    
    return node.data;
  }
  
  // 查找节点
  search(data, node = this.root) {
    if (node === null) {
      return null;
    }
    
    if (data < node.data) {
      return this.search(data, node.left);
    } else if (data > node.data) {
      return this.search(data, node.right);
    } else {
      return node;
    }
  }
  
  // 删除节点
  remove(data) {
    this.root = this._removeNode(this.root, data);
  }
  
  // 辅助方法：递归删除节点
  _removeNode(node, data) {
    if (node === null) {
      return null;
    }
    
    // 查找要删除的节点
    if (data < node.data) {
      node.left = this._removeNode(node.left, data);
      return node;
    } else if (data > node.data) {
      node.right = this._removeNode(node.right, data);
      return node;
    } else {
      // 情况1：叶节点（没有子节点）
      if (node.left === null && node.right === null) {
        return null;
      }
      
      // 情况2：只有一个子节点
      if (node.left === null) {
        return node.right;
      }
      
      if (node.right === null) {
        return node.left;
      }
      
      // 情况3：有两个子节点
      // 找到右子树中的最小节点
      const minRight = this._findMinNode(node.right);
      // 用右子树中的最小值替换当前节点的值
      node.data = minRight.data;
      // 删除右子树中的最小节点
      node.right = this._removeNode(node.right, minRight.data);
      return node;
    }
  }
  
  // 辅助方法：查找最小节点
  _findMinNode(node) {
    while (node.left !== null) {
      node = node.left;
    }
    return node;
  }
  
  // 中序遍历（对于BST，中序遍历会按升序输出节点）
  inOrderTraversal(node = this.root, result = []) {
    if (node !== null) {
      this.inOrderTraversal(node.left, result);
      result.push(node.data);
      this.inOrderTraversal(node.right, result);
    }
    return result;
  }
  
  // 前序遍历和后序遍历与二叉树相同
  preOrderTraversal(node = this.root, result = []) {
    if (node !== null) {
      result.push(node.data);
      this.preOrderTraversal(node.left, result);
      this.preOrderTraversal(node.right, result);
    }
    return result;
  }
  
  postOrderTraversal(node = this.root, result = []) {
    if (node !== null) {
      this.postOrderTraversal(node.left, result);
      this.postOrderTraversal(node.right, result);
      result.push(node.data);
    }
    return result;
  }
}

二叉搜索树使用示例

// 创建二叉搜索树
const bst = new BinarySearchTree();
bst.insert(15);
bst.insert(10);
bst.insert(20);
bst.insert(8);
bst.insert(12);
bst.insert(17);
bst.insert(25);

// 遍历二叉搜索树
console.log("中序遍历:", bst.inOrderTraversal());    // [8, 10, 12, 15, 17, 20, 25]
console.log("前序遍历:", bst.preOrderTraversal());   // [15, 10, 8, 12, 20, 17, 25]
console.log("后序遍历:", bst.postOrderTraversal());  // [8, 12, 10, 17, 25, 20, 15]

// 查找最小值和最大值
console.log("最小值:", bst.min()); // 8
console.log("最大值:", bst.max()); // 25

// 查找节点
const node = bst.search(12);
console.log("查找节点12:", node ? node.data : "未找到"); // 12

// 删除节点
bst.remove(10);
console.log("删除节点10后的中序遍历:", bst.inOrderTraversal()); // [8, 12, 15, 17, 20, 25]

AVL树的实现

AVL树是一种自平衡的二叉搜索树，其中任何节点的左右子树高度差不超过1。

AVL树节点

class AVLNode {
  constructor(data) {
    this.data = data;
    this.left = null;
    this.right = null;
    this.height = 1; // 新节点的高度为1
  }
}

AVL树类

class AVLTree {
  constructor() {
    this.root = null;
  }
  
  // 获取节点高度
  height(node) {
    if (node === null) {
      return 0;
    }
    return node.height;
  }
  
  // 获取平衡因子
  getBalanceFactor(node) {
    if (node === null) {
      return 0;
    }
    return this.height(node.left) - this.height(node.right);
  }
  
  // 更新节点高度
  updateHeight(node) {
    if (node === null) {
      return;
    }
    node.height = Math.max(this.height(node.left), this.height(node.right)) + 1;
  }
  
  // 右旋转
  rightRotate(y) {
    const x = y.left;
    const T2 = x.right;
    
    // 执行旋转
    x.right = y;
    y.left = T2;
    
    // 更新高度
    this.updateHeight(y);
    this.updateHeight(x);
    
    // 返回新的根节点
    return x;
  }
  
  // 左旋转
  leftRotate(x) {
    const y = x.right;
    const T2 = y.left;
    
    // 执行旋转
    y.left = x;
    x.right = T2;
    
    // 更新高度
    this.updateHeight(x);
    this.updateHeight(y);
    
    // 返回新的根节点
    return y;
  }
  
  // 插入节点
  insert(data) {
    this.root = this._insertNode(this.root, data);
  }
  
  // 辅助方法：递归插入节点
  _insertNode(node, data) {
    // 执行标准BST插入
    if (node === null) {
      return new AVLNode(data);
    }
    
    if (data < node.data) {
      node.left = this._insertNode(node.left, data);
    } else if (data > node.data) {
      node.right = this._insertNode(node.right, data);
    } else {
      // 重复值不插入
      return node;
    }
    
    // 更新当前节点的高度
    this.updateHeight(node);
    
    // 获取平衡因子
    const balance = this.getBalanceFactor(node);
    
    // 如果节点不平衡，则有四种情况
    
    // 左左情况 - 右旋转
    if (balance > 1 && data < node.left.data) {
      return this.rightRotate(node);
    }
    
    // 右右情况 - 左旋转
    if (balance < -1 && data > node.right.data) {
      return this.leftRotate(node);
    }
    
    // 左右情况 - 先左旋转再右旋转
    if (balance > 1 && data > node.left.data) {
      node.left = this.leftRotate(node.left);
      return this.rightRotate(node);
    }
    
    // 右左情况 - 先右旋转再左旋转
    if (balance < -1 && data < node.right.data) {
      node.right = this.rightRotate(node.right);
      return this.leftRotate(node);
    }
    
    // 返回未更改的节点指针
    return node;
  }
  
  // 查找最小值节点
  _findMinNode(node) {
    let current = node;
    while (current.left !== null) {
      current = current.left;
    }
    return current;
  }
  
  // 删除节点
  remove(data) {
    this.root = this._removeNode(this.root, data);
  }
  
  // 辅助方法：递归删除节点
  _removeNode(node, data) {
    // 标准BST删除
    if (node === null) {
      return null;
    }
    
    if (data < node.data) {
      node.left = this._removeNode(node.left, data);
    } else if (data > node.data) {
      node.right = this._removeNode(node.right, data);
    } else {
      // 找到要删除的节点
      
      // 情况1：叶节点
      if (node.left === null && node.right === null) {
        return null;
      }
      
      // 情况2：只有一个子节点
      if (node.left === null) {
        return node.right;
      } else if (node.right === null) {
        return node.left;
      }
      
      // 情况3：有两个子节点
      // 找到右子树中的最小节点
      const temp = this._findMinNode(node.right);
      node.data = temp.data;
      
      // 删除右子树中的最小节点
      node.right = this._removeNode(node.right, temp.data);
    }
    
    // 如果树只有一个节点，则返回
    if (node === null) {
      return null;
    }
    
    // 更新高度
    this.updateHeight(node);
    
    // 获取平衡因子
    const balance = this.getBalanceFactor(node);
    
    // 如果节点不平衡，则有四种情况
    
    // 左左情况 - 右旋转
    if (balance > 1 && this.getBalanceFactor(node.left) >= 0) {
      return this.rightRotate(node);
    }
    
    // 左右情况 - 先左旋转再右旋转
    if (balance > 1 && this.getBalanceFactor(node.left) < 0) {
      node.left = this.leftRotate(node.left);
      return this.rightRotate(node);
    }
    
    // 右右情况 - 左旋转
    if (balance < -1 && this.getBalanceFactor(node.right) <= 0) {
      return this.leftRotate(node);
    }
    
    // 右左情况 - 先右旋转再左旋转
    if (balance < -1 && this.getBalanceFactor(node.right) > 0) {
      node.right = this.rightRotate(node.right);
      return this.leftRotate(node);
    }
    
    return node;
  }
  
  // 中序遍历
  inOrderTraversal(node = this.root, result = []) {
    if (node !== null) {
      this.inOrderTraversal(node.left, result);
      result.push(node.data);
      this.inOrderTraversal(node.right, result);
    }
    return result;
  }
  
  // 查找节点
  search(data) {
    return this._searchNode(this.root, data);
  }
  
  // 辅助方法：递归查找节点
  _searchNode(node, data) {
    if (node === null) {
      return null;
    }
    
    if (data < node.data) {
      return this._searchNode(node.left, data);
    } else if (data > node.data) {
      return this._searchNode(node.right, data);
    } else {
      return node;
    }
  }
}

AVL树使用示例

// 创建AVL树
const avlTree = new AVLTree();
avlTree.insert(10);
avlTree.insert(20);
avlTree.insert(30); // 这会触发旋转以保持平衡
avlTree.insert(40);
avlTree.insert(50); // 这会触发旋转以保持平衡
avlTree.insert(25);

// 中序遍历（应该是有序的）
console.log("中序遍历:", avlTree.inOrderTraversal()); // [10, 20, 25, 30, 40, 50]

// 删除节点
avlTree.remove(20);
console.log("删除节点20后的中序遍历:", avlTree.inOrderTraversal()); // [10, 25, 30, 40, 50]

// 查找节点
const node = avlTree.search(30);
console.log("查找节点30:", node ? node.data : "未找到"); // 30

红黑树的实现

红黑树是一种自平衡的二叉搜索树，它通过节点着色和特定规则来保持平衡。红黑树的每个节点都有一个颜色属性，可以是红色或黑色。

红黑树的性质

  1. 每个节点要么是红色，要么是黑色
  2. 根节点是黑色
  3. 所有叶节点（NIL节点）是黑色
  4. 如果一个节点是红色，则它的两个子节点都是黑色
  5. 对于每个节点，从该节点到其所有后代叶节点的简单路径上，均包含相同数量的黑色节点

红黑树节点

class RedBlackNode {
  constructor(data) {
    this.data = data;
    this.left = null;
    this.right = null;
    this.parent = null;
    this.color = 'RED'; // 新插入的节点默认为红色
  }
}

红黑树类

class RedBlackTree {
  constructor() {
    this.NIL = new RedBlackNode(null); // 哨兵节点
    this.NIL.color = 'BLACK';
    this.NIL.left = null;
    this.NIL.right = null;
    this.root = this.NIL;
  }
  
  // 左旋转
  leftRotate(x) {
    const y = x.right;
    x.right = y.left;
    
    if (y.left !== this.NIL) {
      y.left.parent = x;
    }
    
    y.parent = x.parent;
    
    if (x.parent === null) {
      this.root = y;
    } else if (x === x.parent.left) {
      x.parent.left = y;
    } else {
      x.parent.right = y;
    }
    
    y.left = x;
    x.parent = y;
  }
  
  // 右旋转
  rightRotate(y) {
    const x = y.left;
    y.left = x.right;
    
    if (x.right !== this.NIL) {
      x.right.parent = y;
    }
    
    x.parent = y.parent;
    
    if (y.parent === null) {
      this.root = x;
    } else if (y === y.parent.left) {
      y.parent.left = x;
    } else {
      y.parent.right = x;
    }
    
    x.right = y;
    y.parent = x;
  }
  
  // 插入节点
  insert(data) {
    const newNode = new RedBlackNode(data);
    newNode.left = this.NIL;
    newNode.right = this.NIL;
    
    let y = null;
    let x = this.root;
    
    // 找到插入位置
    while (x !== this.NIL) {
      y = x;
      if (newNode.data < x.data) {
        x = x.left;
      } else {
        x = x.right;
      }
    }
    
    newNode.parent = y;
    
    if (y === null) {
      this.root = newNode; // 树为空
    } else if (newNode.data < y.data) {
      y.left = newNode;
    } else {
      y.right = newNode;
    }
    
    // 如果新节点是根节点，则将其设为黑色并返回
    if (newNode.parent === null) {
      newNode.color = 'BLACK';
      return;
    }
    
    // 如果祖父节点为空，则返回
    if (newNode.parent.parent === null) {
      return;
    }
    
    // 修复红黑树性质
    this._fixInsert(newNode);
  }
  
  // 修复插入后的红黑树性质
  _fixInsert(k) {
    let u;
    
    while (k.parent && k.parent.color === 'RED') {
      if (k.parent === k.parent.parent.right) {
        u = k.parent.parent.left; // 叔节点
        
        if (u.color === 'RED') {
          // 情况1：叔节点是红色
          u.color = 'BLACK';
          k.parent.color = 'BLACK';
          k.parent.parent.color = 'RED';
          k = k.parent.parent;
        } else {
          if (k === k.parent.left) {
            // 情况2：叔节点是黑色，k是左子节点
            k = k.parent;
            this.rightRotate(k);
          }
          
          // 情况3：叔节点是黑色，k是右子节点
          k.parent.color = 'BLACK';
          k.parent.parent.color = 'RED';
          this.leftRotate(k.parent.parent);
        }
      } else {
        u = k.parent.parent.right; // 叔节点
        
        if (u.color === 'RED') {
          // 情况1：叔节点是红色
          u.color = 'BLACK';
          k.parent.color = 'BLACK';
          k.parent.parent.color = 'RED';
          k = k.parent.parent;
        } else {
          if (k === k.parent.right) {
            // 情况2：叔节点是黑色，k是右子节点
            k = k.parent;
            this.leftRotate(k);
          }
          
          // 情况3：叔节点是黑色，k是左子节点
          k.parent.color = 'BLACK';
          k.parent.parent.color = 'RED';
          this.rightRotate(k.parent.parent);
        }
      }
      
      if (k === this.root) {
        break;
      }
    }
    
    this.root.color = 'BLACK';
  }
  
  // 中序遍历
  inOrderTraversal(node = this.root, result = []) {
    if (node !== this.NIL) {
      this.inOrderTraversal(node.left, result);
      result.push(`${node.data}(${node.color})`);
      this.inOrderTraversal(node.right, result);
    }
    return result;
  }
  
  // 查找节点
  search(data) {
    return this._searchNode(this.root, data);
  }
  
  // 辅助方法：递归查找节点
  _searchNode(node, data) {
    if (node === this.NIL) {
      return null;
    }
    
    if (data < node.data) {
      return this._searchNode(node.left, data);
    } else if (data > node.data) {
      return this._searchNode(node.right, data);
    } else {
      return node;
    }
  }
}

红黑树使用示例

// 创建红黑树
const rbTree = new RedBlackTree();
rbTree.insert(10);
rbTree.insert(20);
rbTree.insert(30);
rbTree.insert(15);
rbTree.insert(25);
rbTree.insert(5);

// 中序遍历（应该是有序的，并显示每个节点的颜色）
console.log("中序遍历:", rbTree.inOrderTraversal()); 
// 输出类似: ["5(BLACK)", "10(BLACK)", "15(RED)", "20(BLACK)", "25(RED)", "30(BLACK)"]

// 查找节点
const node = rbTree.search(15);
console.log("查找节点15:", node ? `${node.data}(${node.color})` : "未找到"); // "15(RED)"

树的应用实例

1. 文件系统目录结构

树结构可以用来表示文件系统的目录结构：

class FileSystemNode {
  constructor(name, isDirectory = false) {
    this.name = name;
    this.isDirectory = isDirectory;
    this.children = isDirectory ? [] : null;
    this.content = isDirectory ? null : '';
  }
  
  // 添加子节点（仅目录可以添加）
  addChild(child) {
    if (!this.isDirectory) {
      throw new Error('不能向文件添加子节点');
    }
    this.children.push(child);
  }
  
  // 查找子节点
  findChild(name) {
    if (!this.isDirectory) {
      return null;
    }
    
    return this.children.find(child => child.name === name);
  }
  
  // 显示目录结构
  display(indent = 0) {
    const indentStr = ' '.repeat(indent);
    const icon = this.isDirectory ? '📁' : '📄';
    console.log(`${indentStr}${icon} ${this.name}`);
    
    if (this.isDirectory && this.children.length > 0) {
      this.children.forEach(child => {
        child.display(indent + 2);
      });
    }
  }
}

// 创建文件系统
const root = new FileSystemNode('root', true);

// 添加目录和文件
const docs = new FileSystemNode('documents', true);
const pics = new FileSystemNode('pictures', true);
const file1 = new FileSystemNode('file1.txt');
const file2 = new FileSystemNode('file2.txt');
const pic1 = new FileSystemNode('pic1.jpg');

root.addChild(docs);
root.addChild(pics);
docs.addChild(file1);
docs.addChild(file2);
pics.addChild(pic1);

// 显示目录结构
root.display();
// 输出:
// 📁 root
//   📁 documents
//     📄 file1.txt
//     📄 file2.txt
//   📁 pictures
//     📄 pic1.jpg

2. 表达式树

表达式树是一种用于表示算术表达式的二叉树：

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

// 构建表达式树
function buildExpressionTree(expression) {
  const tokens = expression.split(' ');
  const stack = [];
  
  for (const token of tokens) {
    if (['+', '-', '*', '/'].includes(token)) {
      // 运算符：从栈中弹出两个操作数
      const right = stack.pop();
      const left = stack.pop();
      // 创建新节点并压入栈中
      stack.push(new ExpressionNode(token, left, right));
    } else {
      // 操作数：创建叶节点并压入栈中
      stack.push(new ExpressionNode(token));
    }
  }
  
  return stack.pop();
}

// 计算表达式树的值
function evaluateExpressionTree(node) {
  if (!node.left && !node.right) {
    return parseFloat(node.value);
  }
  
  const leftValue = evaluateExpressionTree(node.left);
  const rightValue = evaluateExpressionTree(node.right);
  
  switch (node.value) {
    case '+': return leftValue + rightValue;
    case '-': return leftValue - rightValue;
    case '*': return leftValue * rightValue;
    case '/': return leftValue / rightValue;
    default: return 0;
  }
}

// 中序遍历（添加括号以保持优先级）
function inOrderExpression(node) {
  if (!node.left && !node.right) {
    return node.value;
  }
  
  const leftExpr = inOrderExpression(node.left);
  const rightExpr = inOrderExpression(node.right);
  
  return `(${leftExpr} ${node.value} ${rightExpr})`;
}

// 示例：构建并计算表达式树
// 后缀表达式（逆波兰表示法）: "3 4 + 2 * 7 /"
const expressionTree = buildExpressionTree("3 4 + 2 * 7 /");
console.log("中序表达式:", inOrderExpression(expressionTree)); // "((3 + 4) * 2) / 7"
console.log("计算结果:", evaluateExpressionTree(expressionTree)); // 2

3. 决策树

决策树是一种用于分类和预测的树结构：

class DecisionNode {
  constructor(attribute, value = null) {
    this.attribute = attribute; // 决策属性
    this.value = value; // 叶节点的分类结果
    this.branches = {}; // 分支（键为属性值，值为子节点）
  }
  
  // 添加分支
  addBranch(attributeValue, node) {
    this.branches[attributeValue] = node;
  }
  
  // 预测分类
  predict(sample) {
    // 如果是叶节点，返回分类结果
    if (this.value !== null) {
      return this.value;
    }
    
    // 获取样本中对应属性的值
    const attributeValue = sample[this.attribute];
    
    // 如果没有对应的分支，返回默认分类
    if (!this.branches[attributeValue]) {
      // 返回最常见的分支结果
      const branchValues = Object.values(this.branches);
      if (branchValues.length === 0) {
        return null;
      }
      
      // 简单起见，返回第一个分支的结果
      return branchValues[0].predict(sample);
    }
    
    // 递归预测
    return this.branches[attributeValue].predict(sample);
  }
  
  // 显示决策树
  display(indent = 0) {
    const indentStr = ' '.repeat(indent);
    
    if (this.value !== null) {
      console.log(`${indentStr}→ ${this.value}`);
      return;
    }
    
    console.log(`${indentStr}[${this.attribute}]`);
    
    for (const [attributeValue, node] of Object.entries(this.branches)) {
      console.log(`${indentStr} ${attributeValue}:`);
      node.display(indent + 2);
    }
  }
}

// 创建一个简单的决策树（天气-活动决策）
const root = new DecisionNode('weather');

// 添加分支
const playNode = new DecisionNode(null, 'play');
const stayHomeNode = new DecisionNode(null, 'stay home');
const shopNode = new DecisionNode(null, 'shopping');

// 天气分支
root.addBranch('sunny', playNode);
root.addBranch('rainy', stayHomeNode);
root.addBranch('cloudy', shopNode);

// 显示决策树
root.display();
// 输出:
// [weather]
//  sunny:
//   → play
//  rainy:
//   → stay home
//  cloudy:
//   → shopping

// 预测
const sample1 = { weather: 'sunny' };
const sample2 = { weather: 'rainy' };
console.log(`天气${sample1.weather}时的活动: ${root.predict(sample1)}`); // play
console.log(`天气${sample2.weather}时的活动: ${root.predict(sample2)}`); // stay home

树的性能分析

不同树结构的时间复杂度比较

操作二叉树(最坏)二叉搜索树(平均)二叉搜索树(最坏)AVL树红黑树
查找O(n)O(log n)O(n)O(log n)O(log n)
插入O(n)O(log n)O(n)O(log n)O(log n)
删除O(n)O(log n)O(n)O(log n)O(log n)
遍历O(n)O(n)O(n)O(n)O(n)

空间复杂度

所有树结构的空间复杂度都是O(n)，其中n是节点数量。

平衡树与非平衡树的比较

平衡树（如AVL树和红黑树）通过保持树的平衡来确保操作的时间复杂度为O(log n)，而非平衡的二叉搜索树在最坏情况下可能退化为链表，导致操作的时间复杂度为O(n)。

  • AVL树：严格平衡（任何节点的左右子树高度差不超过1），但平衡操作开销较大
  • 红黑树：近似平衡，平衡操作开销较小，在实际应用中更为常用

总结

树是一种非常重要的数据结构，广泛应用于各种场景：

  1. 二叉树：用于表示层次结构，如文件系统、组织结构等
  2. 二叉搜索树：用于快速查找、插入和删除有序数据
  3. AVL树和红黑树：用于需要保持平衡的场景，如数据库索引
  4. B树和B+树：用于磁盘存储和数据库系统
  5. 堆：用于优先队列和堆排序

在JavaScript中，虽然没有内置的树结构，但我们可以轻松地实现各种树结构来满足不同的需求。理解树的原理和实现方式对于解决复杂问题和优化算法至关重要。

参考资源