数据结构之树

• 二叉树
  • 二叉树遍历
  • 完全二叉树
  • 满二叉树
  • 二叉搜索树
• BMW WARNING

二叉树

二叉树遍历

深度优先遍历（DFS），根据父节点被访问的次序，分为：

• 先序遍历（Preorder）

父节点先于左右子树被遍历。
上述二叉树对应结果为

ABDHIEJKCFLG

• 中序遍历（Inorder）

父节点遍历次序位于左右子树中间。

HDIBJEKALFCG

• 后序遍历（Postorder）

父节点后于左右子树被遍历

HIDJKEBLFGCA

无论父节点被访问的次序，子树总是先左后右被遍历。

二叉树的深度优先遍历用 Python3 实现如下（对应 leetcode 题目）

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right


class Solution:
  # 先序遍历
  def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
      ret = []
      def traversal(root):
          if not root:
              return
          ret.append(root.val)
          if root.left:
                traversal(root.left)
          if root.right:
                traversal(root.right)
      traversal(root)
      return ret

  # 中序遍历
    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        ret = []
        def traversal(root):
            if not root:
                return
            if root.left:
                 traversal(root.left)
            ret.append(root.val)
            if root.right:
                 traversal(root.right)
        traversal(root)
        return ret
  # 后序遍历
  def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
      ret = []
      def traversal(root):
          if not root:
              return
          if root.left:
                traversal(root.left)
          if root.right:
                traversal(root.right)
          ret.append(root.val)
      traversal(root)
      return ret

另外还可使用广度优先遍历（BFS），即层次（层序）遍历。
从左到右一层一层访问所有节点

ABCDEFGHIJKL

层次遍历用 Python 实现如下（对应 leetcode 题目）

# @lc code=start
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    # 递归版本
    def levelOrderRecursion(self, root: Optional[TreeNode]) -> List[List[int]]:
        if not root:
            return []
        ret = []
        def traversal(preLevel):
            level = []
            cells = []
            for node in preLevel:
                cells.append(node.val)
                if node.left:
                    level.append(node.left)
                if node.right:
                    level.append(node.right)
            ret.append(cells)
            if len(level):
                traversal(level)
        traversal([root])
        return ret

    # 双层循环版本
    def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        if not root:
            return []
        ret = []
        level = [root]
        while len(level):
            cells = []
            preLevel = level
            level = []
            for node in preLevel:
                cells.append(node.val)
                if node.left:
                    level.append(node.left)
                if node.right:
                    level.append(node.right)
            ret.append(cells)
        return ret

    # 双层循环版本使用队列优化空间
    def levelOrderQueue(self, root: Optional[TreeNode]) -> List[List[int]]:
        if not root:
            return []
        ret = []
        level = [root]
        while len(level):
            cells = []
            for _ in range(len(level)):
                node = level.pop(0)
                cells.append(node.val)
                if node.left:
                    level.append(node.left)
                if node.right:
                    level.append(node.right)
            ret.append(cells)
        return ret

可以看到，对于变长数组的循环，可以采用while方式进行。

完全二叉树

二叉树是指最多只存在两个子节点的树形数据结构。
完全二叉树是指除了最后一层的叶子节点，每一层节点都存在两个子结点，且最后一层的叶子节点由左起依次排列，排列连续中间不能留空的二叉树。
完全二叉树最后一层节点数量不必达到最大数。

数组可以表示一个典型的完全二叉树。
i（索引） 为 0 的节点为根节点。
所有左子节点的索引为 2i+1，右子节点的索引为 2i+2。
同时，可以通过(i-1)/2 获取其父节点的值

满二叉树

每一层节点达到最大数，除最后一层无任何子节点外，每一层上的所有结点都有两个子结点的二叉树。

满二叉树是一个特殊的完全二叉树。

二叉搜索树

二叉搜索树（BST）满足如下定义：

结点左子树中所含节点的值 小于等于 当前节点的值
结点右子树中所含节点的值 大于等于 当前节点的值
左子树和右子树都是二叉搜索树

中序遍历二叉搜索树等于遍历有序数组

BMW WARNING

• Bulletin

本文首发于 skyline.show 欢迎访问。
文章实时更新，如果有什么错误或不严谨之处望请指出，十分感谢。
如果你觉得有用，欢迎到Github 仓库点亮 ⭐️

I am a bucolic migant worker but I never walk backwards.

• Material

参考资料如下列出，部分引用可能遗漏或不可考，侵删。

https://leetcode.cn/problems/binary-tree-preorder-traversal/ > https://leetcode.cn/problems/binary-tree-level-order-traversal/

• Warrant

本文作者： Skyline(lty)

文章链接：http://www.skyline.show/数据结构之树.html

授权声明： 本博客所有文章除特别声明外， 均采用 CC BY - NC - SA 3.0 协议。 转载请注明出处！