二叉树（Binary Tree）

[TOC]

#### 一、二叉树（Binary Tree）的简介

在计算机科学中，二叉树是一种树形的数据结构，其中每个节点最多具有两个子节点，其被称为左子节点和右子节点。仅使用集合理论概念的递归定义是（非空）二叉树是一个元组（L，S，R），其中L和R是二叉树或空集，S是单例集合。

树中的常见术语包括：

- 某个节点的深度是指当前节点到根节点的边的个数
- 某个节点的高度是指当前节点到最深的叶子节点的边的个数
- 树的高度是指根节点的高度

树结构的优点包括：
- 反应了数据的关系
- 具有层次结构表达能力
- 高效的插入和搜索
- 灵活的数据结构，允许以较小的代价移动子树

如下图所示就是一个二叉树：

<center>![](https://upload.wikimedia.org/wikipedia/commons/thumb/f/f7/Binary_tree.svg/1200px-Binary_tree.svg.png)

</center>

在计算机领域，二叉树有两个主要的用途：

第一个用途是用来实现二叉查找树和二进制堆，以便于搜索和排序。

第二个用途是作为具有相关分叉的数据表示。例如霍夫曼编码（Huffman coding）和分支图（Cladograms）。

注意二叉树并不是<font color=red>一种</font>数据结构，它是<font color=red>一类</font>数据结构。在二叉树数据结构中，不平衡的树比自平衡树的效率低很多。平衡与否取决于左右两个子树的高度差的绝对值。绝对值小于1的一般可以理解为平衡树，否则是不平衡树。

#### 二、二叉树（Binary Tree）的分类

##### 满二叉树（Full Binary Tree）
如果一个二叉树的每一个节点数都是最大节点数，那么它就是满二叉树。如下图：

<center>![](http://web.cecs.pdx.edu/~sheard/course/Cs163/Graphics/FullBinary.jpg)</center>

##### 完全二叉树（Complete Binary Tree）
如果一个二叉树除了最后一层外的每一个节点数都是最大节点数，那么它就是完全二叉树。如下图：

<center>![](https://i.imgur.com/9qQDXVV.png)</center>

##### 二叉树的性质
满二叉树的节点数是$2^k-1$
完全二叉树的节点数$2^{h-1} \leq k < 2^h-1$

#### 三、二叉树（Binary Tree）的应用
二叉树是一种非常基础的数据结构，它和它的变种有很多的应用。这里列举一些：

- [二叉查找树（Binary Search Tree）](https://www.datalearner.com/blog/1051540195789273)：二叉查找树是一种具有高效查找效率的树形结构，在搜索中应用非常广泛。
- 霍夫曼编码树（Huffman Coding Tree）：这压缩算法中应用广泛，例如JPEG和MP3格式的文件压缩。

二叉树（Binary Tree）

欢迎大家关注DataLearner官方微信，接受最新的AI技术推送

相关博客

最热博客