树

相邻节点之间有“父子关系”, 离根节点近的是父节点，没有父节点的是根节点，有相同父节点的互相称为兄弟节点，没有子节点的叫做叶子节点。

树的高度、深度、层

image.png

二叉树(Binary Tree)

每个节点最多有两个子节点，分别为左子节点和右子节点。
image.png

上图中2为满二叉树，3为完全二叉树

完全二叉树

满二叉树比较容易理解，每一层的节点数都达到了最大。
完全二叉树涉及到数据在内存中的存储方式，基于数组的顺序存储法如下：
image.png

如上，如果某棵二叉树是一棵完全二叉树，那么用数组存储数据是一种最节省内存的方式。

二叉树的遍历

image.png

二叉查找树(BST)

二叉查找树：要求在树种的任意一个节点，其左子树种的每个节点的值，都要小于这个节点的值，而右子树节点的值都大于这个节点的值。
二叉查找树最大的特点就是支持动态数据集合的快速插入、删除、查找操作。
image.png

查找

image.png

插入

image.png

删除

删除操作分为三种情况：

  • 待删除的节点没有子节点，则直接删除
  • 待删除的节点只有一个字节点

将待删除节点的子节点移动到该节点位置

  • 待删除节点有两个子节点

找到该节点的右子树种的最小节点，并将其移动到待删除的节点位置并与之替换
image.png

平衡二叉查找树(AVL)

平衡二叉树的定义：二叉树中任意一个节点的左右子树的高度相差不能大于1
image.png

平衡二叉查找树就是满足平衡二叉树要求的二叉查找树。