未央的技术岛

二叉树的基本概念

概述

数据结构中的树有很多种，但是最常见的几种本质都是二叉树，比如说：红黑树、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执行的效果会是这样：

示例二叉树

总结

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

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