二叉树是一棵树,其中每个结点都不能有多于两个的儿子。对于一种特殊类型的二叉树,即二叉查找树。对于二叉查找树,若其左子树不为空,则左子树上的所有值小于根节点;若其右子树不为空,则其右子树上所有的结点都大于根节点,且其左右子树都是二叉查找树,以此递归,即可得出二叉查找树。
以下介绍二叉搜索树的C语言代码实现,代码链接。
0 树
定义:一棵树是一些节点的集合。这个集合可以是空集;若非空,则一棵树由称作根(root)的节点r以及0个或者多个非空的(子)树T1、T2……组成,这些子树中每一棵的根都被来自根r的一条有向的边(edge)所连接。
每一个子树的根是根r的儿子,而r是每一棵子树的根的父亲。
没有儿子的节点称为树叶(或称外部节点,同理,非叶节点称内部节点),具有相同父亲的节点称为兄弟,用类似的方法可以定义祖父和孙子。
树某节点的孩子数目称为该节点的度(自由树节点的度和无向图一样,是相邻顶点的个数,有根树中,指的是孩子的个数)。
从根节点到某节点的一条简单路径的长度即为该节点的深度。某节点到一片树叶最长路径称为高。因此,根节点的深度为0。一棵树的高等于其根节点的高;一棵树的深度等于其最深树叶的深度,该深度等于这棵树的高。
考虑以r为根的树T中一个节点x,从r到x的唯一简单路径上任意节点y称为x的祖先,x称为y的后代,如果x≠y,则y是x的真祖先,x是y的真后代。
1 二叉搜索树
1.1 结构实现
因为二叉搜索树每个节点至多拥有两个儿子,所以我们可以用指针指向它们。可以定义其结构如下:
1 | typedef int myElement; |
1.2 插入(创建)
插入操作是将值插入到二叉搜索树中,针对空树,其插入操作也是创建一个二叉搜索树,代码如下:
- 针对空树,我们将节点数据插入,作为该子树root的值,并指定左右节点为NULL;
- 非空树,当插入数据小于该数节点数据时,递归调用插入左子树;
- 非空树,当插入数据大于该数节点数据时,递归调用插入右子树;
- 非空树,当插入数据等于该节点数据时,不做任何处理。
1 | searchTree_t *search_tree_insert(myElement x, searchTree_t *T) |
1.3 删除树
删除树指删除整个树的所有节点数据,并非单独的某个节点,代码如下:
- 若树为空,无需任何操作;
- 树不为空,将树的左右儿子均值为NULL,并释放该树节点资源;
- 递归调用本函数分别再删除左右子树。
1 | void destroy_search_tree(searchTree_t *T) |
1.4 查找
二叉树最重要的应用就是他在查找中的作用。使二叉树称为二叉搜索树的一个重要的原因是对于树中的每个节点X,其左子树中所有的关键字值小于X的关键字值,其右子树中的所有关键字值大于X的关键字值。
对于特定的值的查找,其代码如下:
- 若该节点为孔,则返回空;
- 该节点不为空,若寻找的值为该节点的关键字值,则返回该节点;
- 该节点不为空,若寻找的值小于该节点的关键字值,则递归查找其左子树中该特定值的查找;
- 该节点不为空,若寻找的值大于该节点的关键字值,则递归查找其右子树中该特定值的查找;
1 | searchTreePos_t *search_tree_search(searchTree_t *T, myElement k) |
特殊的,寻找最大值和最小值代码如下,这里没有用递归,用的是迭代的方式,通常效率比递归要高。
1 |
|
1.5 删除节点
删除节点是二叉树操作中比较复杂的操作,基本可以按照以下理解。
- 当该节点没有儿子,即为树叶时,直接删除该节点即可;
- 当该节点只有一个儿子时,直接用该孩子节点替换该节点即可;
- 当该节点有两个儿子时,用其右子树最小节点数据代替该节点数据,并删除那个最小节点。而右子树的最小节点不可能有左儿子,所以删除右子树只会出现以上1、2两种情况。
代码实现如下所示:
1 | searchTreePos_t *delete_get_min(searchTree_t **T) |
1.6 遍历
1.6.1 中序遍历
- 中序遍历:子根树关键字在其左子树关键字和右子树关键字之间;
- 先序遍历:子根树关键字在左右子树关键字之前,例如一般的目录列表;
- 后续遍历:子根树关键字在左右子树关键字之后;
由于二叉搜索树的特殊性质,其中序遍历必然是递增的,所以我们这里只介绍中序遍历,其代码如下:
1 | // 中序遍历 |
1.6.2 BFS搜索
即从上至下打印二叉树,利用队列的特性,分层从左至右将节点压入队列中,并从队列中取出数据打印。
1 | void BFS(searchTree_t *T) |
1.7 反转二叉树
这个问题是受到Max Howell
的原问题启发的:
1 | 谷歌:我们90%的工程师使用您编写的软件(Homebrew),但是您却无法在面试时在白板上写出翻转二叉树这道题,这太糟糕了。 |
以上,足以说明现代互联网公司一味地八股取士有多荒谬了!
翻转二叉树也是用递归实现的,其代码如下,需要注意的是,翻转后的二叉树不再是搜索二叉树,所以以上介绍的许多搜索二叉树性质的函数都不再适用于翻转后的二叉树。
1 | // 翻转二叉树 |
2 小结
二叉树的C语言实现基本如上,二叉树实现最重要的性质就是使用递归(或者使用迭代)。