树和二叉树基本概念

  • 树是由一个汇合以及在该汇合上定义的一种关系形成的
  • 汇合中的元素称为树的结点，所定义的关系称为父子关系
  • 父子关系在树的结点之间建设了一个层次结构
  • 树的结点蕴含一个数据元素和指向其子树的若干分支
  • 根结点具备非凡位置，简称为根

树（tree）是n（n>=0）个结点的无限集

  • 或者是一个空树（n=0），空树中不蕴含任何结点
  • 或者是一棵非空树（n>0），此时有且仅有一个称为根的特定的结点

结点的度与树的度

  • 结点领有的子树的数目称为结点的度（Degree）
  • 度为0的结点称为叶子（leaf）结点或终端结点
  • 度不为0的结点称为非终端结点或分支结点。除根之外的分支结点也称为外部结点
  • 树内各结点的度的最大值称为树的度

结点的档次和树的深度

  • 结点的档次（level）从根开始定义，根结点档次为1，其子树档次为2
  • 树中的最大档次数称为数的深度（Depth）或高度

父亲、儿子、兄弟

  • 父亲（parent）：一个结点的间接前驱结点
  • 儿子（child）：一个结点的间接后继结点
  • 兄弟（sibling）：同一个父亲结点的其余结点

先人、子孙、堂兄弟

  • 先人：从根到该结点的门路上的所有结点
  • 子孙：以某结点为根的树中的任一结点都是该结点的子孙
  • 堂兄弟：父亲结点在同一档次的结点

有序树、m叉树、森林

  • 有序树：树中结点的各子树从左至右看成有程序的（若不特指阐明，个别探讨的都是有序树）
  • 无序树：不思考子树的程序
  • m叉树：树中所有结点的最大度为m的有序树
  • 森林：m（m>=0）棵互不相交的树的汇合

二叉树

  • 每个结点的度均不超过2的有序树，称为二叉树（binary tree）
  • 二叉树或者是一棵空树，或者是由一个根结点和两个互不相交的左子树和右子树组成的非空树

满二叉树

  • 高度为k并且有$2^k+1$ 个结点的二叉树
  • 满二叉树中每层都达到最大数，即每层结点都是满的

齐全二叉树

  • 在一棵满二叉树中，从最上层最右侧起，去掉相邻的若干叶子节点，失去的即为齐全二叉树
  • 满二叉树肯定是齐全二叉树，而齐全二叉树不肯定是满二叉树

二叉树的性质

  1. 在二叉树的第i层上，最多有$2^(n-1)$个结点（根是第1层）
  2. 高度为h的二叉数至少有$2^h$-1个结点
  3. 对于任意一棵二叉树，叶子节点数 = 度为2的结点数 + 1
  4. 有n个结点的齐全二叉树的高度为$log_2^n$+1，其中$log_2^n$是向下取整
  5. 含有n>=1个结点的二叉树高度至少为n-1；高度至多为$log_2^n$+1，其中$log_2^n$是向下取整

  6. 如果对一棵含有n个结点的齐全二叉树的结点进行编号，则对任意结点i

    1. 如果i=1，则结点i是二叉树的根；如果i>1，则其双亲结点为i/2向下取整
    2. 如果2i>n,则结点i无左孩子；否则其左孩子为2i
    3. 如果2i+1>n，则结点i无右孩子；否则其右孩子为2i+1

二叉树的存储构造

二叉树的存储构造有两种：顺序存储构造和链式存储构造

顺序存储构造

  • 对于满二叉树和齐全二叉树来说，能够将其存储在一组间断的存储单元中
  • 用一维数组来实现顺序存储构造时，将二叉树第i个结点寄存到数组中第i个重量中
  • 依据二叉树的性质，能够失去结点i的父结点、左右孩子结点别离寄存在i/2、2i、2i+1重量中
  • 这种存储形式对于满二叉树和齐全二叉树是十分适合并且高效不便的，因为满二叉树和齐全二叉树采纳顺序存储构造即不节约空间，也能依据公式很快确定结点之间的关系
  • 然而对于个别的二叉树而言，必须用“虚结点”将一棵二叉树补成一棵齐全二叉树来存储，否则无奈确定结点之间的前驱后继关系，然而这样就会造成空间的节约

链式存储构造

  • 设计不同的节点构造可形成不同的链式存储构造
  • 在二叉树中，每个结点都有两个孩子，则能够设计成每个结点至多蕴含3个域：数据域、左孩子域、右孩子域
  • 利用此构造失去的二叉树存储构造称为二叉链表。数据域存放数据元素，左孩子域寄存指向左孩子结点的指针，右孩子域寄存指向右孩子的指针
  • 为了不便找到父结点，能够在上述结点构造中增加一个指针域，指向结点的父结点，采纳此构造失去的存储构造称为三叉链表