数据结构之实现二叉查找树

学习极客时间《数据结构与算法之美》二叉查找树章节，实现一个基础的二叉查找树。

二叉查找树的特点是树中的任一节点，其左子树的每个节点的值，都要小于这个节点的值，而右子树的每个节点的值，都要大于等于这个节点的值，下面是示例图。

构建好的二叉查找树，对其进行中序遍历，可以输出有序的数据序列，时间复杂度为 O(n)。

散列表的查询复杂度为 O(1)，而平衡二叉查找树的复杂度为 O(logn)，为什么还需要平衡二叉查找树呢？通过下面对比可能得到答案。

平衡二叉查找树与散列表对比：

对比项	散列表	平衡二叉查找树
有序性	无序	中序遍历输出有序数据
扩容	扩容消耗时间	无需考虑扩容问题
空间	装载因子导致内存利用率低	指针占用额外空间
性能	哈希函数和散列冲突，速度不稳定	稳定为 O(logn)
复杂性	散列函数设计，扩容，缩容等	只需考虑平衡性

下面代码供参考：

package main

import (
	"fmt"
	"math"
)

type tree struct {
	value int
	left  *tree
	right *tree
}

var root *tree

func main() {

	// 构建二叉查找树
	data := []int{6, 1, 4, 2, 8, 7, 3, 5, 9, 0, 4}
	for _, v := range data {
		insertNode(v)
	}

	inOrder(root)                // 中序遍历二叉树
	fmt.Println(findNode(4))     // 查找存在的节点
	fmt.Println(findNode(11))    // 查找不存在的节点
	fmt.Println(treeLevel(root)) // 获取树的层数
	fmt.Println(minNode())       // 获取最小节点
	fmt.Println(maxNode())       // 获取最大接待您
	deleteNode(4)                // 删除节点
	inOrder(root)                // 中序遍历二叉树
}

// insertNode 插入节点
func insertNode(value int) {
	if root == nil {
		root = &tree{value, nil, nil}
		return
	}

	t := root
	for {
		if value < t.value {
			if t.left == nil {
				t.left = &tree{value, nil, nil}
				break
			}
			t = t.left
		} else {
			if t.right == nil {
				t.right = &tree{value, nil, nil}
				break
			}
			t = t.right
		}
	}
}

// findNode 查找节点
func findNode(value int) *tree {
	t := root
	for t != nil {
		if value < t.value {
			t = t.left
		} else if value > t.value {
			t = t.right
		} else {
			return t
		}
	}
	return nil
}

// deleteNodeOriginCode 删除节点，未将子节点处理逻辑进行合并
func deleteNodeOriginCode(value int) bool {
	t := root         // 指向要删除的节点
	var parentT *tree // 指向要删除节点的父节点
	for t != nil && t.value != value {
		parentT = t
		if value < t.value {
			t = t.left
		} else {
			t = t.right
		}
	}
	if t == nil {
		return false
	}

	if t.left != nil && t.right != nil {
		// 如果待删除节点的两个子节点都是非空节点
		// 那么寻找此节点的右子树中最小的节点替换此节点
		minT := t.right
		minParentT := t // minT 节点的父节点
		for minT.left != nil {
			minParentT = minT
			minT = minT.left
		}
		t.value = minT.value // 将右子树最小节点的数据替换到要被删除的节点中
		// 如果 minT 有右子节点，那么就用此右子节点代替 minT
		// 否则如果 minT 是 minParentT 节点的右子节点，说明 minT 就是待删除节点的右子节点
		// 如果 minT 是 minParentT 节点的左子节点，说明其是最终的叶子节点，删除即可
		if minT.right != nil {
			minParentT.left = minT.right
		} else {
			if minParentT.right == minT {
				minParentT.right = nil
			}
			if minParentT.left == minT {
				minParentT.left = nil
			}
		}
	} else if t.left == nil && t.right == nil {
		// 如果待删除节点的两个子节点都是空节点
		// 则将其父节点指向置为空
		if parentT == nil {
			root = nil
		}
		if parentT.left == t {
			parentT.left = nil
		}
		if parentT.right == t {
			parentT.right = nil
		}
	} else if (t.left == nil && t.right != nil) || (t.left != nil && t.right == nil) {
		// 如果待删除节点的两个子节点有一个是空节点
		// 则将非空子节点取代待删除节点
		var childT *tree
		if t.left != nil {
			childT = t.left
		}
		if t.right != nil {
			childT = t.right
		}
		if parentT == nil {
			parentT = childT
		}
		if parentT.left == t {
			parentT.left = childT
		}
		if parentT.right == t {
			parentT.right = childT
		}
	}
	return deleteNodeOriginCode(value)
}

// deleteNode 删除节点，将子节点处理逻辑进行合并
func deleteNode(value int) bool {
	t := root         // 指向要删除的节点
	var parentT *tree // 指向要删除节点的父节点
	for t != nil && t.value != value {
		parentT = t
		if value < t.value {
			t = t.left
		} else {
			t = t.right
		}
	}
	if t == nil {
		return false
	}

	// 如果待删除节点的两个子节点都是非空节点，那么寻找此节点的右子树中最小的节点替换此节点
	if t.left != nil && t.right != nil {
		minT := t.right
		minParentT := t // minT 节点的父节点
		for minT.left != nil {
			minParentT = minT
			minT = minT.left
		}
		t.value = minT.value // 将右子树最小节点的数据替换到要被删除的节点中
		t = minT             // minT 开始 minT 删除操作
		parentT = minParentT
	}

	// 删除节点是叶子节点或者仅有一个子节点
	// 那么就取到这个节点，用于替换被删除的节点
	var childT *tree
	if t.left != nil {
		childT = t.left
	} else if t.right != nil {
		childT = t.right
	} else {
		childT = nil
	}

	if parentT == nil { // 删除的是根节点
		root = childT
	} else if parentT.left == t {
		parentT.left = childT
	} else {
		parentT.right = childT
	}

	return deleteNode(value)
}

// treeLevel 获取树的层数
func treeLevel(root *tree) float64 {
	if root == nil {
		return 0
	}
	leftLevel := treeLevel(root.left)
	rightLevel := treeLevel(root.right)
	return math.Max(leftLevel, rightLevel) + 1
}

// minNode 寻找最小节点
func minNode() *tree {
	t := root
	for {
		if t.left == nil {
			return t
		}
		t = t.left
	}
}

// maxNode 寻找最大节点
func maxNode() *tree {
	t := root
	for {
		if t.right == nil {
			return t
		}
		t = t.right
	}
}

func inOrder(t *tree) {
	if t == nil {
		return
	}
	inOrder(t.left)
	fmt.Printf("%d ", t.value)
	inOrder(t.right)
}