二叉树及常见遍历方法

在计算机科学中，二叉树是每个结点最多有两个子树的树结构。通常子树被称作“左子树”（left subtree）和“右子树”（right subtree）。二叉树常被用于实现二叉查找树和二叉堆。一棵深度为k，且有2^k-1个结点的二叉树，称为满二叉树。讲到二叉树，它的先序遍历、中序遍历、后续遍历和逐层遍历是最常见的话题。先来看二叉树的生成方法。

// 节点对象的构造函数
function Node(data, left, right) {
  this.data = data;
  this.left = left || null;
  this.right = right || null;
}

Node.prototype.getData = function () {
  return this.data;
};

// 二叉树的构造函数
function BST() {
  this.root = null;
}

function insertNode(parentNode, newNode) {
  if (newNode.data < parentNode.data) {
    if (parentNode.left === null) {
      parentNode.left = newNode;
    } else {
      insertNode(parentNode.left, newNode);
    }
  } else {
    if (parentNode.right === null) {
      parentNode.right = newNode;
    } else {
      insertNode(parentNode.right, newNode);
    }
  }
}

// 插入方法
BST.prototype.insert = function (data) {
  const newNode = new Node(data, null, null);
  if (this.root === null) {
    this.root = newNode;
  } else {
    insertNode(this.root, newNode);
  }
};

// 测试
var nums = new BST();
nums.insert(23);
nums.insert(45);
nums.insert(16);
nums.insert(37);
nums.insert(3);
nums.insert(99);
nums.insert(22);

接下来是二叉树的前序遍历、中序遍历和后序遍历。

function preOrder(node, cb) {
  if (node !== null) {
    cb && cb(node.getData());
    preOrder(node.left, cb);
    preOrder(node.right, cb);
  }
}

function inOrder(node, cb) {
  if (node !== null) {
    inOrder(node.left, cb);
    cb && cb(node.getData());
    inOrder(node.right, cb);
  }
}

function postOrder(node, cb) {
  if (node !== null) {
    postOrder(node.left, cb);
    postOrder(node.right, cb);
    cb && cb(node.getData());
  }
}

// 先序遍历二叉树（先中间，然后左边，然后右边）
BST.prototype.preOrder = preOrder;

// 中序遍历二叉树（先左边，然后中间，然后右边）
BST.prototype.inOrder = inOrder;

// 后序遍历二叉树（先左边，然后右边，然后中间）
BST.prototype.postOrder = postOrder;

nums.inOrder(nums.root, console.log);

// 依次输出如下内容：
// 3
// 16
// 22
// 23
// 37
// 45
// 99

nums.preOrder(nums.root, console.log);

// 依次输入如下内容：
// 23
// 16
// 3
// 22
// 45
// 37
// 99

nums.postOrder(nums.root, console.log);

// 依次输入如下内容：
// 3
// 22
// 16
// 37
// 99
// 45
// 23

最后是二叉树的逐层遍历（从上往下逐层遍历）。这里只说一下思路。用上面的先序遍历方法遍历二叉树，将遍历到的内容一次加入一个队列。最后再从队头开始打印队列即可。

二叉树及常见遍历方法 ​

二叉树及常见遍历方法