二叉树

  • 二叉树
  • 平衡二叉树
    • 二叉树中任意结点的左右子树深度相差不超过 1。
  • 二叉搜索树
    • 若任意节点的左子树不空,则左子树上所有节点的值均小于它的根节点的值;
    • 若任意节点的右子树不空,则右子树上所有节点的值均大于它的根节点的值;
    • 任意节点的左、右子树也分别为二叉查找树;
    • 没有键值相等的节点

深度优先遍历(或搜索)有三种

  • 先序遍历
  • 中序遍历
  • 后序遍历

广度优先遍历(或搜索)一般有一种。

最近公共祖先(Lowest Common Ancestor)

二叉树打印

二叉树按层遍历

  • 即广度优先遍历
  • 使用队列结构实现
  • 可能要求时要求把行号也打印出来

二叉树的序列化和反序列化

  • 序列化
    • 二叉树→字符串
  • 反序列化
    • 字符串→二叉树

前缀树 - Trie

References

  1. 1.1 二叉树打印