1.学习平衡二叉树的时候最难理解的一点就是为什么平衡二叉树能够保证任意一个节点的左子树和右子树的高度差为0,1,-1
2.首先我们发现二叉树是对称的。我们可以通过插入数据1,2,3,4,5,6的方式去发现一般规律，总结怎样插入或者旋转才能使它达到每个节点的左子树和右子树的高度差为0，1,-1.
3.从特殊的案例归纳总结一般的结论
这里我们采用的方法是一种数学归纳法
1.当节点个数为1时，只有一个根节点，左子树和右子树的高度差为0
2.当节点个数为n时，我们假设结论成立，也就是n个节点的任意一个节点的左右子树的高度差为0，-1，1.
3.当插入第n+1个节点时，通过旋转等方式，证明当n+1时结论也是成立的。具体证明方式可以参考别人的博客(画图)。也就是当插入节点的父节点的高度差是0,-1,1的情况下，如何通过一些方式，比如旋转来达到最终每个节点的左右子树的高度差为0，-1，1.
4.当n成立时,n+1就成立。我们按照归纳的方式证明，当n=1是,n=2成立，当n=2成立时，n=3成立，以此类推。这也是数学归纳法的基本原理
下面是我用go实现的平衡二叉树的插入
balancetree.go
package main
import "fmt"
// 二叉平衡树
const (
Equal = iota // 左右子树高度平衡
LeftHeavy = 1 //左边树的高度大于右边
RightHeavy = -1 // 右子树的高度大于左边
)
type balanceTree struct {
value int
left *balanceTree
right *balanceTree
heightDifference int8
parent *balanceTree
}
var (
root *balanceTree
// currentTree *balanceTree
)
// 插入节点
func insert(value int) {
if root == nil {
root = &balanceTree{value: value}
return
}
currentTree := root
insert1(currentTree, value)
}
func insert1(currentTree *balanceTree, value int) {
if value < currentTree.value { //向左边查找
if currentTree.left == nil {
currentTree.left = &balanceTree{value: value, parent: currentTree}
fixHeight(currentTree, value)
} else {
insert1(currentTree.left, value)
}
} else if value > currentTree.value { //向右边查找
if currentTree.right == nil {
currentTree.right = &balanceTree{value: value, parent: currentTree}
fixHeight(currentTree, value)
} else {
insert1(currentTree.right, value)
}
} else { //以前插入过
fmt.Printf("value=%d已经存在\n", value)
}
}
// 修复树的高度
func fixHeight(tree *balanceTree, insertValue int) {
if tree == nil {
return
}
switch tree.heightDifference {
case Equal:
if insertValue < tree.value { //插入的是左边
tree.heightDifference = LeftHeavy
} else { //插入的是右边
tree.heightDifference = RightHeavy
}
fixHeight(tree.parent, insertValue)
case LeftHeavy:
if insertValue < tree.value {
rightRotat(tree, insertValue)
} else { //插入的是右边
//原来左边高度是n+1,右边是n,现在右边增加了1就变成相等了
tree.heightDifference = Equal //高度差变为0
}
case RightHeavy:
if insertValue < tree.value { //插入的是左边+
tree.heightDifference = Equal //高度差变为0
} else {
leftRotat(tree, insertValue)
}
}
}
// 右旋
func rightRotat(tree *balanceTree, insertValue int) {
parent := tree.parent
//右边旋转
left := tree.left
// 改变左边的树
left.heightDifference = Equal //高度差变为0
// left.left = left.left //左边没有改变
leftRight := tree.left.right
left.right = tree
left.parent = parent
//左边的父亲节点，指向当前节点的父亲节点
if parent != nil {
if parent.value > left.value {
parent.left = left
} else {
parent.right = left
}
} else {
root = left
}
//更改当前树
tree.left = leftRight
tree.heightDifference = Equal //高度差变为0
tree.parent = left
// tree.right=tree.right
}
// 左旋
func leftRotat(tree *balanceTree, insertValue int) {
//插入的是右边，需要进行左旋
right := tree.right
parent := tree.parent
right.parent = parent
right.heightDifference = Equal //高度差变为0
// right.right=right.right
rightLeft := tree.right.left
right.left = tree
if parent != nil {
if parent.value > right.value {
parent.left = right
} else {
parent.right = right
}
} else {
root = right
}
// tree.left=tree.left
tree.right = rightLeft
tree.parent = right
tree.heightDifference = Equal //高度差变为0
}
main.go
package main
import "fmt"
func main() {
for i := 1; i <= 20; i++ {
fmt.Println("")
insert(i)
totalLayers := calLays(i)
leveltraversal(totalLayers)
fmt.Println("前序遍历")
preOrder(root)
fmt.Println("")
fmt.Println("中序遍历")
inOrder(root)
fmt.Println("")
fmt.Println("后序遍历")
postOrder(root)
fmt.Println("")
}
}
print.go
package main
import "fmt"
// 第一到n层的数量是 1,2,4,8,..
// 本层的数量是上面一层的2倍，第一层数量为1
// 计算层数
// count代表总共有多少个数
func calLays(count int) int {
if count == 0 {
return 0
}
var total int = 0
var levelCount = 1
var level int = 1
for {
total += levelCount
if total >= count {
return level // 两边子树的层数可能不一致，比如左边比右边高或者右边比左边高
}
levelCount = levelCount * 2
level++
}
}
// 打印每一层数据
// 没有的节点用0表示
func leveltraversal(totalLayers int) {
var level int //第几层，从0开始
var info = make([][]*balanceTree, totalLayers)
info[level] = append(info[level], root)
for {
nextLevel := level + 1
if nextLevel > totalLayers || len(info[level]) <= 0 {
break
}
for i := 0; i < len(info[level]) && nextLevel < totalLayers; i++ {
if info[level][i].left != nil {
info[nextLevel] = append(info[nextLevel], info[level][i].left)
} else if info[level][i].value != 0 {
info[nextLevel] = append(info[nextLevel], &balanceTree{value: 0})
}
if info[level][i].right != nil {
info[nextLevel] = append(info[nextLevel], info[level][i].right)
} else if info[level][i].value != 0 {
info[nextLevel] = append(info[nextLevel], &balanceTree{value: 0})
}
}
level = nextLevel
}
for level := 0; level < len(info); level++ {
var s string
for i := 0; i < len(info[level]); i++ {
s += fmt.Sprintf("%d ", info[level][i].value)
}
if s != "" {
fmt.Println("字符串" + s)
}
}
fmt.Println("")
}
// 前序遍历
// 先根，然后左子树，最后右子树
func preOrder(root *balanceTree) {
if root == nil {
return
}
fmt.Printf("%d ", root.value)
preOrder(root.left)
preOrder(root.right)
}
// 中序遍历
func inOrder(root *balanceTree) {
if root == nil {
return
}
inOrder(root.left)
fmt.Printf("%d ", root.value)
inOrder(root.right)
}
// 后序遍历
func postOrder(root *balanceTree) {
if root == nil {
return
}
postOrder(root.left)
postOrder(root.right)
fmt.Printf("%d ", root.value)
}
以上纯属个人见解，如果有什么错误，敬请留言指正，谢谢
