数据结构与算法(4): 树形结构-树&二叉树

发表于   |   分类于

树

定义

树：是n(n>=0)个节点的有限集。

  • 当n=0时，称为空树
  • 有且仅有一个特定的节点称为根节点
  • 当n>1时，其余节点可分为k(k>0)个互不相交的有限集T1，T2，…，T3，其中每个集合本身又是一棵树，并且称为根的子树。

特性

  1. 节点的度：节点拥有的子树个数；树的度是树内各节点的度的最大值。
  2. 树叶（终端节点）：没有儿子的节点，度为0。
  3. 分支节点（非终端节点）：度不为0的节点。
  4. 内部节点：除根节点之外的分支节点。
  5. 节点的层次：从根开始定义，根为第一层。
  6. 节点的深度：节点i的深度为从根到节点i的唯一路径的长。根的深度为1，树的深度为最深的树叶的深度。
  7. 节点的高度：节点i的高度为从该节点到一片树叶的最长路径的长。树叶的高度为1，树的高为根的高，等于树的深度。

    注：查看国内资料博客时，基本上将根的深度和树叶的高度都设为1，国外的教材教材上则设为0，本文将以1作为标准。

实现

  • 双亲表示法：所有的节点都存有它双亲节点的位置
  • 孩子表示法：每个节点有多个指针域，其中每个指针指向一棵子树的根节点。
  • 孩子兄弟表示法：每个节点有两个指针域，一个指向该节点的第一个孩子节点，另一个指向该节点的右兄弟节点。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    /**
     * 树的实现：孩子兄弟表示法,
     * 如果想获取某节点的双亲节点，可以再添加一个双亲指针域
     */
    public class Tree<T> {
        private static class TreeNode<T>{
            T element;
            // 孩子指针域：指向第一个儿子节点
            TreeNode<T> firstChild;
            // 兄弟指针域：指向兄弟节点
            TreeNode<T> nextSibling;
        }
    }

二叉树

特点

  • 每个节点最多有两棵子树，所以二叉树中不存在度大于2的节点。
  • 左子树和右子树是有顺序的，次序不能任意颠倒。
  • 即使树中某节点只有一棵子树，也要区分它是左子树还是右子树。

性质

  • 一棵非空二叉树的第i层上最多有$2^{i-1}$(i>=1)个节点。
  • 根的深度为1，则深度为k(k>=0)的二叉树最多有$2^{i}-1$个节点
  • 具有n个节点的完全二叉树的深度k为$log_{2}n+1$。
  • 对于一棵非空二叉树，如果度为0的节点树为$n_0$，度为2的节点树为$n_2$，则有$n_0=n_2+1$。

特殊的二叉树

  • 满二叉树：在一棵二叉树中，如果所有分支节点都存在左子树和右子树，并且所有叶子节点都在同一层上，这样的二叉树称为满二叉树。
  • 完全二叉树：对一棵具有n个节点的二叉树按层序编号，如果编号为i（1≤i≤n）的节点与同样深度的满二叉树中编号为i的节点在二叉树中位置完全相同
    • 叶子节点只能出现在最下两层；
    • 最下层的叶子一定集中在左部连续位置；
    • 倒数二层，若有叶子节点，一定都在右部连续位置；
    • 如果节点度为1，则该节点只有左孩子，即不存在只有右子树的情况；
    • 同样节点数的二叉树，完全二叉树的深度最小。

遍历

  1. 前序遍历

    对当前节点的处理工作是在它的各个儿子节点被处理之前进行的。

  2. 中序遍历

    对当前节点的处理工作是在它的左儿子节点被处理之后，在右儿子节点被处理之前进行的。

  3. 后序遍历

    对当前节点的处理工作是在它的各个儿子节点被处理之后进行的。

  • 给定二叉树结点的前序序列和中序序列，可以唯一确定该二叉树。

    步骤：先看前序序列，从左往右方向，确定根节点；再看中序序列找到根节点的左右子树包含的节点；接着对前序序列进行左右子树划分，重复上述步骤即可。

  • 给定二叉树结点的后序序列和中序序列，可以唯一确定该二叉树。

    步骤：先看后序序列，从右往左方向，确定根节点；再看中序序列找到根节点的左右子树包含的节点；接着对前序序列进行左右子树划分，重复上述步骤即可。