树结构详细介绍（javascript版）-CSDN博客

本文链接：https://blog.csdn.net/wl_qianduan/article/details/148255522

树结构的基本概念

树是一种非线性数据结构，由节点和连接节点的边组成。与线性数据结构（如数组、链表）不同，树具有层次结构，非常适合表示有层次关系的数据。

树的基本术语

节点 (Node)： 树中的基本单元，包含数据和指向其他节点的引用
根节点 (Root)： 树的顶部节点，没有父节点
子节点 (Child)： 一个节点的直接下级节点
父节点 (Parent)： 一个节点的直接上级节点
叶节点 (Leaf)： 没有子节点的节点
路径 (Path)： 连接一个节点到另一个节点的节点序列
高度 (Height)： 从叶节点到该节点的最长路径上的节点数
深度 (Depth)： 从根节点到该节点的边数

JavaScript 实现基本树结构

下面是一个使用 JavaScript 实现的基本树结构：

class TreeNode {
  constructor(value) {
    this.value = value;
    this.children = [];
  }
  // 添加子节点
  addChild(childNode) {
    this.children.push(childNode);
    return this;
  }
  // 移除子节点
  removeChild(childNode) {
    const index = this.children.indexOf(childNode);
    if (index !== -1) {
      this.children.splice(index, 1);
    }
    return this;
  }
  // 深度优先遍历
  depthFirstTraversal() {
    const result = [];    
    function traverse(node) {
      result.push(node.value);
      node.children.forEach(child => traverse(child));
    }    
    traverse(this);
    return result;
  }
  // 广度优先遍历
  breadthFirstTraversal() {
    const result = [];
    const queue = [this];
    
    while (queue.length > 0) {
      const currentNode = queue.shift();
      result.push(currentNode.value);
      currentNode.children.forEach(child => queue.push(child));
    }    
    return result;
  }
}

// 使用示例
const root = new TreeNode(1);
const child1 = new TreeNode(2);
const child2 = new TreeNode(3);
const grandChild1 = new TreeNode(4);
const grandChild2 = new TreeNode(5);

child1.addChild(grandChild1);
child2.addChild(grandChild2);
root.addChild(child1).addChild(child2);

console.log("深度优先遍历:", root.depthFirstTraversal()); // [1, 2, 4, 3, 5]
console.log("广度优先遍历:", root.breadthFirstTraversal()); // [1, 2, 3, 4, 5]

树的常见类型

二叉树 (Binary Tree)
二叉树是一种特殊的树，每个节点最多有两个子节点，通常称为左子节点和右子节点。

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

class BinaryTree {
  constructor() {
    this.root = null;
  }	
  // 插入节点
  insert(value) {
    const newNode = new BinaryTreeNode(value);	    
    if (!this.root) {
      this.root = newNode;
      return this;
    }	    
    let current = this.root;
    while (true) {
      if (value === current.value) return undefined;	      
      if (value < current.value) {
        if (!current.left) {
          current.left = newNode;
          return this;
        }
        current = current.left;
      } else {
        if (!current.right) {
          current.right = newNode;
          return this;
        }
        current = current.right;
      }
    }
  }

  // 查找节点
  find(value) {
    if (!this.root) return false;	    
    let current = this.root;
    let found = false;	    
    while (current && !found) {
      if (value < current.value) {
        current = current.left;
      } else if (value > current.value) {
        current = current.right;
      } else {
        found = true;
      }
    }	    
    return found ? current : false;
  }

  // 前序遍历 (根 -> 左 -> 右)
  preOrderTraversal() {
    const result = [];	    
    function traverse(node) {
      result.push(node.value);
      if (node.left) traverse(node.left);
      if (node.right) traverse(node.right);
    }	    
    traverse(this.root);
    return result;
  }	
  // 中序遍历 (左 -> 根 -> 右)
  inOrderTraversal() {
    const result = [];	    
    function traverse(node) {
      if (node.left) traverse(node.left);
      result.push(node.value);
      if (node.right) traverse(node.right);
    }	    
    traverse(this.root);
    return result;
  }	
  // 后序遍历 (左 -> 右 -> 根)
  postOrderTraversal() {
    const result = [];	    
    function traverse(node) {
      if (node.left) traverse(node.left);
      if (node.right) traverse(node.right);
      result.push(node.value);
    }	    
    traverse(this.root);
    return result;
  }
}	
// 使用示例
const binaryTree = new BinaryTree();
binaryTree.insert(10);
binaryTree.insert(6);
binaryTree.insert(15);
binaryTree.insert(3);
binaryTree.insert(8);
binaryTree.insert(20);
console.log("前序遍历:", binaryTree.preOrderTraversal()); // [10, 6, 3, 8, 15, 20]
console.log("中序遍历:", binaryTree.inOrderTraversal()); // [3, 6, 8, 10, 15, 20]
console.log("后序遍历:", binaryTree.postOrderTraversal()); // [3, 8, 6, 20, 15, 10]

二叉搜索树 (Binary Search Tree, BST)

二叉搜索树是一种特殊的二叉树，对于树中的每个节点：

左子树中所有节点的值都小于该节点的值
右子树中所有节点的值都大于该节点的值
左右子树也分别是二叉搜索树

上面的二叉树实现实际上就是一个二叉搜索树的实现，它提供了高效的查找、插入和删除操作，时间复杂度为 O (log n)。

平衡二叉树 (AVL Tree)

平衡二叉树是一种特殊的二叉搜索树，它的每个节点的左右子树的高度差不超过 1。这种平衡特性保证了树的高度始终保持在 O (log n)，从而保证了所有操作的时间复杂度都是 O (log n)。

红黑树 (Red-Black Tree)

红黑树是一种自平衡的二叉搜索树，它通过为每个节点分配一个颜色（红色或黑色）并遵循一些特定的规则来保持树的平衡。红黑树的平衡性不如 AVL 树严格，但它的插入和删除操作更快。

树的遍历方法

树的遍历是指按照某种顺序访问树中的所有节点。主要有两种遍历方式：

深度优先遍历 (DFS)
深度优先遍历沿着树的深度遍历树的节点，尽可能深的搜索树的分支。主要有三种实现方式：
- 前序遍历 (Pre-order)： 根节点 -> 左子树 -> 右子树
- 中序遍历 (In-order)： 左子树 -> 根节点 -> 右子树
- 后序遍历 (Post-order)： 左子树 -> 右子树 -> 根节点
广度优先遍历 (BFS)
广度优先遍历按照层次依次访问树中的节点，从上到下，从左到右。