先了解树
“树”这种数据结构类似生活中的”树”,里面的每个元素叫做”节点”;用来连线相邻两个节点之间的关系,我们叫作”父子关系”.
在如下图中,A节点就是B节点的父节点,B节点是A节点的子节点.B,C,D这三个节点的父节点是同一个节点,所以称它们为兄弟节点.我们把没有父节点的节点叫作根节点,也就是图中的E.我们把没有子节点的节点叫作叶子节点或叶结点,比如图中的H,G,I,J,K,L都是叶子节点.
//TODO 图13
高度,深度和层
- 节点的高度=节点到叶子节点的最长路径(边数).
- 节点的深度=根节点到这个节点所经历的边的个数.
- 节点的层数=节点的深度+1
- 树的高度=根节点的高度
如图:
//TODO 图14
二叉树
二叉树,每个节点最多有两个子节点,分别是左子节点和右子节点.
//TODO 图15
编号2的二叉树,叶子节点全部在对底层,除了叶子节点外,每个节点都有左右两个子节点,这种二叉树叫作满二叉树.
编号3的二叉树,叶子节点都在最底下两层,除了最后一层其它层的节点个数都要达到最大.如果最后一层节点个数不满,必须靠左排列,这样的二叉树叫作完全二叉树.
二叉树的存储
存储二叉树有两种方法,一种是基于指针或者引用的二叉链式存储法.一种是基于数组的顺序存储法.
链式存储法
从图中可以看到,每个节点有三个字段,其中一个存储数据,另外两个分别指向左右子节点的指针.
//TODO 图16
顺序存储法
我们把跟节点存储在下标i=1的位置,左子节点存储在下标2 i = 2的位置,右子节点存储在2 i + 1 = 3的位置,以此类推,如图.
//TODO 图17
总结,如果节点X存储在数组下标为i的位置,下标2 i的位置存储的就是左子节点,下标2 i + 1的位置存储的就是右子节点.反过来下标i/2的位置存储的就是其父节点
二叉树的遍历
经典的方法有三种,前序遍历,中序遍历和后序遍历.
- 前序遍历是指,对于树中任意节点来说,先打印这个节点,然后再打印它的左子树,最后打印它的右子树.
- 中序遍历是指,对于树种任意节点来说,先打印它的左子树,然后打印它本身,再最后打印右子树.
- 后序遍历是指,对于树中任意节点来说,先打印它的左子树,然后打印它的右子树,最后打印本身.
实际上,二叉树的前,中,后序遍历就是一个递归的过程.
1 | //前序遍历 |
二叉查找树
二叉查找树也叫二叉搜索树.二叉查找树是为了实现快速查找而产生的,还支持快速的插入,删除一个数据.
二叉查找树的要求,在树种任意一个节点,其左子树的每个节点的值,都要小于这个节点的值,而右子树节点的值都大于这个节点的值.
//TODO 图18
二叉查找树的查找操作
我们先取根节点,如果等于要查找的值就返回.如果查找的数据比根节点小,那就在左子树中递归查找;如果比根节点值大,那就在右子树中递归查找.
1 | public TreeNode find(int value,TreeNode root){ |
插入操作
新插入的数据一般都是在叶子节点上,所以我们需要从根节点开始依次比较插入的数据和节点的大小关系.
如果插入的数据比节点大,并且右节点的右子树为空,则就将新数据插入到右子节点的位置;如果不为空,就遍历右子树,查找插入位置.同理,如果要插入的数据比节点数值小,并且节点的左子树为空,就插入到左子节点的位置;不为空,则遍历左子树,查找插入位置.
1 | //插入操作,不存在相同数据 |
删除操作
删除操作比较复杂,需要分三种情况处理
第一种情况,如果要删除的节点没有子节点,我们只需要直接将父节点中,指向要删除节点的指针置为null.
第二种情况,如果要删除的节点,只有一个子节点(只有左子节点或右子节点),我们只需要更新父节点中,指向要删除节点的指针,让它指向要删除节点的子节点就可以了.
第三种情况,如果要删除的节点有两个子节点,我们需要找到这个节点右子树中的最小节点,把它替换到要删除的节点上.然后再删除这个最小节点,因为最小节点肯定没有左子节点.
1 | public static void delete(int value, TreeNode root){ |
其他操作
二叉查找树还可以支持快速的查找最大节点和最小节点,前驱节点和后继节点.
还有一个重要特性中序遍历二叉查找树,可以输出有序的数据序列,时间复杂度是O(n),非常高效.
支持重复数据的二叉查找树
如果存储两个相同数据要如何处理?
第一种方法比较容易.二叉查找树中每一个节点不仅会存储一个数据,因此我们通过链表和支持动态扩容的数组等数据结构,把值相同的数据都存储在同一个节点上.
第二种,每个节点仍然只存一个数据.在查找插入位置的过程中,如果碰到一个节点与要插入数据的值相同,我们就将这个值放在这个节点的右子树,也就是说,把这个新插入的数据当做大于这个节点的值来处理.
当要查找的数据的时候,遇到值相同的节点,我们并不停止查找操作,而是继续右子树查找,直到遇到叶子节点,才停止.这样就可以把键值等于查找值的所有数据都找出来.
对于删除操作,我们也需要先查找到每个要删除的节点,然后按照前面讲的删除操作的方法,依次删除.
二叉查找树的时间复杂度分析
二叉查找树的形态格式各样.比如图中,对于同一种数据,我们构造了三种二叉查找树.它们的查找,插入,删除操作的执行效率都是不一样的.图中第一种二叉查找树,根节点的左右树极度不平衡,已经退化成了链表.查找的时间复杂度是O(n).
//todo 图19
理想情况下,二叉查找树是一个满二叉树或者完全二叉树.这个时候的时间复杂度其实都跟树的高度成正比,也就是O(height).
现在问题就变成了如何求一棵包含n个节点的完全二叉树的高度?
树的高度就等于最大层数减一.