数据结构与算法之美-二叉树

数据结构与算法之美-二叉树

树是一种非线性表数据结构,相对于栈、队列等线性表结构较为复杂。二叉树是一种特殊的树,要求父节点最多有两个子节点。

相关概念

  • 节点的高度:节点到叶子节点的最长路径(边数)。
  • 节点的深度:根节点到这个节点所经历的边的个数
  • 节点的层数:节点深度+1。
  • 树的高度:根节点的高度。

二叉树的存储方式

基于指针或者引用的二叉链式存储法

这种方式要求每个节点有三个字段,其中一个存储数据,另外两个是指向左右子节点的指针。我们只要拎住根节点,就可以通过左右子节点的指针,把整棵树都串起来。
链式存储

基于数组的顺序存储法

这个方式把根节点存储在下标i = 1的位置,那根节点左子节点存储在下标2 * i = 2的位置,根节点右子节点存储在2 * i + 1 = 3的位置。以此类推,存储在下标为i的节点的左子节点存储在2 * i 的位置,右子节点存储在2 * i + 1的位置。
顺序存储

二叉树的遍历方式

经典的方法有三种,前序遍历、中序遍历和后序遍历。其中,前、中、后序,表示的是节点与它的左右子树节点遍历打印的先后顺序。也可采用分层打印的方式。

  • 前序遍历是指,对于树中的任意节点来说,先打印这个节点,然后再打印它的左子树,最后打印它的右子树。
  • 中序遍历是指,对于树中的任意节点来说,先打印它的左子树,然后再打印它本身,最后打印它的右子树。
  • 后序遍历是指,对于树中的任意节点来说,先打印它的左子树,然后再打印它的右子树,最后打印这个节点本身。
  • 分层遍历是指,首先打印第一层的数据,然后依次打印下一层的数据,直至最后一层。

前、中、后序遍历采用的是递归的思想,分层遍历可借助一个队列,采用广度优先遍历思想。具体编码实现点击这里查看

常见二叉树

满二叉树

二叉树的叶子节点都在最底层,除了叶子节点外,每个节点都有左右两个子节点,这种二叉树被称为满二叉树。

完全二叉树

二叉树的叶子节点都在最底下两层,最后一层的叶子节点都靠左排列,并且除了最后一层,其他层的节点个数都要达到最大,这种二叉树叫作完全二叉树。

满二叉树是特殊的完全二叉树,且满二叉树的特征很明显,为啥要把完全二叉树单拎出来分个类呢?我们知道二叉树用链式存储的方式要额外存储节点的左右孩子指针,这无疑会造成内存空间的浪费。如果采用顺序存储的方式,当节点不存在孩子节点时也会导致数组中部分节点空闲导致浪费。但是完全二叉树的特点保证了顺序存储只会浪费下标为0的一个节点,所以完全二叉树是完全适合采用顺序存储方式的二叉树。

二叉搜索树(二叉查找树)

二叉查找树中,每个节点的值都大于等于其左子树上节点的值,小于等于其右子树上节点的值。

查找元素

二叉查找树就是为了方便查找而出现的,支持最好O($log^n$),最差O(n)的时间复杂度。查找过程:我们先取根节点,如果它等于我们要查找的数据,那就返回。如果要查找的数据比根节点的值小,那就在左子树中递归查找;如果要查找的数据比根节点的值大,那就在右子树中递归查找。

插入元素

二叉查找树的插入过程有点类似查找操作,新插入的数据一般都是在叶子节点上,所以我们只需要从根节点开始,依次比较要插入的数据和节点的大小关系。

如果要插入的数据比节点的数据大,并且节点的右子树为空,就将新数据直接插到右子节点的位置;如果不为空,就再递归遍历右子树,查找插入位置。同理,如果要插入的数据比节点数值小,并且节点的左子树为空,就将新数据插入到左子节点的位置;如果不为空,就再递归遍历左子树,查找插入位置。

删除元素

删除操作需要分为三种情况进行不同的操作。

  1. 待删除节点无子节点,则直接将父节点中指向该节点的指针置空即可。
  2. 待删除节点只有一个子节点,则需要将父节点中指向该节点的指针指向该节点的子节点即可。
  3. 待删除节点有两个子节点,需要找到该节点左子树中的最大值或右子树中的最小值,然后将待删除节点的值替换成在子树中找到的节点值,然后将找到的节点从树中删除(采用方式1进行删除)。

刚才讨论的操作都是针对树中元素不存在相同值的情况,如果树中元素存在相同值,在查找插入位置的过程中,如果碰到一个节点的值,与要插入数据的值相同,我们就将这个要插入的数据放到这个节点的右子树,也就是说,把这个新插入的数据当作大于这个节点的值来处理。

当要查找数据的时候,遇到值相同的节点,我们并不停止查找操作,而是继续在右子树中查找,直到遇到叶子节点为止。

对于删除操作,我们也需要先查找到每个要删除的节点,然后再按前面讲的删除操作的方法,依次删除。