详细介绍JavaScript二叉树及各种遍历算法

1. 什么是二叉树？

二叉树是一种树形结构，由根节点、左子树和右子树组成，左子树和右子树都是二叉树，它们可以为空。

1.1 二叉树的定义

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

上面的代码是定义一个二叉树节点的类，树中的每个节点包含一个值和两个指向左子树和右子树的指针，如果子树为空，则指针为null。

1.2 二叉树的基本操作

二叉树的基本操作包括：节点的插入、节点的删除和节点的查找。

节点的插入：

function insertNode(root, val) {
  if (!root) {
    root = new TreeNode(val);
    return root;
  }
  if (val < root.val) {
    root.left = insertNode(root.left, val);
  } else if (val > root.val) {
    root.right = insertNode(root.right, val);
  }
  return root;
}

上面代码中insertNode函数实现了向二叉树中插入节点的功能，它的参数是一个根节点和待插入节点的值，如果根节点为空，则新建一个节点作为根节点，否则比较当前节点的值与插入值的大小，如果比当前节点小，则插入到左子树中，否则插入到右子树中。

节点的删除：

function deleteNode(root, val) {
  if (!root) {
    return null;
  }
  if (val < root.val) {
    root.left = deleteNode(root.left, val);
  } else if (val > root.val) {
    root.right = deleteNode(root.right, val);
  } else {
    if (!root.left && !root.right) {
      root = null;
    } else if (root.left && !root.right) {
      root = root.left;
    } else if (root.right && !root.left) {
      root = root.right;
    } else {
      let minNode = findMinNode(root.right);
      root.val = minNode.val;
      root.right = deleteNode(root.right, minNode.val);
    }
  }
  return root;
}
function findMinNode(root) {
  while (root.left) {
    root = root.left;
  }
  return root;
}

上面代码中的deleteNode函数实现了从二叉树中删除节点的功能，它的参数是一个根节点和待删除节点的值，如果节点的值大于根节点，则在右子树中查找，若小于根节点，则在左子树中查找，若等于根节点，则分四种情况进行处理，如上述代码。

节点的查找：

function searchNode(root, val) {
  if (!root) {
    return null;
  }
  if (val === root.val) {
    return root;
  } else if (val < root.val) {
    return searchNode(root.left, val);
  } else if (val > root.val) {
    return searchNode(root.right, val);
  }
}

上面代码中的searchNode函数实现了在二叉树中查找节点的功能，它的参数是一个根节点和待查找节点的值，如果节点的值等于根节点，则返回该节点，否则在左子树或右子树中查找。

2. 二叉树的遍历

二叉树的遍历是指按照一定的顺序遍历二叉树中的每一个节点，常见的遍历方式有三种：前序遍历、中序遍历和后序遍历。

2.1 前序遍历

前序遍历顺序是：根节点 -> 左子树 -> 右子树。

function preOrder(root) {
  const arr = [];
  function traverse(node) {
    if (!node) {
      return;
    }
    arr.push(node.val);
    traverse(node.left);
    traverse(node.right);
  }
  traverse(root);
  return arr;
}

上面代码中的preOrder函数实现了前序遍历二叉树的功能，它返回一个存储所有节点值的数组。

2.2 中序遍历

中序遍历顺序是：左子树 -> 根节点 -> 右子树。

function inOrder(root) {
  const arr = [];
  function traverse(node) {
    if (!node) {
      return;
    }
    traverse(node.left);
    arr.push(node.val);
    traverse(node.right);
  }
  traverse(root);
  return arr;
}

上面代码中的inOrder函数实现了中序遍历二叉树的功能，它返回一个存储所有节点值的数组。

2.3 后序遍历

后序遍历顺序是：左子树 -> 右子树 -> 根节点。

function postOrder(root) {
  const arr = [];
  function traverse(node) {
    if (!node) {
      return;
    }
    traverse(node.left);
    traverse(node.right);
    arr.push(node.val);
  }
  traverse(root);
  return arr;
}

上面代码中的postOrder函数实现了后序遍历二叉树的功能，它返回一个存储所有节点值的数组。

3. 总结

二叉树作为一种常用的树形结构，在编写算法时经常被使用。本文介绍了二叉树的基本定义和操作，包括节点的插入、删除和查找，以及三种常见的遍历方式：前序遍历、中序遍历和后序遍历。在实际编程中，我们可以使用递归的方式对二叉树进行遍历，代码实现起来并不复杂。