二叉树的遍历

Search…
二叉树的遍历
二叉树的遍历
二叉树（Binary Tree）每个节点最多有两个子节点的树型数据结构。
1
class TreeNode {
2
  constructor(val, left = null, right = null) {
3
    this.val = val;
4
    this.left = left;
5
    this.right = right;
6
  }
7
}
Copied!
二叉树的遍历方式主要分为 深度优先（Deep-first Search, DFS） 和 广度优先（Breadth-first Search，BFS）。
其中深度优先遍历有以下几种方法
1.前序遍历
2.中序遍历
3.后序遍历
深度优先
深度优先顾名思义就是先纵向搜索，在进入下一个兄弟节点之前，尽可能的向下搜索每一个子节点。 该算法从根节点开始（在图的情况下选择一些任意节点作为根节点）并在回溯之前尽可能地沿着每个分支进行探索。
前序遍历
前序遍历（pre-order）的访问顺序是 DLR
L 为左子树，R 为右子树，D 为根节点
Could not load image
上图的前序遍历顺序为: ABDGHCEIF
前序遍历的递归方式
1
function preOrder(root) {
2
  if (!root) {
3
    return;
4
  }
5
  // do something
6
  // console.log(root.val)
7
  preOrder(root.left);
8
  preOrder(root.right);
9
}
Copied!
前序遍历的非递归方式
对于任一结点 P：
1.访问结点 P，并将结点 P 入栈;
2.判断结点 P 的左孩子是否为空，若为空，则取栈顶结点并进行出栈操作，并将栈顶结点的右孩子置为当前的结点 P，循环至 1; 若不为空，则将 P 的左孩子置为当前的结点 P;
3.直到 P 为 null 并且栈为空，则遍历结束。
1
function preOrderWithoutRecursion(root) {
2
  const stack = [];
3
  let node = root;
4
  while (node || stack.length > 0) {
5
    if (node) {
6
      // do something
7
      // console.log(node.val);
8
      stack.push(node);
9
      node = node.left;
10
    } else {
11
      node = stack.pop().right;
12
    }
13
  }
14
}
Copied!
中序遍历
中序遍历（in-order）的顺序是 LDR
Could not load image
上图的中序遍历顺序为: GDHBAEICF
中序遍历的递归方式
1
function inOrder(root) {
2
  if (!root) {
3
    return;
4
  }
5
  inOrder(root.left);
6
  // do something
7
  // console.log(root.val);
8
  inOrder(root.right);
9
}
Copied!
中序遍历的非递归方式
对于任一结点 P：
1.若其左孩子不为空，则将 P 入栈并将 P 的左孩子置为当前的 P，然后对当前结点 P 再进行相同的处理；
2.若其左孩子为空，则取栈顶元素并进行出栈操作，访问该栈顶结点，然后将当前的 P 置为栈顶结点的右孩子；
3.直到 P 为 null 并且栈为空则遍历结束
1
function inOrderWithoutRecursion(root) {
2
  const stack = [];
3
  let node = root;
4
  while (node || stack.length > 0) {
5
    if (node) {
6
      stack.push(node);
7
      node = node.left;
8
    } else {
9
      const lastNode = stack.pop();
10
      // do something
11
      // console.log(lastNode.val);
12
      node = lastNode.right;
13
    }
14
  }
15
}
Copied!
后序遍历
后序遍历（post order）的顺序是 LRD
Could not load image
上图的后序遍历顺序为: GHDBIEFCA
后序遍历的递归方式
1
function postOrder(root) {
2
  if (!root) {
3
    return;
4
  }
5
​
6
  postOrder(root.left);
7
  postOrder(root.right);
8
  // do something
9
  // console.log(root.val);
10
}
Copied!
后序遍历的非递归方式
1
function postOrderWithoutRecursion(root) {
2
  if (!root) {
3
    return;
4
  }
5
  const stack = [];
6
  let node = root;
7
  let last = node;
8
  stack.push(node);
9
  while (stack.length > 0) {
10
    node = stack[stack.length - 1];
11
    if (
12
      (!node.left && !node.right) ||
13
      (!node.right && last === node.left) ||
14
      last === node.right
15
    ) {
16
      // doing something
17
      // console.log(node.val);
18
      last = node;
19
      stack.pop();
20
    } else {
21
      if (node.right) {
22
        stack.push(node.right);
23
      }
24
      if (node.left) {
25
        stack.push(node.left);
26
      }
27
    }
28
  }
29
}
Copied!
广度优先遍历
广度优先遍历，也可以称之为层级遍历，先访问兄弟节点，再访问子节点。
Could not load image
上图的后序遍历顺序为: FBGADICEH
1
function bfs(root) {
2
  if (!root) {
3
    return;
4
  }
5
  const queue = [root];
6
​
7
  while (queue.length > 0) {
8
    const node = queue.shift();
9
    // do something
10
    // console.log(node.val)
11
    if (node.left) {
12
      queue.push(node.left);
13
    }
14
    if (node.right) {
15
      queue.push(node.right);
16
    }
17
  }
18
}
Copied!
基数排序
HTTP
Last modified 2yr ago
Copy link
Contents