Faster, Higher, Stronger
更快,更高,更强

二叉树及常见遍历方法

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

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

赞(0) 打赏
未经允许不得转载:峰间的云 » 二叉树及常见遍历方法

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

微信扫一扫打赏