二叉搜索树之构建

二叉搜索树

二叉搜索树（BST）又叫二叉查找树（Binary Sort Tree），它是一种树型结构，具有如下特征：

• 若它的左子树不为空，则左子树上所有结点的值均小于它的根结点的值；
• 若它的右子树不为空，则右子树上所有结点的值均大于它的根结点的值
• 它的左、右子树分别为二叉排序树
• 没有键值相等的节点

设计这样的结构主要是为了提高查找速度（时间复杂度可以达到 O(logN)）。

创建 BST

package main

import "fmt"

type TreeNode struct {
    data   int
    lChild *TreeNode
    rChild *TreeNode
}

const MaxUint = ^uint(0)
const MinUint = 0
const MaxInt = int(MaxUint >> 1)
const MinInt = -MaxInt - 1

type BST struct {Root *TreeNode // 根节点指针}

func (this *BST) Insert(item int) bool {return this.insertItem(&this.Root, item)
}

func (this *BST) insertItem(pp **TreeNode, item int) bool {
    p := *pp
    if p == nil {
        *pp = &TreeNode{
            data:   item,
            lChild: nil,
            rChild: nil,
        }
        return true
    } else if item == p.data {return false} else if item < p.data {return this.insertItem(&((*pp).lChild), item) // 添加到左子树
    } else {return this.insertItem(&((*pp).rChild), item) // 添加到右子树
    }
}

func (this *BST) Display() {this.displayBST(this.Root)
}

func (this *BST) displayBST(p *TreeNode) {
    if p != nil {fmt.Printf("%d", p.data)
        if p.lChild != nil || p.rChild != nil {fmt.Print("(")
            this.displayBST(p.lChild)
            if p.rChild != nil {fmt.Print(",")
                this.displayBST(p.rChild)
            }
            fmt.Print(")")
        }
    }
}

func (this *BST) Create(nums []int) {
    for idx, item := range nums {if this.Insert(item) {fmt.Printf("第 %d 步，插入 %d：", idx+1, item)
            this.Display()
            fmt.Print("\n")
        }
    }
}

上述程序根据传入的 nums 数组构建 BST

测试

func main() {arr := []int{4, 9, 0, 1, 8, 6, 3, 5, 2, 7}
    bst := BST{nil}
    fmt.Println("创建一颗 BST 树")
    bst.Create(arr)
}

输出

创建一颗 BST 树
第 1 步，插入 4：4
第 2 步，插入 9：4(,9)
第 3 步，插入 0：4(0,9)
第 4 步，插入 1：4(0(,1),9)
第 5 步，插入 8：4(0(,1),9(8))
第 6 步，插入 6：4(0(,1),9(8(6)))
第 7 步，插入 3：4(0(,1(,3)),9(8(6)))
第 8 步，插入 5：4(0(,1(,3)),9(8(6(5))))
第 9 步，插入 2：4(0(,1(,3(2))),9(8(6(5))))
第 10 步，插入 7：4(0(,1(,3(2))),9(8(6(5,7))))