定义

二叉树（binary tree）是指树中节点的度不大于2的有序树，它是一种最简单且最重要的树。二叉树的递归定义为：二叉树是一棵空树，或者是一棵由一个根节点和两棵互不相交的，分别称作根的左子树和右子树组成的非空树；左子树和右子树又同样都是二叉树。

实现

结构定义

尝试了一下C语言，各种指针乱指，各种bug，暂时放自己一马，跟自己和解一下用js写写吧。

1
2
3
4
5
6
7
class TreeNode {
  constructor(data) {
    this.data = data;
    this.left = null;  // 左节点
    this.right = null; // 右边节点
  }
}

创建对象并绑定节点

1
2
3
4
5
6
// 手动绑定节点
let root = new TreeNode(1)
root.left = new TreeNode(2)
root.right = new TreeNode(3)
root.left.left = new TreeNode(4)
root.right.right = new TreeNode(5)

此时树的结构：

1
2
3
4
5
    1
   /  \
   2   3
 /  \   \
4    5   6

遍历二叉树

前序遍历（DFS）

1
2
3
4
5
6
7
function preOrder(node) {
  if(node) {
    console.log(node.data)
    preOrder(node.left)
    preOrder(node.right)
  }
}

这里用递归调用，遍历到左右元素

层序遍历（BFS）

1
2
3
4
5
6
7
8
9
10
function levelOrder(root) {
  const queue = [];
  queue.push(root);
  while (queue.length) {
    const node = queue.shift();
    console.log(node.data);
    if (node.left) queue.push(node.left);
    if (node.right) queue.push(node.right);
  }
}