二叉树

〇、返回

返回传送门

一、二叉树的基本定义

二叉树（Binary Tree）是由n（n≥0）个有限节点组成的一个具有层次关系的集合。它具有以下特点：

    每个节点最多只有两棵子树（即二叉树不存在度大于2的节点）。

    二叉树的子树有左右之分，次序不能颠倒（因为这是有序树）。

二、二叉树的基本术语

节点

树中的一个独立单元，包含一个数据元素及若干指向其子树的分支。

根节点

一棵树中唯一一个没有父节点的节点。

叶子节点

没有子节点的节点。

父节点

如果有向边A->B，则称A为B的父节点。

子节点

如果有向边A->B，则称B为A的子节点。

兄弟节点

具有同一父节点的各节点彼此是兄弟节点。

路径和路径长度

从节点n1到nk的路径为一个节点序列n1, n2, ..., nk，ni是ni+1的父节点。路径所包含边的个数为路径的长度。

节点的度

节点拥有的子树个数称为节点的度。

树的度

树内各节点的度的最大值。

深度

节点的深度是从根节点到该节点的唯一路径上的边的数量。

高度

节点的高度是从该节点到一棵最深的子树上的叶子节点的唯一路径上的边的数量。

三、二叉树的性质

1. 在二叉树的第i层上至多有$2^{i-1}$个节点（i≥1）。

2. 深度为k的二叉树至多有$2^k - 1$个节点（k≥1）。

3. 对于任何一棵二叉树T，如果其终端节点数（叶子节点数）为n0，度为2的节点数为n2，则n0 = n2 + 1。

4. 具有n个节点的完全二叉树的深度为$\lfloor \log_2 n \rfloor + 1$。

5. 在满二叉树中，具有n个节点的满二叉树的深度为$\lfloor \log_2 n \rfloor + 1$且该深度上叶子节点数达到最大值。

四、二叉树的存储结构

二叉树的存储结构主要有两种：顺序存储结构和链式存储结构。

顺序存储结构

用一组连续的存储单元来存储二叉树的数据元素。

链式存储结构

用链表来表示二叉树的存储结构称为二叉链表。在二叉链表中，每个结点由三个域组成，数据域和左右指针域。

五、二叉树的遍历

二叉树的遍历是指从根节点出发，按照某种次序访问二叉树中的所有节点，使得每个节点被访问一次且仅被访问一次。

前序遍历

先访问根节点，然后遍历左子树，最后遍历右子树。

中序遍历

先遍历左子树，然后访问根节点，最后遍历右子树。

后序遍历

先遍历左子树，然后遍历右子树，最后访问根节点。

层次遍历

从树的根节点开始，从上到下逐层遍历，在同一层中，按从左到右的顺序进行。

六、二叉树的应用

二叉树在计算机科学中有广泛的应用，例如：

二叉搜索树（BST）

一种动态查找表，支持高效的插入、删除和查找操作。

堆（Heap）

一种特殊的完全二叉树，分为最大堆和最小堆，常用于实现优先队列。

哈夫曼树

用于数据压缩的编码算法。

表达式树

用于表示算术表达式或逻辑表达式。

七、二叉树的构建

构建二叉树通常可以通过给定的遍历序列来实现。例如，给定一棵二叉树的前序遍历和中序遍历序列，可以唯一确定这棵二叉树。

八、总结

二叉树作为一种重要的数据结构，在算法设计和数据处理中扮演着关键角色。理解二叉树的定义、性质、存储结构和遍历方法，对于解决实际问题具有重要意义。