树的转换与平衡二叉树

树如何转化成二叉树

1. 将树的根节点直接作为二叉树的根节点。

2. 将树的根节点的第一个子节点作为二叉树根节点的左指针，若该子节点存在兄弟节点，则将该子节点的第一个兄弟节点（方向从左往右）作为该子节点的右指针。

3. 树中的剩余节点按照上一步的方式（左孩子，右兄弟），依序添加到二叉树中。直到树中所有的节点都在二叉树中。

   如何将树转化为二叉树

二叉排序树

节点左子树的数据必须小于该节点的数据，右子树必须大于该节点的数据。 中序遍历刚好是从小到大排列。

图片.png

平衡树

为什么要有平衡树：对二叉排序树进行查询、新增、删除操作时，决定所花的时间与树的高度相关，与树的容量不成正比。因此，将二叉排序树无论在什么情况下都能使他的形态最大限度的接近满二叉树来保证他的查询效率就很有意义。
平衡树：它或者是一颗空树，或者是具有以下性质的二叉树：它的左子树和右子树都是平衡二叉树，且左子树和右子树的高度只差的绝对值不超过1。
平衡因子：每一节点的左子树高度减右子树高度称为该节点的平衡因子。平衡二叉树每一节点的平衡因子只能是0，-1，+1.

平衡二叉树的调整

不平衡节点称为麻烦节点，调整优先下层不平衡子树
左单旋LL（要从左向右旋）
添加节点在麻烦节点的左子树的左节点上导致不平衡

图片.png

右单旋RR（要从右向左旋）
添加节点在麻烦节点的右子树的右节点上

图片.png

LR旋转（先从左向右，再从右向左）
添加节点在麻烦节点的左子树右节点上

图片.png

注意 下图要先旋转9 10 再按RR型旋转

图片.png

RL旋转
添加节点在麻烦节点右子树左节点上

图片.png 图片.png