（七）算法与数据结构|二叉树

树的相关概念（高度、深度、层数）图示：

二叉树图示：

定义：

二叉树

每个节点最多两个“叉（子节点）”。图中三个都是二叉树。

满二叉树

看起来是一个三角形，如二叉树图示编号2的树。

• 叶子节点全部在底层
• 除了叶子节点，所有节点都有两个子节点

完全二叉树

如二叉树图示编号3的树。

• 叶子节点都在最后2层
• 最后一层叶子节点的父节点如果只有一个节点，则只有子节点
• 倒数第二层的叶子点的父节点都有两个子节点

完全二叉树定义的由来和如何表示（存储）一颗二叉树有关。

存储一棵树有2种方法：

• 基于链表或引用的二叉链式存储法
• 基于数组的顺序存储法

二叉链式存储法：

每个节点存储三个字段：一个存数据、两个存指针指向左右子节点。只要得到根节点，就能通过子节点指向左右子节点的指针得到整棵树。此方法是常用的存储二叉树方法。

顺序存储法：

根节点存在数组下标 i=1 的位置。左子节点存在 父节点下标x2 的位置，右子节点存在 父节点下标x2+1 的位置。以此类推，存其余节点。反过来推算，左子节点下标/2 即父节点下标。

根据上面的顺序存储法，用数组存储完全二叉树比链表存储更节省内存，因为链表还要额外存储指向子节点的指针。这就是完全二叉树定义由来，这就是要求完全二叉树最后一层叶子节点的父节点如果只有一个子节点则只有左子节点的原因。

堆就是一种完全二叉树，常用数组存储。

二叉树遍历：

如何将二叉树所有节点都遍历？经典方法有3种：

• 前序遍历：任意树中节点，先遍历此节点，再遍历其左子节点，后遍历其右子节点
• 中序遍历：任意树中节点，先遍历其左子节点，再遍历此节点，后遍历其右子节点
• 后序遍历：任意树中节点，先遍历其左子节点，再遍历其右子节点，后遍历此节点

  

  前序、中序、后序表示节点和其左右子节点遍历顺序。三种遍历其实是一个递归的过程。

  时间复杂度：O(n)。

二叉查找树：

支持动态数据集合的快速地插入、删除、查找操作。散列表也支持这些操作，但是有些情况二叉查找树无法转换为散列表。什么情况呢？

支持以上操作依赖于二叉查找树的特殊结构：要求树中任意节点的左子树的每个值都小于这个节点的值；右子树的每个值都大于这个节点的值。

二叉查找树的查找操作：

取到根节点值与给定值比较，小于根节点值则在节点的左子树递归继续查找；大于根节点值则在节点右子树递归继续查找。

二叉查找树的插入操作：

类似查找操作。

二叉查找树的删除操作：

分3种情况：

• 被删除节点没有子节点，只要把父节点指向被删除节点的指针，指向null
• 被删除节点有一个子节点，只要把父节点指向被删除节点的指针，指向被删除节点的子节点
• 被删除节点有两个子节点，只要把被删除节点的值更新为被删除节点树中的最小值

二叉查找树的其他操作：

支持快速查找最大节点、最小节点、前驱节点、后驱节点。

中序遍历二叉查找树可以得到有序序列。时间复杂度：O(n)，高效。 因此二叉查找树也叫二叉排序树。

支持重复数据的二叉查找树：

实际开发中，二叉查找树存储的多是包含多个字段的对象，用其中一个对象作为键值构建二叉查找树，其余对象字段叫做卫星数据。

如果多个对象的键值相等，两种处理方法：

• 此方法简单。通过链表和支持动态扩容的数组等数据结构，把值相同的数据存储在同一个节点

• 此方法优雅，如果两个值相等，则把要插入的值插入到这个值的右子节点。把插入的值处理为大于这个节点。

  当查找时，查找到相等的值并不停止查找，继续查找节点的右子树，直到遇到叶子节点。

  当删除时，先查找到要删除的所有节点，然后按照前面的二叉树删除操作操作。

二叉查找树时间复杂度分析

各种二叉查找树：

最糟糕情况时第一种，直接退化成链表；最理想的情况是：完全二叉树或满二叉树。

查找、删除、插入操作的时间复杂度都和树的高度成正比，即O(height)。

END