数据结构 · 树(二叉树)
1. 二叉树
1. 1 二叉树定义
在一棵普通树中,每个节点可以有任意数量的子节点,而二叉树是一种特殊类型的树数据结构。对于二叉树,每个节点可以有0个子节点,或1个或2个,但是不能超过2个(最多只能是2个子节点),一个被称为左子节点(左子树),另外一个称为右子节点(右子树)。它是一种非常有用的数据结构,广泛用于快速存储排序、快速检索排序等场景。许多高效的检索算法(如: 二分搜索数、红黑树)都是基于二叉树衍生而来。
二叉树的正式定义:
要么是空树(无节点),或者
由根节点(root)和一个分别称为左子树与右子树的节点组成。
根据二叉树的定义,可知其具有以下几种形态:
1. 2 二叉树图示法
二叉树的典型图示法表示本质上是一棵颠倒的树。从根(root)节点开始,对于根节点的左子树与右子树,它们又可以/可能有自己的子节点。理想情况下,树的结构应为一棵完美平衡的树,即每个节点的左边和右边均是相同数量的子节点,完美平衡的树允许以最快的平均速度插入数据或是检索数据。而最坏的情况是树中的每个节点只有一个子节点,对于这样的树,从速度、效率上来讲,犹如一个链表。
2. 二叉树性质
-
其双亲节点的编号为 i/2(1 < i <= n); -
其左子树节点的编号为 2i(1 <= i <= n/2); -
其右子树节点的编号为 2i + 1(1 <= i <= (n-1) / 2).
3. 二叉树分类
3. 1 退化二叉树(Degenerate Binary Tree)
所谓退化二叉树是指该二叉树中,每个节点只有一个子节点。这样的二叉树无论外形,还是性能方面,均类似于链表。如下图所示:
▲ 退化二叉树
3. 2 平衡二叉树(Balanced Binary Tree)
定义中指明“高度最多可相差一个。”为何不是高度相等?难道不应该要求零高度差来达到完美的平衡吗?” 让我们来看这样一个例子,对于简单的两节点的树,如下图:
▲ 两节点树形状
对于上图中的左图,左子树是单个节点,高度为1;右“子树”为空,因此高度是零。或对于右图,右子树是单节点,高度为1,而左“子树”为空,高度为0。对于这样的树,无法使其达到零高度差的完美平衡,除非另添加一个“假”节点(第3节点)。但是这样勉强的为了达到完美平衡而增加一个非真实有用的数据节点并不会让我们从中受益,此外,还会多耗费一个节点的内存空间。
像下面这样任何一个节点的两个子树高度差超过1的二叉树, 则不是平衡二叉树。
▲ 非平衡二叉树
3. 3 满二叉树(Perfect Binary Tree)
▲ 满二叉树
3. 4 完全二叉树(Complete Binary Tree)
▲ 完全二叉树
3. 5 全二叉树(Full Binary Tree)
即:一棵二叉树,其中每个节点有0个或两个子节点。
▲ 全二叉树
4. 二叉树遍历
「维基百科」对于树的遍历是这样定义的:
翻译:在计算机科学中,树遍历(也称为树搜索)是图形遍历的一种形式,指的是访问(检查和/或更新)树数据结构中的每个节点的过程,只访问一次。这种遍历是按照访问节点的顺序进行分类的。
-
深度优先搜索(DFS)算法
-
广度优先搜索(BFS)算法
4. 1 先序遍历(Preorder Traversal)
-
先访问根节点(root) -
访问根节点的左子树(Left-Tree) -
访问根节点的右子树(Right-Tree)
4. 2 中序遍历(Inorder Traversal)
二叉树的中序遍历按照以下三个流程:
-
先访问左子树(Left-Tree) -
接着访问根节点(root) -
最后访问根节点的右子树(Right-Tree)
▲ 中序遍历 - 此图来自 towardsdatascience.com
4. 3 后序遍历(Postorder Traversal)
-
先访问左子树(Left-Tree) -
接着访问右子树(Right-Tree) -
最后访问根节点(root)
▲ 后序遍历 - 此图来自 towardsdatascience.com
5. 二叉树存储
二叉树的表示与实现,同样有两种方式,分别是:动态节点表示(链表)、数组表示(顺序表示)。本节先详细讲解使用数组的顺序存储方式来实现二叉树的存取,下节再对二叉树的链表实现方式进行分析与探讨。
当用数组来实现二叉树时候,通常节点的编号(下标)从0 - (n - 1),或 1 - n 开始。如下图所示:
▲ 二叉树顺序存储(数组表示)
当节点编号从0开始时,存储到数组中的示意图如下:
当节点编号从1开始时,存储到数组中的示意图如下:
const char binary_tree[] = {'\0', 'A', 'B', 'C', 'D', 'E', '\0', 'F'};
'\0'
)情况。
int g_tree_node_num = 7;
/*
* fn: get_left_child_node
* desc: 获取node_index的左节点索引编号
* date: 2020/12/16/02:40:08
* author: lixiaogang5
* mail: [email protected]
*/
int get_left_child_node(const char *bin_tree, int node_index)
{
if('\0' != bin_tree[node_index] && (2 * node_index) <= g_tree_node_num)
{
return 2 * node_index;
}
return -1;
}
/*
* fn: get_right_child_node
* desc: 获取node_index的右节点索引编号
* date: 2020/12/16/02:41:57
* author: lixiaogang5
* mail: [email protected]
*/
int get_right_child_node(const char *bin_tree, int node_index)
{
if('\0' != bin_tree[node_index] && ((2 * node_index) + 1) <= g_tree_node_num)
{
return (2 * node_index) + 1;
}
return -1;
}
/*
* fn: preorder_traversal
* desc: 先序遍历
* date: 2020/12/16/02:54:13
* author: lixiaogang5
* mail: [email protected]
*/
void preorder_traversal(const char *bin_tree, int node_index)
{
//判断是否为空节点, 以及索引(编号)是否有效
if(node_index > 0 && '\0' != bin_tree[node_index])
{
//1. 打印根节点
printf("%c ", bin_tree[node_index]);
//2. 访问左子树
preorder_traversal(bin_tree, get_left_child_node(bin_tree, node_index));
//3. 访问右子树
preorder_traversal(bin_tree, get_right_child_node(bin_tree, node_index));
}
}
/*
* fn: inorder_traversal
* desc: 中序遍历
* date: 2020/12/16/03:00:10
* author: lixiaogang5
* mail: [email protected]
*/
void inorder_traversal(const char *bin_tree, int node_index)
{
//判断是否为空节点, 以及索引(编号)是否有效
if(node_index > 0 && '\0' != bin_tree[node_index])
{
//1. 访问左子树
inorder_traversal(bin_tree, get_left_child_node(bin_tree, node_index));
//2. 打印根节点
printf("%c ", bin_tree[node_index]);
//3. 访问右子树
inorder_traversal(bin_tree, get_right_child_node(bin_tree, node_index));
}
}
/*
* fn: postorder_traversal
* desc: 后序遍历
* date: 2020/12/16/03:05:10
* author: lixiaogang5
* mail: [email protected]
*/
void postorder_traversal(const char *bin_tree, int node_index)
{
//判断是否为空节点, 以及索引(编号)是否有效
if(node_index > 0 && '\0' != bin_tree[node_index])
{
//1. 访问左子树
postorder_traversal(bin_tree, get_left_child_node(bin_tree, node_index));
//2. 访问右子树
postorder_traversal(bin_tree, get_right_child_node(bin_tree, node_index));
//3. 打印根节点
printf("%c ", bin_tree[node_index]);
}
}
int main(int argc, char *argv[])
{
const char binary_tree[] = {'\0', 'A', 'B', 'C', 'D', 'E', '\0', 'F'};
//1. 先序遍历(binary_tree数组下标编号1为二叉树的根(root)节点.
const int node_index = 1;
puts("Preorder Traversal:");
preorder_traversal(binary_tree, node_index);
//2. 中序遍历
printf("\nPreorder Traversal:\n");
inorder_traversal(binary_tree, node_index);
//3. 后序遍历
printf("\nPostorder Traversal:\n");
postorder_traversal(binary_tree, node_index);
return 0;
}
打印结果: