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表达式求值