作业帮 > 综合 > 作业

27,16,73,35,42构造平衡二叉树.怎么构建、、然后所做的平衡旋转都是什么?

来源:学生作业帮 编辑:作业帮 分类:综合作业 时间:2024/05/05 20:38:56
27,16,73,35,42构造平衡二叉树.怎么构建、、然后所做的平衡旋转都是什么?
首先按照这个顺序27,16,73,35,42输入,得到如下二叉排序树
27
16 73
35
42
不平衡最小子树的根节点是73
所以要旋转以73为根结点的子树使得整棵树平衡
观察这棵子树可知 这是一个LR型的子树
需要对其进行两次旋转先L软后R
L旋转得到
73
42
35
R旋转得到
42
35 73
所以整合整棵树得到平衡二叉树为
27
16 42
35 73