阿呆的博客

# 基本概念

树是一种分层数据的抽象模型，它对于存储需要快速查找的数据非常有用。

生活中最常见的例子就是家谱，公司的组织架构等。

# 相关术语

一个树由一系列存在父子关系的节点组成。一个节点可以有祖先和后代。

位于树顶部的节点叫做根结点，根结点没有父节点。没有后代的节点称为叶节点。

# 二叉树

二叉树中的节点最多只能有两个子节点，一个是左侧子节点，一个是右侧子节点。

# 二叉搜索树

二叉搜索树是二叉树的一种，但是只允许在左侧节点存储比父节点小的值，在右侧节点存储比父节点大的值。

# 树的遍历

树的遍历分为两种，分别是深度优先遍历(简称DFS)和广度优先遍历(简称BFS)。

  • 深度优先遍历

    • 先序遍历
      先访问节点本身，然后在访问它的左侧子节点，最后是右侧子节点。
      递归代码

      var preorderTraversal = function(root) {
    const result = []
    function dfs(root) {
        if(!root) {
            return
        }
        result.push(root.val)
        dfs(root.left)
        dfs(root.right)
    }
    dfs(root)
    return result
}

      迭代代码
      使用颜色标记法，白色表示节点未进行遍历，黑色表示节点已经遍历过了。

      var preorderTraversal = function(root) {
    const result = []
    const WHITE = 'WHITE'
    const BLACK = 'BLACK'
    const stack = []
    stack.push({color: WHITE, node: root})
    while(stack.length) {
        const item = stack.pop()
        if(item.node) {
            if(item.color === WHITE) {
                stack.push({color: WHITE, node: item.node.right})
                stack.push({color: WHITE, node: item.node.left})
                stack.push({color: BLACK, node: item.node})
            }else {
                result.push(item.node.val)
            }
        }
    }
    return result
}

    • 中序遍历
      先访问左侧子节点，然后在访问节点本身，最后是右侧子节点。
      递归代码

      var inorderTraversal = function(root) {
    const result = []
    function dfs(root) {
        if(!root) {
            return
        }
        dfs(root.left)
        result.push(root.val)
        dfs(root.right)
    }
    dfs(root)
    return result
}

      迭代代码

      var inorderTraversal = function(root) {
    const result = []
    const WHITE = 'WHITE'
    const BLACK = 'BLACK'
    const stack = []
    stack.push({color: WHITE, node: root})
    while(stack.length) {
        const item = stack.pop()
        if(item.node) {
            if(item.color === WHITE) {
                stack.push({color: WHITE, node: item.node.right})
                stack.push({color: BLACK, node: item.node})
                stack.push({color: WHITE, node: item.node.left}) 
            }else {
                result.push(item.node.val)
            }
        }
    }
    return result
}

    • 后序遍历
      先访问左侧子节点，然后在访问右侧子节点，最后是节点本身。
      递归代码

      var postorderTraversal = function(root) {
    const result = []
    function dfs(root) {
        if(!root) {
            return
        }
        dfs(root.left)
        dfs(root.right)
        result.push(root.val)
    }
    dfs(root)
    return result
}

      迭代代码

      var postorderTraversal = function(root) {
    const result = []
    const WHITE = 'WHITE'
    const BLACK = 'BLACK'
    const stack = []
    stack.push({color: WHITE, node: root})
    while(stack.length) {
        const item = stack.pop()
        if(item.node) {
            if(item.color === WHITE) {
                stack.push({color: BLACK, node: item.node})
                stack.push({color: WHITE, node: item.node.right})
                stack.push({color: WHITE, node: item.node.left}) 
            }else {
                result.push(item.node.val)
            }
        }
    }
    return result
}

  • 广度优先遍历

    var bfs = function(root) {
    if(!root) {
        return []
    }
    const result = []
    const queue = []
    queue.push(root)
    while(queue.length) {
        const node = queue.shift()
        result.push(node.val)
        if(node.left) {
            queue.push(node.left)
        }
        if(node.right) {
            queue.push(node.right)
        }
    }
    return result
}

  • 小结
    我们不难发现树的深度优先遍历方式代码都是几乎一样的，区别只是位置有所调整而已。

# 推荐题目(应该掌握的题目)

# 更多文章

← 最小堆 →