# 深入理解数据结构--二叉树（进阶篇1）

## 二叉查找树

1. 如果左子树不为空，则左子树上所有节点的值均小于根节点的值。
2. 如果右子树不为空，则右子树上所有节点的值均大于根节点的值。
3. 左、右子树也都是二叉查找树。

``````type binaryTree struct {
value int
leftNode *binaryTree
rightNode *binaryTree
}``````

### 二叉树的查找

1. 访问根节点6，发现4<6

1. 访问根节点6的左孩子节点3，发现4>3

1. 访问节点3的右孩子节点4，发现正是要查找的节点

``````//节点查找
func findNode(num int,tree *binaryTree) bool{
targetNode := tree
for targetNode != nil{
if targetNode.value == num {
return true
}else if targetNode.value > num {
targetNode = targetNode.leftNode
}else {
targetNode = targetNode.rightNode
}
}
return false
}``````

### 二叉树的插入

``````//节点插入
func insertNode(tree *binaryTree,node *binaryTree) *binaryTree {

if tree.value == 0 {
return node
}
if tree.value == node.value {
return tree
}else if tree.value > node.value {
//往左子树走,为空则直接插入节点
if tree.leftNode == nil {
tree.leftNode = node
}else {
tree.leftNode = insertNode(tree.leftNode,node)
}
}else {
//往右子树走,为空则直接插入节点
if tree.rightNode == nil {
tree.rightNode = node
}else {
tree.rightNode = insertNode(tree.rightNode,node)
}
}
return tree
}``````

### 二叉树的删除

``````
//删除节点
func deleteNode(num int,tree *binaryTree) *binaryTree{
//先查看删除的值是否存在树当中
find := findNode(num,tree)
if find {
//配置到节点值，执行删除操作
if tree.value == num {
//删除的节点无左右节点
if tree.leftNode == nil && tree.rightNode == nil {
tree = &binaryTree{}
}else if tree.leftNode == nil && tree.rightNode != nil {
//左节点为空，右节点不为空
tree = tree.rightNode
}else if tree.rightNode == nil && tree.leftNode != nil {
//右节点为空，左节点不为空
tree = tree.leftNode
}else{
//节点左右节点都存在
tree = replaceNode(tree)
}
}else if tree.value > num {
tree.leftNode = deleteNode(num,tree.leftNode)
}else {
tree.rightNode = deleteNode(num,tree.rightNode)
}
}
return tree
}

//替换删除节点
func replaceNode(tree *binaryTree) *binaryTree{
//删除的节点无左右节点
if tree.leftNode == nil && tree.rightNode == nil {
tree = &binaryTree{}
}else if tree.leftNode == nil && tree.rightNode != nil {
//左节点为空，右节点不为空
tree = tree.rightNode
}else if tree.rightNode == nil && tree.leftNode != nil {
//右节点为空，左节点不为空
tree = tree.leftNode
}else{
//节点左右节点都存在，则从右子树查找节点替代父节点
//若右节点下没有左右节点,则直接用右节点的值替换，并删除右节点
if tree.rightNode.leftNode == nil && tree.rightNode.rightNode == nil {
tree.value = tree.rightNode.value
tree.rightNode = &binaryTree{}
}else if tree.rightNode.leftNode == nil && tree.rightNode.rightNode != nil {
//若右节点下左节点为空，右节点不为空，则右节点的值替换，并将右节点的右节点替换过来
tree.value = tree.rightNode.value
tree.rightNode = tree.rightNode.rightNode
}else{
//若右节点的左节点不为空
tree.value = tree.rightNode.leftNode.value
tree.rightNode.leftNode = replaceNode(tree.rightNode.leftNode)
}
}
return tree
}``````

``````package main

import "fmt"

type binaryTree struct {
value int
leftNode *binaryTree
rightNode *binaryTree
}

func main(){

var numArr = []int{10,11,4,2,8,1,3,6,9,5,7}

tree := createBinarySearchTree(numArr)
find := findNode(9,tree)
fmt.Print(find)
tree = deleteNode(4,tree)
node := &binaryTree{13,nil,nil}
tree = insertNode(tree,node)
node = &binaryTree{1,nil,nil}

var middle []int
middle = middleForeach(*tree,middle)
fmt.Println(middle)
}

//创建平衡二叉树
func createBinarySearchTree(nums []int) *binaryTree{
tree := new(binaryTree)
for index := range nums{
node := &binaryTree{nums[index],nil,nil}
tree = insertNode(tree,node)
}
return tree
}

//删除节点
func deleteNode(num int,tree *binaryTree) *binaryTree{
//先查看删除的值是否存在树当中
find := findNode(num,tree)
if find {
//配置到节点值，执行删除操作
if tree.value == num {
//删除的节点无左右节点
if tree.leftNode == nil && tree.rightNode == nil {
tree = &binaryTree{}
}else if tree.leftNode == nil && tree.rightNode != nil {
//左节点为空，右节点不为空
tree = tree.rightNode
}else if tree.rightNode == nil && tree.leftNode != nil {
//右节点为空，左节点不为空
tree = tree.leftNode
}else{
//节点左右节点都存在
tree = replaceNode(tree)
}
}else if tree.value > num {
tree.leftNode = deleteNode(num,tree.leftNode)
}else {
tree.rightNode = deleteNode(num,tree.rightNode)
}
}
return tree
}

//替换删除节点
func replaceNode(tree *binaryTree) *binaryTree{
//删除的节点无左右节点
if tree.leftNode == nil && tree.rightNode == nil {
tree = &binaryTree{}
}else if tree.leftNode == nil && tree.rightNode != nil {
//左节点为空，右节点不为空
tree = tree.rightNode
}else if tree.rightNode == nil && tree.leftNode != nil {
//右节点为空，左节点不为空
tree = tree.leftNode
}else{
//节点左右节点都存在，则从右子树查找节点替代父节点
//若右节点下没有左右节点,则直接用右节点的值替换，并删除右节点
if tree.rightNode.leftNode == nil && tree.rightNode.rightNode == nil {
tree.value = tree.rightNode.value
tree.rightNode = &binaryTree{}
}else if tree.rightNode.leftNode == nil && tree.rightNode.rightNode != nil {
//若右节点下左节点为空，右节点不为空，则右节点的值替换，并将右节点的右节点替换过来
tree.value = tree.rightNode.value
tree.rightNode = tree.rightNode.rightNode
}else{
//若右节点的左节点不为空
tree.value = tree.rightNode.leftNode.value
tree.rightNode.leftNode = replaceNode(tree.rightNode.leftNode)
}
}
return tree
}

//节点查找
func findNode(num int,tree *binaryTree) bool{
targetNode := tree
for targetNode != nil{
if targetNode.value == num {
return true
}else if targetNode.value > num {
targetNode = targetNode.leftNode
}else {
targetNode = targetNode.rightNode
}
}
return false
}

//节点插入
func insertNode(tree *binaryTree,node *binaryTree) *binaryTree {

if tree.value == 0 {
return node
}
if tree.value == node.value {
return tree
}else if tree.value > node.value {
//往左子树走,为空则直接插入节点
if tree.leftNode == nil {
tree.leftNode = node
}else {
tree.leftNode = insertNode(tree.leftNode,node)
}
}else {
//往右子树走,为空则直接插入节点
if tree.rightNode == nil {
tree.rightNode = node
}else {
tree.rightNode = insertNode(tree.rightNode,node)
}
}
return tree
}

//中序遍历
func middleForeach(tree binaryTree,num []int) []int{
var leftNum,rightNum []int
//若存在左节点，遍历左节点树
if tree.leftNode != nil {
leftNum = middleForeach(*tree.leftNode,leftNum)
for _,value := range leftNum{
num = append(num,value)
}
}

//先遍历根节点
if tree.value != 0 {
num = append(num,tree.value)
}

//若存在右节点，遍历右节点树
if tree.rightNode != nil {
rightNum = middleForeach(*tree.rightNode,rightNum)
for _,value := range rightNum{
num = append(num,value)
}
}

return num
}
``````

## 二叉平衡树

### 平衡因子

AVL树对平衡因子的限制(只能是-1，0，1)，保证了任意节点的两棵树的高度差都不超过1，这种状态被称为高度平衡

``````//检查树是否达到平衡
func (tree binaryTree) isBalance() bool {
if tree.RightNode == nil && tree.LeftNode == nil {
return true
}
//节点的平衡因子
factor := tree.getTreeFactor()
if factor > 1 || factor < -1 {
return false
}
return true
}

//获取节点的平衡因子
func (tree binaryTree) getTreeFactor() int{
leftFactor,rightFactor := 0,0
if tree.RightNode != nil {
rightFactor = tree.RightNode.getTreeHeight()
}
if tree.LeftNode != nil {
leftFactor = tree.LeftNode.getTreeHeight()
}
factor := float64(leftFactor - rightFactor)
return int(factor)
}

//获取节点树高度，深度优先
func (tree binaryTree) getTreeHeight() int{
//节点无
if tree.RightNode == nil && tree.LeftNode == nil {
return 1
}
leftHeight,rightHeight := 1,1
if tree.LeftNode != nil && tree.LeftNode.Value != 0 {
leftHeight = 1 + tree.LeftNode.getTreeHeight()
}
if tree.RightNode != nil && tree.RightNode.Value != 0{
rightHeight = 1 + tree.RightNode.getTreeHeight()
}
//比较左右节点树高度
height := math.Max(float64(leftHeight),float64(rightHeight))
return int(height)
}``````

### 树平衡调整

1. 左左局面(LL)

1. 右右局面(RR)

1. 左右局面(LR)

1. 右左局面(RL)

``````//左左局面
func LeftLeftRotate(tree *binaryTree) *binaryTree{
//原节点左节点成为根节点
mainNode := tree.LeftNode
changeNode := &binaryTree{}
//判断原节点左节点是否存在
if mainNode.RightNode != nil {
changeNode = mainNode.RightNode
}
mainRightNode := tree
mainRightNode.LeftNode = changeNode
//刷新树高度
mainRightNode.Height = mainRightNode.getTreeHeight()
mainNode.RightNode = mainRightNode
mainNode.Height = mainNode.getTreeHeight()
return mainNode
}

//右右局面
func RightRightRotate(tree *binaryTree) *binaryTree{
mainNode := tree.RightNode
changeNode := &binaryTree{}
if mainNode.LeftNode != nil {
changeNode = mainNode.LeftNode
}
mainLeftNode := tree
mainLeftNode.RightNode = changeNode
mainLeftNode.Height = mainLeftNode.getTreeHeight()
mainNode.LeftNode = mainLeftNode
mainNode.Height = mainNode.getTreeHeight()
return mainNode
}

//左右局面
func LeftRightRotate(tree *binaryTree) *binaryTree{
mainLeftNode := tree.LeftNode
changeNode := &binaryTree{}
mainNode := mainLeftNode.RightNode
if mainNode.LeftNode != nil {
changeNode = mainNode.LeftNode
}
mainLeftNode.RightNode = changeNode
mainLeftNode.Height = mainLeftNode.getTreeHeight()
mainNode.LeftNode = mainLeftNode
mainNode.Height = mainNode.getTreeHeight()
tree.LeftNode = mainNode
tree = LeftLeftRotate(tree)
return tree
}

//右左局面
func RightLightRotate(tree *binaryTree) *binaryTree{
mainRightNode := tree.RightNode
changeNode := &binaryTree{}
mainNode := mainRightNode.LeftNode
if mainNode.RightNode != nil {
changeNode = mainNode.RightNode
}
mainRightNode.LeftNode = changeNode
mainRightNode.Height = mainRightNode.getTreeHeight()
mainNode.RightNode = mainRightNode
mainNode.Height = mainNode.getTreeHeight()
tree.RightNode = mainNode
tree = RightRightRotate(tree)
return tree
}``````

### 二叉平衡树的插入和删除

``````package main

import (
"fmt"
"math"
)

type binaryTree struct {
Value int
Height int
LeftNode *binaryTree
RightNode *binaryTree
}

func main(){
var numArr = []int{10,11,4,2,8,1,3,6,9,5,7,12}
tree := createBinaryBalanceTree(numArr)
var middle []int
tree = deleteNode(9,tree)
tree = deleteNode(11,tree)
tree = deleteNode(12,tree)
fmt.Println("\n")
middle := middleForeach(*tree,middle)
fmt.Println(middle,"\n")
}

//获取节点树高度，深度优先
func (tree binaryTree) getTreeHeight() int{
//节点无
if tree.RightNode == nil && tree.LeftNode == nil {
return 1
}
leftHeight,rightHeight := 1,1
if tree.LeftNode != nil && tree.LeftNode.Value != 0 {
leftHeight = 1 + tree.LeftNode.getTreeHeight()
}
if tree.RightNode != nil && tree.RightNode.Value != 0{
rightHeight = 1 + tree.RightNode.getTreeHeight()
}
//比较左右节点树高度
height := math.Max(float64(leftHeight),float64(rightHeight))
return int(height)
}

//检查树是否达到平衡
func (tree binaryTree) isBalance() bool {
if tree.RightNode == nil && tree.LeftNode == nil {
return true
}
//节点的平衡因子
factor := tree.getTreeFactor()
if factor > 1 || factor < -1 {
return false
}
return true
}

//获取节点的平衡因子
func (tree binaryTree) getTreeFactor() int{
leftFactor,rightFactor := 0,0
if tree.RightNode != nil {
rightFactor = tree.RightNode.getTreeHeight()
}
if tree.LeftNode != nil {
leftFactor = tree.LeftNode.getTreeHeight()
}
factor := float64(leftFactor - rightFactor)
return int(factor)
}

//创建二叉平衡树
func createBinaryBalanceTree(nums []int) *binaryTree{
tree := new(binaryTree)
for index := range nums{
node := &binaryTree{Value: nums[index]}
tree = insertNode(tree,node)
}
return tree
}

//插入节点
func insertNode(tree *binaryTree,node *binaryTree) *binaryTree {

if tree.Value == 0 {
return node
}
if tree.Value == node.Value {
return tree
}else if tree.Value > node.Value {
//往左子树走,为空则直接插入节点
if tree.LeftNode == nil {
tree.LeftNode = node
}else {
tree.LeftNode = insertNode(tree.LeftNode,node)
}
//节点高度重置
tree.LeftNode.Height = tree.LeftNode.getTreeHeight()
}else {
//往右子树走,为空则直接插入节点
if tree.RightNode == nil {
tree.RightNode = node
}else {
tree.RightNode = insertNode(tree.RightNode,node)
}
//节点高度重置
tree.RightNode.Height = tree.RightNode.getTreeHeight()
}
//节点高度重置
tree.Height = tree.getTreeHeight()
//节点不平衡
if !tree.isBalance() {
//tree = treeInsertRotateBalance(node,tree)
//左子树偏大
if tree.getTreeFactor() > 1 {
if node.Value < tree.LeftNode.Value {
tree = LeftLeftRotate(tree)
}else {
tree = LeftRightRotate(tree)
}
}else {
//右子树偏大
if node.Value > tree.RightNode.Value {
tree = RightRightRotate(tree)
}else {
tree = RightLightRotate(tree)
}
}
}
return tree
}

//删除节点
func deleteNode(num int,tree *binaryTree) *binaryTree{
//先查看删除的值是否存在树当中
find := findNode(num,tree)
if find {
//配置到节点值，执行删除操作
if tree.Value == num {
//删除的节点无左右节点
if tree.LeftNode == nil && tree.RightNode == nil {
tree = &binaryTree{}
}else if tree.LeftNode == nil && tree.RightNode != nil {
//左节点为空，右节点不为空
tree = tree.RightNode
}else if tree.RightNode == nil && tree.LeftNode != nil {
//右节点为空，左节点不为空
tree = tree.LeftNode
}else{
//节点左右节点都存在
tree = replaceNode(tree)
}
}else if tree.Value > num {
tree.LeftNode = deleteNode(num,tree.LeftNode)
}else {
tree.RightNode = deleteNode(num,tree.RightNode)
}
tree.Height = tree.getTreeHeight()
}
if !tree.isBalance() {
if tree.getTreeFactor() > 1 {
if num > tree.Value {
tree = LeftLeftRotate(tree)
}else {
tree = LeftRightRotate(tree)
}
}else {
if num < tree.Value {
tree = RightRightRotate(tree)
}else {
tree = RightLightRotate(tree)
}
}
}
return tree
}

//替换删除节点
func replaceNode(tree *binaryTree) *binaryTree{
//删除的节点无左右节点
if tree.LeftNode == nil && tree.RightNode == nil {
tree = &binaryTree{}
}else if tree.LeftNode == nil && tree.RightNode != nil {
//左节点为空，右节点不为空
tree = tree.RightNode
}else if tree.RightNode == nil && tree.LeftNode != nil {
//右节点为空，左节点不为空
tree = tree.LeftNode
}else{
//节点左右节点都存在，则从右子树查找节点替代父节点
//若右节点下没有左右节点,则直接用右节点的值替换，并删除右节点
if tree.RightNode.LeftNode == nil && tree.RightNode.RightNode == nil {
tree.Value = tree.RightNode.Value
tree.RightNode = &binaryTree{}
}else if tree.RightNode.LeftNode == nil && tree.RightNode.RightNode != nil {
//若右节点下左节点为空，右节点不为空，则右节点的值替换，并将右节点的右节点替换过来
tree.Value = tree.RightNode.Value
tree.RightNode = tree.RightNode.RightNode
}else{
//若右节点的左节点不为空
tree.Value = tree.RightNode.LeftNode.Value
tree.RightNode.LeftNode = replaceNode(tree.RightNode.LeftNode)
}
}
return tree
}

//左左局面
func LeftLeftRotate(tree *binaryTree) *binaryTree{
//原节点左节点成为根节点
mainNode := tree.LeftNode
changeNode := &binaryTree{}
//判断原节点左节点是否存在
if mainNode.RightNode != nil {
changeNode = mainNode.RightNode
}
mainRightNode := tree
mainRightNode.LeftNode = changeNode
//刷新树高度
mainRightNode.Height = mainRightNode.getTreeHeight()
mainNode.RightNode = mainRightNode
mainNode.Height = mainNode.getTreeHeight()
return mainNode
}

//右右局面
func RightRightRotate(tree *binaryTree) *binaryTree{
mainNode := tree.RightNode
changeNode := &binaryTree{}
if mainNode.LeftNode != nil {
changeNode = mainNode.LeftNode
}
mainLeftNode := tree
mainLeftNode.RightNode = changeNode
mainLeftNode.Height = mainLeftNode.getTreeHeight()
mainNode.LeftNode = mainLeftNode
mainNode.Height = mainNode.getTreeHeight()
return mainNode
}

//左右局面
func LeftRightRotate(tree *binaryTree) *binaryTree{
mainLeftNode := tree.LeftNode
changeNode := &binaryTree{}
mainNode := mainLeftNode.RightNode
if mainNode.LeftNode != nil {
changeNode = mainNode.LeftNode
}
mainLeftNode.RightNode = changeNode
mainLeftNode.Height = mainLeftNode.getTreeHeight()
mainNode.LeftNode = mainLeftNode
mainNode.Height = mainNode.getTreeHeight()
tree.LeftNode = mainNode
tree = LeftLeftRotate(tree)
return tree
}

//右左局面
func RightLightRotate(tree *binaryTree) *binaryTree{
mainRightNode := tree.RightNode
changeNode := &binaryTree{}
mainNode := mainRightNode.LeftNode
if mainNode.RightNode != nil {
changeNode = mainNode.RightNode
}
mainRightNode.LeftNode = changeNode
mainRightNode.Height = mainRightNode.getTreeHeight()
mainNode.RightNode = mainRightNode
mainNode.Height = mainNode.getTreeHeight()
tree.RightNode = mainNode
tree = RightRightRotate(tree)
return tree
}

//节点查找
func findNode(num int,tree *binaryTree) bool{
targetNode := tree
for targetNode != nil{
if targetNode.Value == num {
return true
}else if targetNode.Value > num {
targetNode = targetNode.LeftNode
}else {
targetNode = targetNode.RightNode
}
}
return false
}

//中序遍历
func middleForeach(tree binaryTree,num []int) []int{
var leftNum,rightNum []int
//若存在左节点，遍历左节点树
if tree.LeftNode != nil {
leftNum = middleForeach(*tree.LeftNode,leftNum)
for _,value := range leftNum{
num = append(num,value)
}
}

//先遍历根节点
if tree.Value != 0 {
num = append(num,tree.Value)
}

//若存在右节点，遍历右节点树
if tree.RightNode != nil {
rightNum = middleForeach(*tree.RightNode,rightNum)
for _,value := range rightNum{
num = append(num,value)
}
}

return num
}
``````

(=￣ω￣=)··· 暂无内容！

43

30

163

313