什么是二叉树

任意节点的度不大于 2 的树是二叉树

二叉树创建

节点定义

1
2
3
4
5

function Node(val) {
  this.val = val;
  this.left = null;
  this.right = null;
}

粗暴创建

1
2
3
4
5
6
7
8

var tree = new Node(1);
tree.left = new Node(2);
tree.right = new Node(3);
tree.right.right = new Node(6);
tree.left.left = new Node(4);
tree.left.right = new Node(5);
tree.left.right.left = new Node(7);
tree.left.right.right = new Node(8);

二叉树遍历

通过上面的创建，我们生成了如下的二叉树数据

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

var tree = {
  value: 1,
  left: {
    value: 2,
    left: {
      value: 4
    },
    right: {
      value: 5,
      left: {
        value: 7
      },
      right: {
        value: 8
      }
    }
  },
  right: {
    value: 3,
    right: {
      value: 6
    }
  }
};

前序遍历

中->左->右

  1. 递归

    1
2
3
4
5
6
7
8
9

    var preOrderRecurseStack = [];

function preOrderRecurseTraverse(tree) {
if (tree) {
preOrderRecurseStack.push(tree.value);
preOrderRecurseTraverse(tree.left);
preOrderRecurseTraverse(tree.right);
}
}

  2. 非递归

     1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

    var preOrderStack = [];
function preOrderTraverse(tree) {
var stack = [];
var currentNode = tree;
while (currentNode || stack.length > 0) {
if (currentNode) {
  preOrderStack.push(currentNode.value);
  stack.push(currentNode);
  currentNode = currentNode.left;
} else {
  var node = stack.pop();
  currentNode = node.right;
}
}
}

中序遍历

左->中->右

  1. 递归

    1
2
3
4
5
6
7
8

    var inOrderRecurseStack = [];
function inOrderRecurseTraverse(tree) {
if (tree) {
inOrderRecurseTraverse(tree.left);
inOrderRecurseStack.push(tree.value);
inOrderRecurseTraverse(tree.right);
}
}

  2. 非递归

     1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

    var inOrderStack = [];
function inOrderTraverse(tree) {
var stack = [];
var currentNode = tree;
while (currentNode || stack.length > 0) {
if (currentNode) {
  stack.push(currentNode);
  currentNode = currentNode.left;
} else {
  var node = stack.pop();
  inOrderStack.push(node.value);
  currentNode = node.right;
}
}
}

后序遍历

左->右->中

  1. 递归

    1
2
3
4
5
6
7
8

    var postOrderRecurseStack = [];
function postOrderRecurseTraverse(tree) {
if (tree) {
postOrderRecurseTraverse(tree.left);
postOrderRecurseTraverse(tree.right);
postOrderRecurseStack.push(tree.value);
}
}

  2. 非递归

二叉树是对称的，所以正向的后序遍历和逆向的先序遍历是反过来的

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

var postOrderStack = [];
function postOrderTraverse(tree) {
  var stack = [];
  var currentNode = tree;
  while (currentNode || stack.length > 0) {
    if (currentNode) {
      postOrderStack.push(currentNode.value);
      stack.push(currentNode);
      currentNode = currentNode.right;
    } else {
      var node = stack.pop();
      currentNode = node.left;
    }
  }
}

广度优先遍历（层次遍历）

从左到右，一层一层

  1. 递归

     1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

    function bfsRecurse(tree) {
var bfsRecurseStack = [tree];
var bfsRecurseResult = [];
var count = 0;
(function inner() {
var node = bfsRecurseStack[count];
if (node) {
  bfsRecurseResult.push(node.value);
  if (node.left) bfsRecurseStack.push(node.left);
  if (node.right) bfsRecurseStack.push(node.right);
  count++;
  inner();
}
})();
return bfsRecurseResult;
}

  2. 非递归

     1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

    function bfs(tree) {
var bfsStack = [tree];
var bfsResult = [];
var count = 0;
while (count < bfsStack.length) {
var node = bfsStack[count++];
bfsResult.push(node.value);
if (node.left) bfsStack.push(node.left);
if (node.right) bfsStack.push(node.right);
}

return bfsResult;
}

总结：

  1. 二叉树遍历递归实现比较好理解，但是性能不好（每次进入函数环境的消耗，栈消耗，不必要步骤的运行）
  2. 二叉树的非递归实现，也是利用栈（js 数组），是我们自己用逻辑控制的，性能更好