未央的技术岛

二叉树的基本概念

概述

数据结构中的树有很多种,但是最常见的几种本质都是二叉树,比如说:红黑树、B树等。

二叉树因为每个结点只有两个分支,因此构造起来容易,使用起来方便。

二叉树具有以下规律:

  1. 第i层最多结点数为2^(i-1)
  2. 深度为k的二叉树最多结点数为2^k-1
  3. 记叶子数为n0,分支度为2的结点数为n2,则n0=n2+1

结点的定义

一个结点具有自己的值,同时又指向自己的左结点和右结点。

对于值为int类型的结点,C的定义方式可以如下。

1
2
3
4
5
typedef struct _node
{
int val;
struct _node *left, *rigt;
} node;

用数组构造一棵平衡二叉树

平衡二叉树是二叉树中较为实用的一种,它的任意结点的子树的高度差都小于或等于1。

用数组构造平衡二叉树的方式可能比较多,如下是依顺序逐层构造二叉树的C实现。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#define MALLOC_NODE(tree_pp, value) \
*tree_pp = malloc(sizeof(node)); \
(*tree_pp)->val = value; \
(*tree_pp)->left = NULL; \
(*tree_pp)->rigt = NULL;

void insert_node(node **tree_pp, int arr[], unsigned i, unsigned n)
{
if (i >= n) return;

MALLOC_NODE(tree_pp, arr[i]);

insert_node(&(*tree_pp)->left, arr, 2*i+1, n);
insert_node(&(*tree_pp)->rigt, arr, 2*i+2, n);
}

参数解释,tree_pp是一个指向结点指针的指针,此参数也可重构为函数返回值;i是递归索引,从0开始;n是数组长度。

构造一棵平衡二叉搜索树

如果稍加调整,就可以构造一棵平衡二叉搜索树。

1
2
3
4
5
6
7
8
9
10
11
void insert_bst_node(node **tree_pp, int arr[], unsigned sta, unsigned end)
{
if (sta >= end) return;

unsigned mid = (sta + end) / 2;

MALLOC_NODE(tree_pp, arr[mid]);

insert_bst_node(&(*tree_pp)->left, arr, sta, mid);
insert_bst_node(&(*tree_pp)->rigt, arr, mid+1, end);
}

给定一个排序好的数组arr,我们将其中间值设为根结点。

然后递归地对其左半部分和右半部分进行类似操作,即可得到一棵平衡二叉搜索树。

注意,当使用完一棵树后,应该递归调用free释放内存。

二叉搜索树的搜索

二叉搜索树的搜索效率较高,最坏时间复杂度为O(h),其中h是树的高度。

以下是可能的C实现。

1
2
3
4
5
6
7
8
9
node *search_bst_tree(node *tree_p, int val)
{
node *node_p = tree_p;
while (node_p != NULL && val != node_p->val)
{
node_p = val < node_p->val ? node_p->left : node_p->rigt;
}
return node_p;
}

二叉树的遍历

二叉树有许多遍历方式,可以如下分类:

  • 深度优先
    • 前序遍历
    • 中序遍历
    • 后序遍历
  • 广度优先

对于深度优先,可以递归遍历,或是使用栈来遍历。而广度优先则可以使用队列来遍历。

它们的时间复杂度和空间复杂度都是O(n),n是结点数。

后序遍历可以美观地打印出一棵树,比如说如下C代码。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#define INDENT_STEP 4

#define PUT_SPACE(count) \
for (size_t i = 0; i < count; i++) \
{ \
putchar(' '); \
}

#define PRINT_NODE(tree_p, indent) \
PUT_SPACE(indent) \
if (tree_p->rigt) \
{ \
puts(" /"); \
PUT_SPACE(indent) \
} \
printf("%d\n", tree_p->val); \
if (tree_p->left) \
{ \
PUT_SPACE(indent) \
puts(" \\"); \
}

void print_postorder_tree(node *tree_p, unsigned indent)
{
if (tree_p == NULL) return;

print_postorder_tree(tree_p->rigt, indent+INDENT_STEP);
PRINT_NODE(tree_p, indent)
print_postorder_tree(tree_p->left, indent+INDENT_STEP);
}

void print_tree(node *tree_p)
{
print_postorder_tree(tree_p, 0);
}

print_tree执行的效果会是这样:

示例二叉树

总结

树是链表的延伸,是一种比链表复杂的数据结构。而二叉树是树里面常用的一种,具有许多用途,诸如搜索。

学习构建二叉树是第一步,然后才能探索其更广阔的用途。