是什么

树： 非线性数据结构， 表示一对多的关系。

常用树为二叉树

二叉树

条件

1. 是有序树
2. 节点个数不超过 2，即只能是 0、1、2

分类

1. 满二叉树： 除叶子节点，每个节点个数为 2 个

2. 完全二叉树: 除叶子节点，最后一层节点依次从左到右排列

遍历

• 前序遍历
• 中序遍历
• 后续遍历

  遍历区分： 访问根节点的表现

1. 递归实现

const tree = (root) => {
  if (!root) return;
  console.log(root.value);
  tree(root.left);
  tree(root.right);
};

const tree = (root) => {
  if (!root) return;
  tree(root.left);
  console.log(root.value);
  tree(root.right);
};

const tree = (root) => {
  if (!root) return;
  tree(root.left);
  tree(root.right);
  console.log(root.value);
};

2. 非递归

const tree = (root) => {
  if (!root) return;
  const stack = [root];
  while (stack.length) {
    const current = stack.pop();
    console.log(current.value); // 访问根
    if (current.left) stack.push(current.left);
    if (current.right) stack.push(current.right);
  }
};