1）什么是平衡二叉树？
2）平衡二叉树的特点是什么？
3）平衡二叉树的构建实现？
一、什么是平衡二叉树？
假设有一组数据[1,2,3,4,5]，插入到排序二叉树上，此时这颗二叉树的高度是5，时间效率为O(n)。为了解决这种查询低效情况下的排序二叉树，改进得到平衡二叉树，它是一棵平衡因子（左右子树高度差不超过1）不大于一的排序二叉树，并且它这颗树上的所有结点的平衡因子都不大于一。
二、平衡二叉树的特点是什么？
1）它是一棵排序二叉树
2）这颗树上的每一个结点的平衡因子都不大于一。
三、平衡二叉树的构建实现？
假设往一棵平衡二叉树插入一个数据，那么只会有四种情况打破平衡。分别是：
1）离打破平衡因子最近一个结点开始，它的左子树上的左结点加入数据
2）离打破平衡因子最近一个结点开始，它的左子树上的右结点加入数据
3）离打破平衡因子最近一个结点开始，它的右子树上的左结点加入数据
4）离打破平衡因子最近一个结点开始，它的右子树上的右结点加入数据
第一种对结点进行：右旋转
第二种对结点进行：先左旋转-右旋转
第三种对结点进行：左旋转
第四种对节点进行：先右旋转-左旋转
平衡二叉树是什么
平衡二叉树调整
平衡二叉树左旋转代码原理
平衡二叉树右旋转代码原理
平衡二叉树双旋代码原理
下面代码实现：
左旋转
func (t *AVLBTree)LeftRotate() {
// 1)创建一个新节点，值等于当前根节点的值
tVal := *t.val
newTNode := &AVLBTree{
val:&tVal,
}
// 2)把新节点的左子树设置成当前根节点的左子树
newTNode.lchild = t.lchild
// 3)把新节点的右子树设置成当前根节点右子树的左子树
newTNode.rchild = t.rchild.lchild
// 4)把当前根节点的值设置成当前根节点右子树的值
*t.val = *t.rchild.val
// 5)把当前根节点的左子树设置成新节点
t.lchild = newTNode
// 6)把当前根节点的右子树设置成当前根节点的右子树的右子树
t.rchild = t.rchild.rchild
}
右旋转
func (t *AVLBTree)RightRotate() {
// 1)创建一个新节点，值等于当前节点
tVal := *t.val
newTNode := &AVLBTree{
val:&tVal,
}
// 2)新节点的左子树指向当前节点的左子树的右子树
newTNode.lchild = t.lchild.rchild
// 3)新节点的右子树指向当前节点的右子树
newTNode.rchild = t.rchild
// 4）当前节点的值等于当前节点左子树的值
*t.val = *t.lchild.val
// 5)当前节点的右子树等于新节点
t.rchild = newTNode
// 6)当前节点的左子树等于当前节点左子树的左子树
t.lchild = t.lchild.lchild
}
完整代码
package main
import (
"fmt"
"math"
)
type AVLBTree struct {
val *int
bal int
lchild, rchild, parent *AVLBTree
}
func (t *AVLBTree)Insert(val int) {
if t.val == nil {
t.val = &val
return
}
if *t.val > val {
if t.lchild == nil {
t.lchild = &AVLBTree{val:&val}
} else {
t.lchild.Insert(val)
}
} else {
if t.rchild == nil {
t.rchild = &AVLBTree{val:&val}
} else {
t.rchild.Insert(val)
}
}
//for {
// for *t1.val > val && t1.lchild != nil {
// t1 = t1.lchild
// }
// if *t1.val > val && t1.lchild == nil {
// t1.lchild = &AVLBTree{
// val:&val,
// parent:t1}
// break
// }
// for *t1.val <= val && t1.rchild != nil {
// t1 = t1.rchild
// }
// if *t1.val <= val && t1.rchild == nil {
// t1.rchild = &AVLBTree{
// val:&val,
// parent:t1}
// break
// }
//}
//r = t
// 当添加一个数据之后，如果：（右子树的高度-左子树的高度） > 1，左旋转
if t.rchild.Height() - t.lchild.Height() > 1 {
// 如果右子树的左子树高度 大于 右子树的右子树高度，则要先进行右旋转
if t.rchild != nil && t.rchild.lchild.Height() > t.rchild.rchild.Height() {
t.rchild.RightRotate()
}
t.LeftRotate()
}
// 当添加一个数据之后，如果：（左子树的高度-右子树的高度） < 1，右旋转
if t.lchild.Height() - t.rchild.Height() > 1 {
// 如果左子树的左子树高度 小于 右子树，则要先进行左选择
if t.lchild != nil && t.lchild.lchild.Height() < t.lchild.rchild.Height() {
t.lchild.LeftRotate()
}
t.RightRotate()
}
}
func (t *AVLBTree)PreOrder() {
if t == nil {
return
}
fmt.Print(*t.val, " ")
if t.lchild != nil {
t.lchild.PreOrder()
}
if t.rchild != nil {
t.rchild.PreOrder()
}
}
func (t *AVLBTree)InfixOrder() {
if t == nil {
return
}
if t.lchild != nil {
t.lchild.InfixOrder()
}
fmt.Print(*t.val, " ")
if t.rchild != nil {
t.rchild.InfixOrder()
}
}
func (t *AVLBTree)PostOrder() {
if t == nil {
return
}
if t.lchild != nil {
t.lchild.PostOrder()
}
if t.rchild != nil {
t.rchild.PostOrder()
}
fmt.Print(*t.val, " ")
}
func (t *AVLBTree)Height() int {
var lh, rh int
if t == nil {
return 0
}
if t.lchild != nil {
lh = t.lchild.Height()
}
if t.rchild != nil {
rh = t.rchild.Height()
}
return int(math.Max(float64(lh), float64(rh))) + 1
}
/*
打破平衡二叉树有四种情况：
（1）LL
（2）LR
（3）RR 左旋转
（4）RL
*/
func (t *AVLBTree)LeftRotate() {
// 1)创建一个新节点，值等于当前根节点的值
tVal := *t.val
newTNode := &AVLBTree{
val:&tVal,
}
// 2)把新节点的左子树设置成当前根节点的左子树
newTNode.lchild = t.lchild
// 3)把新节点的右子树设置成当前根节点右子树的左子树
newTNode.rchild = t.rchild.lchild
// 4)把当前根节点的值设置成当前根节点右子树的值
*t.val = *t.rchild.val
// 5)把当前根节点的左子树设置成新节点
t.lchild = newTNode
// 6)把当前根节点的右子树设置成当前根节点的右子树的右子树
t.rchild = t.rchild.rchild
}
func (t *AVLBTree)RightRotate() {
// 1)创建一个新节点，值等于当前节点
tVal := *t.val
newTNode := &AVLBTree{
val:&tVal,
}
// 2)新节点的左子树指向当前节点的左子树的右子树
newTNode.lchild = t.lchild.rchild
// 3)新节点的右子树指向当前节点的右子树
newTNode.rchild = t.rchild
// 4）当前节点的值等于当前节点左子树的值
*t.val = *t.lchild.val
// 5)当前节点的右子树等于新节点
t.rchild = newTNode
// 6)当前节点的左子树等于当前节点左子树的左子树
t.lchild = t.lchild.lchild
}
func main() {
var t AVLBTree
//var v = []int{10,6,3,7,5,6,1,12,13}
//v := []int{3,2,1}
var v = []int{8,6,7,5,4,10,12,13,9,11}
for i := 0;i < len(v);i++ {
t.Insert(v[i])
}
fmt.Println("先续遍历：")
t.PreOrder()
fmt.Println()
fmt.Println("中序遍历：")
t.InfixOrder()
fmt.Println()
fmt.Println("后序遍历：")
t.PostOrder()
fmt.Println()
fmt.Println("高度=", t.Height())
}
网友评论