7.1 二叉树
非线性数据结构
与链表类似,二叉树的基本单元是节点,每个节点包含值、左子节点引用和右子节点引用。
malloc
是C语言标准库中的一个函数,用于动态分配内存。它的全称是“memory allocation”(内存分配)。malloc
函数在运行时从堆(heap)中分配指定大小的内存块,并返回一个指向该内存块的指针。
/* 二叉树节点结构体 */
typedef struct TreeNode {
int val; // 节点值
int height; // 节点高度
struct TreeNode *left; // 左子节点指针
struct TreeNode *right; // 右子节点指针
} TreeNode;
/* 构造函数 */
TreeNode *newTreeNode(int val) {
TreeNode *node;
node = (TreeNode *)malloc(sizeof(TreeNode));
node->val = val;
node->height = 0;
node->left = NULL;
node->right = NULL;
return node;
}
在二叉树中,除叶节点外,其他所有节点都包含子节点和非空子树。
7.1.1 二叉树常见术语
- 根节点(root node):位于二叉树顶层的节点,没有父节点。
- 叶节点(leaf node):没有子节点的节点,其两个指针均指向
None
。 - 边(edge):连接两个节点的线段,即节点引用(指针)。
- 节点所在的层(level):从顶至底递增,根节点所在层为 1 。
- 节点的度(degree):节点的子节点的数量。在二叉树中,度的取值范围是 0、1、2 。
- 二叉树的高度(height):从根节点到最远叶节点所经过的边的数量。
- 节点的深度(depth):从根节点到该节点所经过的边的数量。
- 节点的高度(height):从距离该节点最远的叶节点到该节点所经过的边的数量。
根节点到叶节点之间的边的数量可以看作是根节点到叶节点的“距离”。每个叶节点到根节点之间的边的数量可能不同,而边数量最多的叶节点,就是“最远叶节点”。
通常将“高度”和“深度”定义为“经过的边的数量”,但有些题目或教材可能会将其定义为“经过的节点的数量”。在这种情况下,高度和深度都需要加 1 。
7.1.2 二叉树基本操作
1. 初始化二叉树
首先初始化节点,然后构建引用(指针)。
/* 初始化二叉树 */
// 初始化节点
TreeNode *n1 = newTreeNode(1);
TreeNode *n2 = newTreeNode(2);
TreeNode *n3 = newTreeNode(3);
TreeNode *n4 = newTreeNode(4);
TreeNode *n5 = newTreeNode(5);
// 构建节点之间的引用(指针)
n1->left = n2;
n1->right = n3;
n2->left = n4;
n2->right = n5;
2. 插入与删除节点
在二叉树中插入与删除节点可以通过修改指针来实现。
/* 插入与删除节点 */
TreeNode *P = newTreeNode(0);
// 在 n1 -> n2 中间插入节点 P
n1->left = P;
P->left = n2;
// 删除节点 P
n1->left = n2;
需要注意的是,插入节点可能会改变二叉树的原有逻辑结构,而删除节点通常意味着删除该节点及其所有子树。因此,在二叉树中,插入与删除通常是由一套操作配合完成的,以实现有实际意义的操作。
7.1.3 常见二叉树类型
1. 完美二叉树
叶节点的度为 0 ,其余所有节点的度都为 2 ;若树的高度为 ℎ ,则节点总数为 \(2^{ℎ+1}−1\)
2. 完全二叉树
只有最底层的节点未被填满,且最底层节点尽量靠左填充。
3. 完满二叉树
除了叶节点之外,其余所有节点都有两个子节点。
4. 平衡二叉树
任意节点的左子树和右子树的高度之差的绝对值不超过 1 。
7.1.4 二叉树的退化
当二叉树的每层节点都被填满时,达到“完美二叉树”;而当所有节点都偏向一侧时,二叉树退化为“链表”。
- 完美二叉树是理想情况,可以充分发挥二叉树“分治”的优势。
- 链表则是另一个极端,各项操作都变为线性操作,时间复杂度退化至 𝑂(𝑛)