二叉树的概念及面试题大全


1. 二叉树(Binary Tree)的定义

1.1 什么是二叉树(Binary Tree)

每个结点至多拥有两棵子树的树结构(即二叉树中不存在度大于2的结点)。并且,二叉树的子树有左右之分,其次序不能任意颠倒。

上面概念中提到了“度”的概念,“度”其实就是某个节点子节点的数量。如果某个节点的子节点数量为1,则该节点的度为1,如果有8个子节点,则度为8,以此类推。

1.2 二叉树的术语

除了二叉树的定义外,还有许多相关的术语。单纯介绍术语可能不容易理解,这里给出一幅图进行说明。
图1 二叉树的主要概念

下面是对二叉树中主要术语的解释:
结点的度(Degree):结点的子树个数;
树的度:树的所有结点中最大的度数;
叶结点(Leaf):度为0的结点;
父结点(Parent):有子树的结点是其子树的根节点的父结点;
子结点/孩子结点(Child):若A结点是B结点的父结点,则称B结点是A结点的子结点;
兄弟结点(Sibling):具有同一个父结点的各结点彼此是兄弟结点;
路径和路径长度:从结点n1到nk的路径为一个结点序列n1,n2,…,nk。ni是ni+1的父结点。路径所包含边的个数为路径的长度;
祖先结点(Ancestor):沿树根到某一结点路径上的所有结点都是这个结点的祖先结点;
子孙结点(Descendant):某一结点的子树中的所有结点是这个结点的子孙;
结点的层次(Level):规定根结点在1层,其他任一结点的层数是其父结点的层数加1;
树的深度(Depth):树中所有结点中的最大层次是这棵树的深度;

1.3 二叉树的性质

我们设定二叉树的根节点为为第1层,则二叉树有如下性质。这些性质可以通过数学方式进行证明,但本文暂时不做证明,大家了解即可,对于理解后续概念有一些帮助:
性质1:二叉树第i层上最多有 2^(i-1) 个结点(i≥1);
性质2:深度(高度)为k的二叉树至多有2^(k)-1个结点(k≥1,深度k也就是树的最大层级);
性质3:包含n个结点的二叉树的深度(高度)至少为log2 (n+1);
性质4:在任意一棵二叉树中,如果其叶子结点(度为0)数为m, 度为2的结点数为n, 则m = n + 1。

1.4 二叉树的数据存储

二叉树在C语言中可以通过结构体表示,其定义的方式可以是如下:

1
2
3
4
5
struct bitree_node {
int b_data; //数据域,指向具体的数据
struct bitree_node *left; //指向左子节点
struct bitree_node *right; //指向右子节点
};

在这个实例中,为了简单,我们假设其存储的数据类型为整型数,当然最好的方式是void指针的形式。这样,二叉树就是一个通用的数据结构,可以存储任何类型的数据。

图2 二叉树的数据存储

2. 二叉树的特例

根据二叉树存储数据组织结构的差异,二叉树有很多特例。比如有些二叉树所有节点只有左子节点,或者非叶子节点的每个二叉树的节点都有2个子节点等等。下面我们分别进行介绍。

2.1 斜二叉树

只有左子节点或只有右子节点的二叉树称为斜二叉树。
图3 斜二叉树

2.2 完美二叉树

一个深度为k(>=-1)且有2^(k+1) - 1个结点的二叉树称为完美二叉树。完美二叉树也就是满二叉树,也就是所有非叶子节点都有2个叶子节点,并且每一次都是满的。如图所示:
图4 完美二叉树

2.3 完全二叉树(Complete)

完全二叉树从根结点到倒数第二层满足完美二叉树,最后一层可以不完全填充,其叶子结点都靠左对齐。
下图就不是一棵完全(Complete)二叉树
图5 完全二叉树

3. 二叉树相关的算法(面试题)

在面试和笔试的过程中,二叉树的题目是非常多的。除了常见的关于二叉树遍历的题目外,还有其它一些延伸的题目。本文今天先将二叉树相关的题目罗列到这里,后续会给出每个题目的解题思路和代码示例。

3.1 二叉树的前序遍历(递归&非递归,下同)

3.2 二叉树的中序遍历

3.3 二叉树的后序遍历

3.4 二叉树层序遍历

3.5 求二叉树的高度

3.6 求二叉树节点个数

3.7 求二叉树第k层的节点个数

3.8 求二叉树中叶子节点的个数

3.9 判断一个节点是否在一棵二叉树中

3.10 判断两棵二叉树是否相同的树

3.11 判断二叉树是不是平衡二叉树

3.12 求二叉树的镜像

3. 13 判断两个二叉树是否互相镜像

3.14 从二叉树中查找结点

3.15 求二叉树中两个节点的最低公共祖先节点

3.16 判断是否为二分查找树BST

3.17 二叉搜索树中第K小的元素

3.18 填充每个节点的下一个右侧节点指针(完美二叉树)

3.19 填充每个节点的下一个右侧节点指针(普通二叉树)

3.20 表达式转二叉树

3.21 表达式求值

3.22 求两个节点的最近公共祖先

3.23 求二叉树中最远的两个节点的距离

3.24 由前序遍历和中序遍历重建二叉树

3.25 判断一棵树是否是完全二叉树

3.26 将二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点,只能调整树中结点指针的指向

3.27 求二叉树的宽度

3.28 判断一棵二叉树是否是平衡二叉树

3.28 判断一颗二叉树是否是另一颗树的子树

3.29 二叉树的右视图(二叉树最右边节点)

参考文献

  1. https://www.cnblogs.com/33debug/p/7252371.html
  2. https://www.cnblogs.com/33debug/p/7248822.html