1. 树的概念及结构

树的概念

树是一种非线性的数据结构,与之相对的是顺序表、链表、栈和队列等线性的数据结构。它由n(n >= 0)个有限节点组成一个具有层次关系的集合。之所以被称为树是因为它的结构像一棵倒挂的树,也就是根朝上,而叶朝下。它具有以下特点:每个非根节点有且只有一个父节点,而每个节点有零个或多个子节点;没有父节点的节点称为根节点;除了根节点外,没个字节点可以分为多个不相交的树。

注意,树中的每个节点的左右子树都符合树的性质,也就是说树的定义是递归的,根节点是一棵树,根的左节点或者右节点又分别构成了不同的树。这一性质很重要,隐含着相当多的关于树的问题都可以通过递归来解决。

2. 与树相关的术语

  • 节点的度:一个节点含有的子节点的个数称为该节点的度。
  • 叶子节点:度为0的节点被称为叶子节点。
  • 双亲节点/父节点:若一个节点含有子节点,则这个节点是它的子节点的双亲结点/父节点。
  • 孩子节点/子节点:一个节点的子树的根节点称为这个节点的孩子节点/子节点。
  • 兄弟节点:拥有相同的双亲节点的节点互为兄弟节点。
  • 树的度:一棵树中,最大的节点的度称为这棵树的度。
  • 节点的层次:从根开始算起,根为第1层,根节点的子节点称为第2层,以此类推。
  • 树的高度/深度:树中节点的最大的层次称为树的高度/深度。
  • 堂兄弟节点:双亲在同一层的节点互为堂兄弟。
  • 节点的祖先:从根节点到该节点所经路径上所有的节点都是该节点的祖先。
  • 子孙:以某节点为根的子树中任一节点都称为该节点的子孙。
  • 森林:由m(m >= 0)棵不相交的树的集合称为森林。

3. 树的表示

树有多种表示方法:

  • 双亲表示法
  • 孩子表示法:只有指向孩子的指针,最常用。
  • 孩子兄弟表示法:既有指向孩子的指针,还有指向兄弟的指针。

4. 二叉树

二叉树是一棵树,但其中的每个节点的度都不会超过2,即最多只会有左右孩子。

而且二叉树是一棵有序树,即孩子之间是有顺序的,不能颠倒。

5. 完全二叉树与满二叉树

  • 满二叉树:如果一棵树的每层的节点数目都达到了最大值,则称之为满二叉树。
  • 完全二叉树:假设一棵树有n个节点,而这n个节点与同层的满二叉树的前n个节点的位置完全相同,则称这棵树为完全二叉树。

6. 二叉树的存储

二叉树有两种最常见的存储方式,顺序存储与链式存储。

顺序存储即存储在数组里,一般这种存储方式只适合于完全二叉树的存储。

链式结构即用指针来存储节点间的对应关系,常见的链式存储的二叉树的节点结构如下:

struct BTreeNode {
    int val;
    struct BTreeNode* left;
    struct BTreeNode* right;
}

7. 二叉树的性质

  1. 对于一棵完全二叉树,从根节点开始按层编号,根节点为0号,以此类推。则一个编号为 i 的节点的两个子节点的编号为 i 2 + 1 和 i 2 + 2 。
  2. 接上条,一个编号为 i 的节点的双亲结点的编号为 (i - 1) / 2
  3. 若规定根节点的层数为1,则第 i 层最多有 $ 2^{i-1} $ 个节点
  4. 若规定根节点的层数为1,则高度为 i 的二叉树最多有 $ 2^{i}-1 $ 个节点
  5. 具有n个节点的完全二叉树的深度k为 $ log_2 (n+1) $
  6. 对于任意一棵二叉树,如果其叶节点的个数为 $ n_{0} $,度为2的节点的个数为 $ n_{2} $,则有$ n_{0} = n_{2} + 1 $
Last modification:November 28th, 2021 at 08:12 pm