概述
数据结构中的树有很多种,但是最常见的几种本质都是二叉树,比如说:红黑树、B树等。
二叉树因为每个结点只有两个分支,因此构造起来容易,使用起来方便。
二叉树具有以下规律:
- 第i层最多结点数为
2^(i-1)
个 - 深度为k的二叉树最多结点数为
2^k-1
个 - 记叶子数为n0,分支度为2的结点数为n2,则
n0=n2+1
结点的定义
一个结点具有自己的值,同时又指向自己的左结点和右结点。
对于值为int
类型的结点,C的定义方式可以如下。
ctypedef struct _node
{
int val;
struct _node *left, *rigt;
} node;
用数组构造一棵平衡二叉树
平衡二叉树是二叉树中较为实用的一种,它的任意结点的子树的高度差都小于或等于1。
用数组构造平衡二叉树的方式可能比较多,如下是依顺序逐层构造二叉树的C实现。
c#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
是数组长度。
构造一棵平衡二叉搜索树
如果稍加调整,就可以构造一棵平衡二叉搜索树。
cvoid 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实现。
cnode *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代码。
c#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
执行的效果会是这样:
总结
树是链表的延伸,是一种比链表复杂的数据结构。而二叉树是树里面常用的一种,具有许多用途,诸如搜索。
学习构建二叉树是第一步,然后才能探索其更广阔的用途。
评论
发表评论