术语

根结点root
叶子结点/终端结点（Leaf）：度为0的结点；
分支结点/非终端结点internal node：度不为0的结点
父结点（Parent）
子结点/孩子结点（Child）：左子结点、右子结点
兄弟结点（Sibling）
祖先结点（Ancestor）：含父结点
子孙结点（Descendant）：含子结点

结点的度Degree：结点拥有子树（孩子结点）的个数
树的度：树中各结点中最大的度
路径path和路径长度：从结点n1到nk的路径为一个结点序列n1，n2，…，nk。ni是ni+1的父结点。路径所包含边的个数为路径的长度；
结点的层次Level：规定根结点在1层，其他任一结点的层数是其父结点的层数加1；即到根结点的路径长度加1
树的高度/深度Depth：树中所有结点中的最大层次

二叉树Binary Tree

定义

树（Tree）：n（n≥0）个结点构成的有限集合。当n=0时，称为“空树”；对于任一棵“非空树”（n>0），它具备以下性质：

  • 树中有一个称为“根（Root）”的特殊结点，用r表示；
  • 其余结点可分为m（m≥0）个“互不相交”的有限集T1，T2，…，Tm，其中每一个集合本身又是一棵树，称为原来树的“子树（SubTree）”。

特点：

  • 子树是不相交的；
  • 除了根结点外，每个结点有且仅有一个父节点；
  • 一棵N个结点的树有N-1条边。

二叉树T：一个有穷的结点集合。这个集合可以为空；若不为空，则它是由根结点和称为其左子树TL和右子树TR的两个不相交的二叉树组成。二叉树的子树有左右顺序之分。
二叉树的五种基本形态：
image.png
【特殊的二叉树】

  • 斜二叉树（Skewed Binary Tree）：分左右

    树 - 图2

  • 满二叉树（Full Binary Tree）/ 完美二叉树（Perfect Binary Tree）：除最后一层无任何子结点外，每一层上的所有结点都有两个子结点的二叉树。

    树 - 图3

  • 完全二叉树（Complete Binary Tree）：有n个结点的二叉树，对树中结点从上至下、从左到右顺序进行编号，编号为i（1≤i≤n）结点与满二叉树中编号为i结点在二叉树中的位置相同。

    树 - 图4
    完全二叉树的顺序存储结构中，按从上至下、从左到右顺序存储n个结点的完全二叉树的结点父子关系：

  1. 根结点的序号为1；
  2. 非根结点（序号i>1）的父结点的序号是：i / 2；
  3. 结点（序号为i）的左孩子结点的序号是：2 i，若2i > n，则没有左孩子；

  4. 结点（序号为i）的右孩子结点的序号是：2 i + 1，若2i+1 > n，则没有右孩子；

    二叉树

    性质

  5. 一个二叉树第i层的最大结点数为：2i-1，i≥1；

  6. 深度为k的二叉树有最大结点总数为：2k-1，k≥1；

  7. 对任何非空二叉树T，若n0表示叶结点的个数，n2是度为2的非叶结点个数，那么两者满足关系：n0=n2+1；

    假设：叶结点个数为n0；度为1的结点个数为n1；度为2的结点个数为n2。
    则二叉树的总边数N=2n2+n1；总结点数N′=n0+n1+n2；
    因N+1=N′，所以2    n2+n1+1=n0+n1+n2；得n0=n2+1。

遍历（前中后层）

前序遍历