C++(数据结构与算法):34---树的介绍及树的各种术语_c++树的分类

一、树

• 树状图是一种数据结构，它是由n（n>=1）个有限结点组成一个具有层次关系的集合。把它叫做“树”是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的

二、树的种类

• 按功能：
  • 一般树（简单树）、二叉树
  • 堆（heap）、左高树（leftist tree）、竞标赛树、二叉搜索树、AVL树、红黑树、伸展树、B树
  • 配对堆、区间堆、双端优先级队列的树结构、字典树（也称前缀数、单词查找树、键树）、后缀树等等......
• 按顺序：
  • 有序树：树中的节点，其子树从左至右是有次序的（不能互换），例如二叉树
  • 无序数：树中的节点，其子树从左至右是无次序的（可以互换），例如普通树

三、树的术语、名词

• 以上图为例：
  • 根：一棵树t是一个非空的有限元素的集合，其中最顶级的元素称为根。Joe就是根
  • 子树：一个树除了根节点之外，其余的称为子树。除了Joe节点之外，其余节点全是子树
  • 孩子：Ann、John是Joe的孩子、Mark是Mary的孩子，以此类推...
  • 父母：Mary是Mark、Sue节点的父母，以此类推...
  • 兄弟：Sue是Mark的兄弟，Ann是John的兄弟，以此类推...
  • 孙子、祖父、祖先、后代：Mark是Joe的孙子，其他名次以此类推...
  • 叶子：树种没有孩子的元素称为叶子，例如Ann、Mark、Sue等
• 另一些术语：
  • 备注：有的术语中级数/深度/高度会以0开始计算
  • 节点的级数/层数：树根是1级（Joe节点），Ann、Mary、John节点是2级、Mark节点等是3级，以此类推...
  • 深度（从上到下）：
    • 节点的深度：树根的深度1，Ann、Mary、John节点的深度2，Mark节点的深度3，以此类推...
    • 树的深度：是指树深度的最大数，例如本图中，树的深度为3
  • 高度（从下到上）：
    • 节点的高度：从最底部的叶节点开始计算，每增一层高度加1。例如Ann、Mark、Sue、Chris的高度为1，Mary、John的高度为2，Joe的高度为3
    • 树的高度：高度最高的节点值，也就是根节点的高度。此图中的树的高度为3
  • 节点的度：是指其孩子的个数。例如Joe的度为3、Ann的度为0，以此类推...
    • 度为0的节点称为叶节点或终端节点
    • 度不为0的节点称为分支节点或非终端节点
  • 树的度：是指树种最大节点的那个度。例如本图中，树的度为3，因为树种最大的度节点为Joe，其度为3

四、二叉树

• 定义：一棵二叉树t是有限个元素的集合（可以为空）。当二叉树非空时，其中有一个元素称为根，余下的元素被划分为两颗二叉树，分别称为t的左子树和右子树
• 二叉树与数的根本区别：
  • 1.二叉树的每个元素都恰好有两颗子树（其中一个或两个可能为空）。而树的每个元素可有任意数量的子树
  • 2.在二叉树中，每个元素的子树都是有序的，也就是所，有左子树和右子树之分。而树的子树是无序的

图例

• 本图中展示的就是二叉树，此二叉树用于表示算术表达式
• 算术表达式树的一个应用是生成优化的计算机代码以计算表达式的值

五、二叉树的特性

特性①

• 一棵二叉树有n个元素，n>0，则其有n-1条边
• 证明：二叉树的每个元素（除了根节点）有且只有一个父节点。在子节点与父节点间有且只有一条边，因此边数为n-1

特性②

• 一棵二叉树的高度为h，h>=0，它最少有h个元素，最多有$2^{h}-1$个元素
• 证明：因为每一级最少有1个元素，因此元素的个数最少为h。每个元素最多有2个子节点，则第i层节点做多为$2^{i}-1$个，i>0.当h=0时，元素的总数为0，也就是$2^{0}-1$。当h>0时，元素的总数不会超过

特性③

• 一棵二叉树有n个元素，n>0，它的高度最大为n，最小高度为[$\log (n+1)$]
• 证明：因为每层至少有一个元素，因此高度不会超过n。有特性②可以知道，高度为h的二叉树做多有$2^{h}-1$个元素。因此n<=$2^{h}-1$，所以h>=$\log_{2}(n+1)$。由于h是整数，所以h>=[$\log (n+1)$]

特性④

• 这个特性是属于完全二叉树的
• 设完全二叉树的一个元素其编号为i，1<=i<=n，则由以下关系：
  • 1.如果i=1，则该元素为二叉树的根。若i>1，则其父节点的编号为i/2
  • 2.如果2i>n，则元素无左孩子。否则，其左孩子的编号为2i
  • 3.如果2i+1>n，则该元素无右孩子。否则， 其右孩子的编号为2i+1

六、满二叉树

• 定义：当高度为h的二叉树恰好有$2^{h}-1$个元素时，称其为满二叉树
• 特点：
  • 第i层上的节点数必为$2^{i-1}$个
  • 高度为h的二叉树恰好有$2^{h}-1$个元素
  • 满二叉树不存在度为1的节点
• 例如下面的a是一个高度为3的满二叉树、b和c不是

七、完全二叉树

• 定义：对高度为h的满二叉树的元素，从第一层到最后一层，在每一次中从左至右，顺序编号，从1到$2^{h}-1$。假设从满二叉树中删除k个其编号为$2^{h}-i$元素，1<=i<=k<$2^{h}$，所得到的的二叉树被称为完全二叉树
• 设完全二叉树的一个元素其编号为i，1<=i<=n，则由以下关系：
  • 1.如果i=1，则该元素为二叉树的根。若i>1，则其父节点的编号为i/2
  • 2.如果2i>n，则元素无左孩子。否则，其左孩子的编号为2i
  • 3.如果2i+1>n，则该元素无右孩子。否则， 其右孩子的编号为2i+1
• 满二叉树是完全二叉树的一个特例
• 下面是3颗完全二叉树

八、森林

• 树是n（n>=0）个节点的集合；森林是m（m>=0）课互不相交的树的集合
• 例如：

树和森林的转换

• 树转换为森林：把树的根节点删除，那么剩余的所有子树就组成了一棵森林
• 森林转换为树：如果把所有的森林赋值一个相同的根节点，那么这些森林就会重新组织成一棵树