数据结构 算法 二叉树
2020年4月28日

二叉树

Aren

二叉树简介

二叉树（Binary Tree）是一种非线性数据结构，它由节点组成，每个节点最多有两个子节点，通常称为”左子节点”和”右子节点”。二叉树在计算机科学中有广泛的应用，包括表达式解析、数据压缩、路由算法等。

二叉树的基本概念

节点结构

在JavaScript中，我们可以用以下方式定义一个二叉树节点：

class TreeNode {
  constructor(val) {
    this.val = val;       // 节点值
    this.left = null;     // 左子节点
    this.right = null;    // 右子节点
  }
}

二叉树的基本术语

  • 根节点：二叉树最顶层的节点，没有父节点
  • 叶子节点：没有子节点的节点
  • 父节点：有子节点的节点
  • 子节点：某节点下一层的直接连接节点
  • 兄弟节点：共享同一个父节点的节点
  • 节点的深度：从根节点到该节点的边数
  • 节点的高度：从该节点到最远叶子节点的边数
  • 树的高度：根节点的高度

二叉树的类型

  1. 满二叉树：除了叶子节点外，每个节点都有两个子节点，所有叶子节点都在同一层
  2. 完全二叉树：除了最后一层外，其他层的节点数都达到最大值，且最后一层的节点都靠左排列
  3. 平衡二叉树：任意节点的左右子树高度差不超过1
  4. 二叉搜索树：左子树上所有节点的值都小于根节点的值，右子树上所有节点的值都大于根节点的值
  5. 堆：一种特殊的完全二叉树，分为最大堆和最小堆

二叉树的遍历

遍历是指按照某种顺序访问二叉树中的所有节点。常见的遍历方式有：

1. 深度优先遍历（DFS）

前序遍历（根-左-右）

function preorderTraversal(root) {
  const result = [];
  
  function traverse(node) {
    if (node === null) return;
    
    // 访问根节点
    result.push(node.val);
    // 遍历左子树
    traverse(node.left);
    // 遍历右子树
    traverse(node.right);
  }
  
  traverse(root);
  return result;
}
前序遍历可视化
1245367
前序遍历结果:

中序遍历（左-根-右）

function inorderTraversal(root) {
  const result = [];
  
  function traverse(node) {
    if (node === null) return;
    
    // 遍历左子树
    traverse(node.left);
    // 访问根节点
    result.push(node.val);
    // 遍历右子树
    traverse(node.right);
  }
  
  traverse(root);
  return result;
}
中序遍历可视化
1245367
中序遍历结果:

后序遍历（左-右-根）

function postorderTraversal(root) {
  const result = [];
  
  function traverse(node) {
    if (node === null) return;
    
    // 遍历左子树
    traverse(node.left);
    // 遍历右子树
    traverse(node.right);
    // 访问根节点
    result.push(node.val);
  }
  
  traverse(root);
  return result;
}
后序遍历可视化
1245367
后序遍历结果:

2. 广度优先遍历（BFS）/ 层序遍历

function levelOrderTraversal(root) {
  if (!root) return [];
  
  const result = [];
  const queue = [root];
  
  while (queue.length > 0) {
    const levelSize = queue.length;
    const currentLevel = [];
    
    for (let i = 0; i < levelSize; i++) {
      const node = queue.shift();
      currentLevel.push(node.val);
      
      if (node.left) queue.push(node.left);
      if (node.right) queue.push(node.right);
    }
    
    result.push(currentLevel);
  }
  
  return result;
}
层序遍历可视化
1245367
层序遍历结果:

二叉树的应用

1. 表达式树

表达式树是一种用于表示算术表达式的二叉树，其中叶子节点是操作数，非叶子节点是操作符。

function evaluateExpressionTree(root) {
  // 如果是叶子节点（操作数），直接返回值
  if (!root.left && !root.right) {
    return parseInt(root.val);
  }
  
  // 递归计算左右子树的值
  const leftValue = evaluateExpressionTree(root.left);
  const rightValue = evaluateExpressionTree(root.right);
  
  // 根据操作符计算结果
  switch (root.val) {
    case '+': return leftValue + rightValue;
    case '-': return leftValue - rightValue;
    case '*': return leftValue * rightValue;
    case '/': return leftValue / rightValue;
    default: return 0;
  }
}

// 计算结果：(3 + 4) * 5 = 35

2. 二叉搜索树（BST）

二叉搜索树是一种特殊的二叉树，它支持高效的查找、插入和删除操作。二叉搜索树的结构如下:

  1. 左子树所有节点的值 < 根节点的值
  2. 右子树所有节点的值 > 根节点的值
  3. 左右子树也必须是二叉搜索树
/**
 * 二叉搜索树(BST)结构说明：
 * 1. 左子树所有节点的值 < 根节点的值
 * 2. 右子树所有节点的值 > 根节点的值
 * 3. 左右子树也必须是二叉搜索树
 * 
 * 示例结构：
 *     10
 *    /  \
 *   5    15
 *  / \   / \
 * 2   7 12 20
 */
class BinarySearchTree {
  constructor() {
    this.root = null;
  }
  
  // 插入节点
  insert(val) {
    const newNode = new TreeNode(val);
    
    if (this.root === null) {
      this.root = newNode;
      return this;
    }
    
    function insertNode(node, newNode) {
      // 如果新值小于当前节点值，放在左边
      if (newNode.val < node.val) {
        if (node.left === null) {
          node.left = newNode;
        } else {
          insertNode(node.left, newNode);
        }
      } 
      // 如果新值大于当前节点值，放在右边
      else {
        if (node.right === null) {
          node.right = newNode;
        } else {
          insertNode(node.right, newNode);
        }
      }
    }
    
    insertNode(this.root, newNode);
    return this;
  }
  
  // 查找节点
  search(val) {
    if (!this.root) return false;
    
    let current = this.root;
    let found = false;
    
    while (current && !found) {
      if (val < current.val) {
        current = current.left;
      } else if (val > current.val) {
        current = current.right;
      } else {
        found = true;
      }
    }
    
    return found ? current : false;
  }
}

// 使用示例
const bst = new BinarySearchTree();
bst.insert(10);
bst.insert(5);
bst.insert(15);
bst.insert(2);
bst.insert(7);

/*
    10
   /  \
  5    15
 / \
2   7
*/

console.log(bst.search(7)); // TreeNode { val: 7, left: null, right: null }
console.log(bst.search(20)); // false

3. 堆（Heap）

堆是一种特殊的完全二叉树，分为最大堆和最小堆。在最大堆中，父节点的值总是大于或等于其子节点的值；在最小堆中，父节点的值总是小于或等于其子节点的值。

class MinHeap {
  constructor() {
    this.heap = [];
  }
  
  // 获取父节点索引
  getParentIndex(index) {
    return Math.floor((index - 1) / 2);
  }
  
  // 获取左子节点索引
  getLeftChildIndex(index) {
    return 2 * index + 1;
  }
  
  // 获取右子节点索引
  getRightChildIndex(index) {
    return 2 * index + 2;
  }
  
  // 交换两个节点
  swap(index1, index2) {
    [this.heap[index1], this.heap[index2]] = [this.heap[index2], this.heap[index1]];
  }
  
  // 向上调整
  heapifyUp(index) {
    const parentIndex = this.getParentIndex(index);
    
    if (index > 0 && this.heap[parentIndex] > this.heap[index]) {
      this.swap(parentIndex, index);
      this.heapifyUp(parentIndex);
    }
  }
  
  // 向下调整
  heapifyDown(index) {
    const leftChildIndex = this.getLeftChildIndex(index);
    const rightChildIndex = this.getRightChildIndex(index);
    let smallest = index;
    
    if (leftChildIndex < this.heap.length && this.heap[leftChildIndex] < this.heap[smallest]) {
      smallest = leftChildIndex;
    }
    
    if (rightChildIndex < this.heap.length && this.heap[rightChildIndex] < this.heap[smallest]) {
      smallest = rightChildIndex;
    }
    
    if (smallest !== index) {
      this.swap(index, smallest);
      this.heapifyDown(smallest);
    }
  }
  
  // 插入节点
  insert(val) {
    this.heap.push(val);
    this.heapifyUp(this.heap.length - 1);
  }
  
  // 提取最小值
  extractMin() {
    if (this.heap.length === 0) return null;
    
    const min = this.heap[0];
    const last = this.heap.pop();
    
    if (this.heap.length > 0) {
      this.heap[0] = last;
      this.heapifyDown(0);
    }
    
    return min;
  }
}

// 使用示例
const minHeap = new MinHeap();
minHeap.insert(5);
minHeap.insert(3);
minHeap.insert(8);
minHeap.insert(1);

console.log(minHeap.extractMin()); // 1
console.log(minHeap.extractMin()); // 3

总结

二叉树是一种重要的数据结构，它在计算机科学中有广泛的应用。通过本文，我们了解了二叉树的基本概念、类型、遍历方法以及常见应用。在实际编程中，掌握二叉树的相关知识对于解决复杂问题和优化算法效率非常有帮助。

二叉树的主要优点包括：

  1. 高效的数据存储和检索
  2. 有序数据的快速查找（二叉搜索树）
  3. 表示层次结构的自然方式
  4. 支持多种高效的遍历算法

在学习和使用二叉树时，需要注意树的平衡性，因为不平衡的树可能会导致操作效率降低。例如，一个极度不平衡的二叉搜索树可能会退化成链表，使得查找操作的时间复杂度从 O(log n) 变为 O(n)。

Share

目录

查看所有文章...