数据结构论坛

首页 » 分类 » 分类 » 二叉树的概念及面试题大全SunnyZh
TUhjnbcbe - 2025/2/2 16:39:00

1.二叉树(BinaryTree)的定义

1.1什么是二叉树(BinaryTree)

每个结点至多拥有两棵子树的树结构(即二叉树中不存在度大于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语言中可以通过结构体表示,其定义的方式可以是如下:

structbitree_node{intb_data;//数据域,指向具体的数据structbitree_node*left;//指向左子节点structbitree_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判断是否为二分查找树BST

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

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

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

3.18表达式转二叉树

3.19表达式求值

1
查看完整版本: 二叉树的概念及面试题大全SunnyZh