术语

根结点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。

遍历(前中后层)

前序遍历