0

我有以下二叉树,我正在尝试使用最少的树旋转次数将其转换为目标二叉树(帖子中的第二棵树)。这棵树的理论最小旋转数是 5,但是,我能算出的最小值是 6 旋转,我也复制了旋转,我错过了什么?

树: 1 \ \ 3 / \ / \ 2 5 / \ / \ 4 7 / \ / \ 6 11 / \ / \ 9 12 / \ 8 10

目标树: 1 \ \ 11 / \ / \ 9 12 / \ / \ 3 10 / \ / \ 2 5 / \ / \ 4 7 / \ 6 8

到目前为止我尝试过的旋转(所有这些都需要 6 次旋转):

订单 1: Rotate left with root 7 and pivot 11 Rotate left with root 5 and pivot 11 Rotate left with root 3 and pivot 11 Rotate left with root 7 and pivot 9 Rotate left with root 5 and pivot 9 Rotate left with root 3 and pivot 9 订单 2: Rotate left with root 7 and pivot 11 Rotate left with root 5 and pivot 11 Rotate left with root 7 and pivot 9 Rotate left with root 3 and pivot 11 Rotate left with root 5 and pivot 9 Rotate left with root 3 and pivot 9

订单3: Rotate left with root 7 and pivot 11 Rotate left with root 5 and pivot 11 Rotate left with root 7 and pivot 9 Rotate left with root 5 and pivot 9 Rotate left with root 3 and pivot 11 Rotate left with root 3 and pivot 9

订单4: Rotate left with root 7 and pivot 11 Rotate left with root 7 and pivot 9 Rotate left with root 5 and pivot 11 Rotate left with root 3 and pivot 11 Rotate left with root 5 and pivot 9 Rotate left with root 3 and pivot 9

订单5: Rotate left with root 7 and pivot 11 Rotate left with root 7 and pivot 9 Rotate left with root 5 and pivot 11 Rotate left with root 5 and pivot 9 Rotate left with root 3 and pivot 11 Rotate left with root 3 and pivot 9

4

1 回答 1

1

以根 11 和轴 9
向右旋转 以根 7 和轴 9
向左旋转 以根 5 和轴 9
向左旋转 以根 3 和轴 9
向左旋转 以根 9 和轴 11 向左旋转

于 2016-10-23T21:29:09.130 回答