二叉查找树,又叫二叉排序树,二叉搜索树,是一种有特定规则的二叉树,定义如下
- 它是一棵二叉树,或者是空树
- 左子树所有节点的值都小于它的根节点,右子树所有节点的值都大于它的根节点
- 左右子树也是一棵二叉查找树
以下是GO语言实现的完整代码
package main import ( "fmt" ) //二叉搜索树节点 type Searc2TreeNode struct { Value int Left *Searc2TreeNode Right *Searc2TreeNode } //添加节点 func (n *Searc2TreeNode) Add(val int) { if val > n.Value { if n.Right == nil { n.Right = &Searc2TreeNode{Value: val} } else { n.Right.Add(val) } } else if val < n.Value { if n.Left == nil { n.Left = &Searc2TreeNode{Value: val} } else { n.Left.Add(val) } } else { fmt.Println(val, "已经存在") } } //遍历节点 func (n *Searc2TreeNode) View(vType string) { if vType != "first" && vType != "last" && vType != "mid" { fmt.Println("参数不合法") } else if vType == "first" { //先序遍历 fmt.Print(n.Value, " ") if n.Left != nil { n.Left.View(vType) } if n.Right != nil { n.Right.View(vType) } } else if vType == "mid" { //中序遍历 if n.Left != nil { n.Left.View(vType) } fmt.Print(n.Value, " ") if n.Right != nil { n.Right.View(vType) } } else { //后序遍历 if n.Left != nil { n.Left.View(vType) } if n.Right != nil { n.Right.View(vType) } fmt.Print(n.Value, " ") } } //查找节点 func (n *Searc2TreeNode) Find(val int) *Searc2TreeNode { if n.Value == val { return n } if n.Left != nil && val < n.Value { return n.Left.Find(val) } if n.Right != nil && val > n.Value { return n.Right.Find(val) } return nil } //查找父节点 func (n *Searc2TreeNode) FindParent(val int) *Searc2TreeNode { if n.Left != nil && val < n.Value { if n.Left.Value == val { return n } else { return n.Left.FindParent(val) } } if n.Right != nil && val > n.Value { if n.Right.Value == val { return n } else { return n.Right.FindParent(val) } } return nil } //二叉搜索树 type Searc2Tree struct { Root *Searc2TreeNode } //添加节点 func (t *Searc2Tree) Add(val int) { if t.Root == nil { t.Root = &Searc2TreeNode{Value: val} } else { t.Root.Add(val) } } //遍历节点 func (t *Searc2Tree) View(vType string) { if t.Root != nil { t.Root.View(vType) } else { fmt.Println("root is empty") } fmt.Println("") } //查找节点 func (t *Searc2Tree) Find(val int) *Searc2TreeNode { if t.Root != nil { return t.Root.Find(val) } else { return nil } } //查找父节点 func (t *Searc2Tree) FindParent(val int) *Searc2TreeNode { if t.Root != nil { return t.Root.FindParent(val) } else { return nil } } //删除节点 func (t *Searc2Tree) Delete(val int) bool { if t.Root != nil { node := t.Find(val) if node == nil { return false } else { nodeParent := t.FindParent(val) if nodeParent == nil && node.Left == nil && node.Right == nil { //如果是根节点,且只有根节点 t.Root = nil return true } else if node.Left == nil && node.Right == nil { //删除的节点有父亲节点,但没有子树 if nodeParent.Left != nil && val == nodeParent.Left.Value { //左子树 nodeParent.Left = nil } else { //右子树 nodeParent.Right = nil } return true } else if node.Left != nil && node.Right != nil { //删除的节点下有两个子树,因为右子树的值都比左子树大,那么用右子树中的最小元素来替换删除的节点,这时二叉查找树的性质又满足了。 // 找右子树中最小的值,一直往右子树的左边找 minNode := node.Right for minNode.Left != nil { minNode = minNode.Left } // 把最小的节点删掉 t.Delete(minNode.Value) // 最小值的节点替换被删除节点 node.Value = minNode.Value return true } else { //只有一个子树,那么该子树直接替换被删除的节点即可 // 父亲为空,表示删除的是根节点,替换树根 if nodeParent == nil { if node.Left != nil { t.Root = node.Left } else { t.Root = node.Right } return true } // 左子树不为空 if node.Left != nil { // 如果删除的是节点是父亲的左儿子,让删除的节点的左子树接班 if nodeParent.Left != nil && val == nodeParent.Left.Value { nodeParent.Left = node.Left } else { nodeParent.Right = node.Left } } else { // 如果删除的是节点是父亲的左儿子,让删除的节点的右子树接班 if nodeParent.Left != nil && val == nodeParent.Left.Value { nodeParent.Left = node.Right } else { nodeParent.Right = node.Right } } return true } } return false } else { return false } } func main() { values := []int{5, 2, 7, 3, 6, 1, 4, 8, 9} tree := new(Searc2Tree) for _, v := range values { tree.Add(v) } tree.View("first") tree.View("mid") tree.View("last") }
二叉查找树可能退化为链表,也可能是一棵非常平衡的二叉树,查找,添加,删除元素的时间复杂度取决于树的高度h。