Java 中的倾斜二叉树

面试中关于二叉树的重要考点之一是Java 中的倾斜二叉树。必须了解倾斜二叉树，因为它有助于理解为什么学习 AVL 和其他树很重要。它是基本树之一，也影响数据结构（二叉搜索树）的时间复杂度。

倾斜二叉树的类型

倾斜二叉树有两种类型

1. 左倾斜二叉树
2. 右倾斜二叉树

现在我们将详细探讨上述类型。

1. 左倾斜二叉树

如果树的所有节点都只有一个左子节点或没有子节点，则该二叉树称为左倾斜二叉树。也可以说它是一个偏向左侧的树。请注意，在此树中，所有出现在右侧的子节点都为 null。

文件名： LeftSkewedBinaryTree.java

输出

11 10 9 8 7

2. 右倾斜二叉树

如果树的所有节点都只有一个右子节点或没有子节点，则该二叉树称为右倾斜二叉树。也可以说它是一个偏向右侧的树。请注意，在此情况下，所有出现在左侧的子节点都为 null。

文件名： RightSkewedBinaryTree.java

输出

11 12 13 14 15

倾斜二叉树对复杂度的影响

倾斜二叉树可以被视为链表，我们知道遍历链表的时间复杂度为 O(n)。倾斜二叉树的时间复杂度也为 O(n)。如果考虑二叉搜索树的情况，我们知道搜索一个元素需要 O(log(n)) 的时间，但如果二叉搜索树是倾斜的，则需要 O(n) 的时间。这就是自平衡树的必要性出现的原因。