本文源码地址: https://github.com/zboyco/go-test/blob/master/findtree/main.go

二叉查找树

树有多种不同的结构，但都是由节点构成，一颗树至少有一个根节点，节点下有子节点，没有子节点的节点称为叶子；
二叉树指每一个树节点都最多有两个子节点的树，两个子节点分别称为左节点和右节点；
二叉查找树则是指每一个节点的左节点的值都小于当前节点的值，右节点的值都大于或等于当前节点的值。

0. 节点定义

二叉树的节点由三个属性构成，值、左节点指针和右节点指针：

type TreeNode struct {
	Value     int
	LeftNode  *TreeNode
	RightNode *TreeNode
}

1. 生成

1.1 思路

因为二叉查找树的特性，每一个节点都可以看成是一棵树的根节点，所以我们采用递归的方式构建一颗树：
a. 一个新值进入
b. 判断当前节点时候存在
b.1 若不存在就新建一个节点，并赋值给当前节点（本次新值已经找到位置，赋值结束）；
b.2 若存在就比较新值与当前节点值大小
b.2.1 小于当前节点值则把新值传入左节点
b.2.2 否则传入右节点

当值传入左节点或者右节点的时候，对于传入的节点，又回到了步骤a，这样就形成了一个递归循环，下面我们用代码实现这个递归过程.

1.2 实现递归

func (node *TreeNode) pushValue(value int) *TreeNode {
	if node == nil {
		node = &TreeNode{
			Value: value,
		}
	} else {
		if value <= node.Value {
			node.LeftNode = node.LeftNode.pushValue(value)
		} else {
			node.RightNode = node.RightNode.pushValue(value)
		}
	}
	return node
}

方法返回一个节点指针，是因为当前节点有可能为nil，需要将当前节点的指针返回并重新赋值给当前节点.

1.3 使用方法

假如有一个切片，要生成一个查找二叉树，我们只需要新建一个根节点，然后遍历这个切片，往这个根节点中推值即可，如下：

// NewTree 新建树
func NewTree(values ...int) (*TreeNode, error) {
	if len(values) <= 0 {
		return nil, errors.New("length error")
	}
	var rootNode *TreeNode
	for i := range values {
		rootNode = rootNode.pushValue(values[i])
	}
	return rootNode, nil
}

arr := []int{10, 9, 20, 35, 15}
tree, err := NewTree(arr...)

2. 遍历

二叉查找树的遍历有三种顺序：
先序遍历：先遍历当前节点值，再遍历左节点值，最后遍历右节点值；
中序遍历：先遍历左节点值，再遍历当前节点值，最后遍历右节点值；
后序遍历：先遍历左节点值，再遍历右节点值，最后遍历当前节点值；

前提：当前节点不为空(!= nil)

2.1 思路

三种遍历的顺序基本上就是遍历的思路了，所以代码比较简单，直接上代码了。

2.2 实现

先序：

// FrontForeach 先序遍历
func (node *TreeNode) FrontForeach() {
	if node == nil {
		return
	}
	fmt.Printf("%v ", node.Value)
	node.LeftNode.FrontForeach()
	node.RightNode.FrontForeach()
}

中序:

// MidForeach 中序遍历
func (node *TreeNode) MidForeach() {
	if node == nil {
		return
	}
	node.LeftNode.MidForeach()
	fmt.Printf("%v ", node.Value)
	node.RightNode.MidForeach()
}

后序:

// BehindForeach 后续遍历
func (node *TreeNode) BehindForeach() {
	if node == nil {
		return
	}
	node.LeftNode.BehindForeach()
	node.RightNode.BehindForeach()
	fmt.Printf("%v ", node.Value)
}

2.3 使用方法

arr := []int{10, 9, 20, 35, 15}
tree, err := NewTree(arr...)
if err != nil {
	fmt.Println(err)
	return
}
tree.FrontForeach()
fmt.Println()
tree.MidForeach()
fmt.Println()
tree.BehindForeach()

输出：

1
2
3

10 9 20 15 35
9 10 15 20 35
9 15 35 20 10

3. 深度计算

深度指从根节点开始，到所有叶子的路径中层级最多的这个层数，就是这棵树的深度。

3.1 思路

a. 如果一个节点为空，那么深度肯定就是0了；
b. 如果这个节点不为空，那么深度就是深度较大的子节点的深度+1（把每个子节点看作一个根节点递归，子节点为空，所以子节点深度为0）。

3.2 实现

实现方法比较简单：

// GetHeight 获取深度
func (node *TreeNode) GetHeight() int {
	if node == nil {
		return 0
	}
	left := node.LeftNode.GetHeight()
	right := node.RightNode.GetHeight()

	if left < right {
		return right + 1
	} else {
		return left + 1
	}
}

4. 最大值

获取二叉查找树中的最大值.

4.1 思路

同求深度的思路相似，只需要把左右节点看作根节点，分别计算最大值，再用左节点最大值、右节点最大值和当前节点值进行比较，返回最大值即可.

4.2 实现

// GetMax 获取最大值
func (node *TreeNode) GetMax() (int, error) {
	if node == nil {
		return 0, errors.New("none")
	}
	max := node.Value
	left, err := node.LeftNode.GetMax()
	if err == nil && max < left {
		max = left
	}
	right, err := node.RightNode.GetMax()
	if err == nil && max < right {
		max = right
	}
	return max, nil
}

5. 最小值

同最大值

// GetMin 获取最小值
func (node *TreeNode) GetMin() (int, error) {
	if node == nil {
		return 0, errors.New("none")
	}
	min := node.Value
	left, err := node.LeftNode.GetMax()
	if err == nil && min > left {
		min = left
	}
	right, err := node.RightNode.GetMax()
	if err == nil && min > right {
		min = right
	}
	return min, nil
}

6. 测试

func main() {
	arr := []int{10, 9, 20, 35, 15}
	tree, err := NewTree(arr...)
	if err != nil {
		fmt.Println(err)
		return
	}
	tree.FrontForeach()
	fmt.Println()
	tree.MidForeach()
	fmt.Println()
	tree.BehindForeach()
	fmt.Println()
	fmt.Print("当前树深度: ")
	fmt.Println(tree.GetHeight())
	fmt.Print("当前树最大值: ")
	fmt.Println(tree.GetMax())
	fmt.Print("当前树最小值: ")
	fmt.Println(tree.GetMin())
}

输出:

❯ go run main.go
10 9 20 15 35
9 10 15 20 35
9 15 35 20 10
当前树深度: 3
当前树最大值: 35 <nil>
当前树最小值: 9 <nil>

白羊的空间

二叉查找树的一些操作方法