树的基本概念与二叉树

树的基本概念与二叉树

一、树的概念和结构

1. 树的概念

树是一种非线性的数据结构,它是由 n (n≥0) 个有限结点组成一个具有层次关系的集合。之所以称之为"树",是因为它的结构看起来像一棵倒挂的树,根朝上,叶子朝下。树具有以下特点:

• 有一个特殊的节点,称为根节点,根节点没有前驱节点。
• 除根节点外,其余节点被分成 M 个 (M>0) 互不相交的集合。
• 树是递归定义的。
• 在树形结构中,子树之间不能有交集,否则就不是树形结构。

2. 树的相关概念

• 节点的度: 一个节点含有的子树的个数称为该节点的度。
• 叶节点或终端节点: 度为 0 的节点称为叶节点。
• 非终端节点或分支节点: 度不为 0 的节点。
• 双亲节点或父节点: 若一个节点含有子节点,则这个节点称为其子节点的父节点。
• 孩子节点或子节点: 一个节点含有的子树的根节点称为该节点的子节点。
• 兄弟节点: 具有相同父节点的节点互称为兄弟节点。
• 树的度: 一棵树中,最大的节点的度称为树的度。
• 节点的层次: 从根节点开始定义,根为第一层,根的子节点为第二层,以此类推。
• 树的高度或深度: 树中节点的最大层次。
• 堂兄弟节点: 双亲在同一层的节点互为堂兄弟。
• 节点的祖先: 从根到该节点所经分支上的所有节点。
• 子孙: 以某节点为根的子树中任一节点都称为该节点的子孙。
• 森林: 由 m (m>0) 棵互不相交的树的集合称为森林。

需要注意的是:

• 当树为空树时,树的高度/深度通常设为 0。
• 子树之间是不能相交的。
• 除了根节点外,每个节点有且仅有一个父节点。
• 一棵拥有 N 个节点的树有 N-1 条边。

二、树的存储

1. 左孩子右兄弟表示法

左孩子右兄弟表示法是树形结构的一种常见且最优的存储方式。其结点结构如下:

struct TreeNode {
    int val;
    struct TreeNode* firstChild;    // 指向最左边的第一个孩子结点
    struct TreeNode* nextSibling;   // 指向当前节点右边一个兄弟结点
};
1
2
3
4
5

• firstChild: 指向最左边的第一个孩子结点,如果没有则指向 null。
• nextSibling: 指向当前节点右边的一个兄弟节点,如果没有则指向 null。

2. 双亲表示法

双亲表示法不存储指向孩子的指针,只存储指向父亲的指针或下标。

• 不支持从根找孩子,只支持从孩子找父亲。
• 判断两个节点是否在同一棵树中,可以通过寻找它们的根节点是否相同来确定。
• 并查集就是使用双亲表示法实现的。
• 根节点没有父亲,所以通常存储 -1。

三、二叉树

二叉树是一种特殊的树形结构,它实行了"计划生育",每个节点最多只能有两个孩子。二叉树具有以下特点:

• 二叉树中不存在度大于 2 的节点,每个节点最多有两个孩子,也可以只有一个孩子或没有孩子。
• 二叉树由一个根节点以及两棵分别称为左子树和右子树的二叉树组成。
• 二叉树的子树有左右之分,次序不能颠倒,因此二叉树是有序树。
• 二叉树有多种情况:空树、只有根节点、只有左子树、只有右子树以及左右子树都存在。

1. 特殊的二叉树

1.1 满二叉树

满二叉树是指一棵二叉树的每一层节点数都达到最大值。对于一棵高度为 h 的满二叉树,它一共有 (2^h)-1 个节点。证明如下:

设 F(h) 表示高度为 h 的满二叉树的节点总数,则有:
F(h) = 2^0 + 2^1 + 2^2 + ... + 2^(h-2) + 2^(h-1)

这是一个等比数列,其前 n 项和公式为:
Sn = (a1 * (1 - q^n)) / (1 - q)

代入 a1 = 1, q = 2, n = h,得:
F(h) = (2^h) - 1

另一种证明方法是错位相减法:

• `2F(h) = 2^1 + 2^2 + 2^3 + … + 2^(h-1) + 2^h
• F(h) = 2^0 + 2^1 + 2^2 + ... + 2^(h-2) + 2^(h-1)
F(h) = 2^h - 2^0 = 2^h - 1

1.2 完全二叉树

完全二叉树是由满二叉树引出来的,其效率很高。满二叉树是完全二叉树的一种特殊情况。

假设二叉树的高度为 h,则完全二叉树满足以下条件:

• 前 h-1 层都是满的。
• 第 h 层不一定满,但第 h 层的节点从左到右是连续的。

对于高度为 h 的完全二叉树,其节点数的范围是 [2^(h-1), 2^h - 1]。

以上就是对树的基本概念以及二叉树的介绍。树是一种非常重要且常用的数据结构,在计算机科学领域有着广泛的应用。深入理解树的概念和特性,对于解决实际问题和优化算法设计都有很大帮助。