为何二叉树旋转能让人秒懂其操作原理？

本文共计2071个文字，预计阅读时间需要9分钟。

事情要从某天晚上买床垫说起。买了香肠边吃边想，多年来的树旋转是否应该看看，就点进了某百科。树旋转是二叉树中的一种子树调整操作，每次旋转不影响树这个概念。

事情要从某天晚上买夜宵说起。买了香肠拿着吃，想着多年来一直没搞懂的树旋转是不是应该看看，就点进某百科。

树旋转是在二叉树中的一种子树调整操作， 每一次旋转并不影响对该二叉树进行中序遍历的结果。

中序遍历！灵光一闪，好像很多东西都联系起来了！

为什么是中序遍历

中序遍历是指按的顺序遍历，这个内容能让我们想起什么？二叉排序树。

二叉排序树要求左节点的值小于父节点，右节点大于父节点。如果按照中序遍历二叉排序树，就能得到一个顺序结果。

知道这一点有什么用？在后续的旋转过程中，我们可以根据二叉排序树的父节点和子节点的大小关系来辅助理解旋转。

举个例子

现在我们有一颗二叉排序树：

其中序遍历的结果是 1、2、3、4、5、6、7、8、9。

以下先不考虑子树的旋转。

右旋

现在对根节点 5 执行右旋。右旋的时候，要选择根节点 5 的左节点 3 作为新的根节点，称为以节点 3 为转轴。

为讨论方便，把旋转前 3 的右子树称为 A，5 的右子树称为 B。如下图所示：

由于是右旋转，当节点 3 处于根节点的时候，其左子树的数必须仍然小于 3，又因为 A、5、B 都大于 3，所以 3 旋转前的左子树在旋转后保持原样，仍然是 3 的左子树。

现在有两个问题：

1. A 放哪里？
2. 根节点 5 放在哪里？

结合二叉排序树来理解。