二叉树及常见遍历方法

在计算机科学中，二叉树是每个结点最多有两个子树的树结构。 通常子树被称作“左子树”（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

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