Go實現(xiàn)的二叉搜索樹

二叉搜索樹(BST)是一種極重要的數(shù)據(jù)結(jié)構(gòu)，它由淺及深，覆蓋了數(shù)據(jù)結(jié)構(gòu)與算法中的許多問題。本文出于實踐Go編程的目的，用Go實現(xiàn)BST，這里先做一個初步的實現(xiàn)，暫時不考慮樹的平衡性，不實現(xiàn)刪除樹節(jié)點。

首先定義BST的結(jié)構(gòu)，這里體現(xiàn)Go優(yōu)越性的地方來了。由于Go對每一個基礎數(shù)據(jù)類型都定義了一個初始零值，如int型為0，指針*TreeNode為nil，我們不用寫繁雜的構(gòu)造函數(shù)來生成新節(jié)點。

type TreeNode struct {
    Left, Right *TreeNode
    Key         int
}

type Tree struct {
    Root *TreeNode
    Num  int
}

func NewTree() (t *Tree) {
    t = &Tree{}
    return
}

BST由于其數(shù)據(jù)組織特性，大量的方法可以天然地使用遞歸實現(xiàn)。遞歸實現(xiàn)過于直觀，這里就不重復了。遞歸函數(shù)都可以利用迭代實現(xiàn)，而且遞歸需要占用函數(shù)調(diào)用棧，一旦遞歸層數(shù)過多，容易出現(xiàn)棧溢出，因此，對于數(shù)據(jù)量多的輸入，迭代實現(xiàn)才是可靠的。
首先用實現(xiàn)插入節(jié)點，插入節(jié)點要保證BST的節(jié)點順序，Key(left) < Key(root) < Key(Right)。首先找到一個葉子節(jié)點，然后將新建節(jié)點鏈接在葉子節(jié)點上。

/*iterative insert new key into tree*/
func (t *Tree) Insert(val int) {
    node := &TreeNode{Key: val}
    if t.Root == nil {
        t.Root = node
        t.Num++
        return
    } //create root

    //find the parent node to host new one
    var cur, parent *TreeNode = t.Root, nil
    for cur != nil {
        parent = cur
        if val < cur.Key {
            cur = cur.Left
        } else {
            cur = cur.Right
        }
    }

    //link the new node to the tree
    if parent == nil {
        panic("corrupt tree") //parent = node
    } else if val < parent.Key {
        parent.Left = node
    } else if val > parent.Key {
        parent.Right = node
    }
    t.Num++
}

對比一下插入節(jié)點的遞歸實現(xiàn)

/*recursively insert new key into tree*/
func (t *Tree) InsertRecur(val int) {
    t.Root = insert(t.Root, val)
}

func insert(root *TreeNode, val int) *TreeNode {
    if root == nil {
        return &TreeNode{Key: val}
    }

    if val < root.Key {
        root.Left = insert(root.Left, val)
    } else if val > root.Key {
        root.Right = insert(root.Right, val)
    }
    return root
}

然后用迭代實現(xiàn)BST的幾種遍歷方法，中序遍歷，前序遍歷，后序遍歷和按層遍歷。
中序遍歷輸出的是順序的鍵值數(shù)組，中序遍歷利用一個棧來實現(xiàn)，從根節(jié)點開始，從上向下，依次將左子節(jié)點壓入棧，直到左子節(jié)點為空。隨后彈出棧頂，首先訪問的節(jié)點為最左子節(jié)點。訪問完根節(jié)點后，再將右子樹按同樣方式訪問。

/*iterative in-order traversal*/
func (t *Tree) Inorder() (out []int) {
    if t.Root == nil {
        return
    }

    var stack []*TreeNode
    curr := t.Root

    for true {
        for curr != nil {
            stack = append(stack, curr)
            curr = curr.Left
        }

        if len(stack) > 0 {
            curr = stack[len(stack)-1]
            stack = stack[:len(stack)-1]
            out = append(out, curr.Key)
        }

        curr = curr.Right
        if curr == nil && len(stack) == 0 {
            break
        }
    }
    return
}

前序遍歷最先訪問的是根節(jié)點，然后是左子樹和右子樹，因此可以用隊列來實現(xiàn)。

/*iterative pre-order traversal*/
func (t *Tree) Preorder() (out []int) {
    if t.Root == nil {
        return
    }

    queue := []*TreeNode{t.Root}
    for len(queue) > 0 {
        curr := queue[0]
        queue = queue[1:]

        out = append(out, curr.Key)

        if curr.Left != nil {
            queue = append(queue, curr.Left)
        }
        if curr.Right != nil {
            queue = append(queue, curr.Right)
        }
    }

    return
}

后序遍歷的遞歸實現(xiàn)比前序和中序更復雜，可以用兩個棧實現(xiàn)。在棧1中，將節(jié)點按照根->左->右的順序壓棧，同時將根壓入棧2，最后將棧2推出，即為后序遍歷結(jié)果。

/*iterative post-order traversal with two stacks*/
func (t *Tree) Postorder() (out []int) {
    if t.Root == nil {
        return
    }

    var stack1, stack2 []*TreeNode
    stack1 = append(stack1, t.Root)
    for len(stack1) > 0 {
        curr := stack1[len(stack1)-1]
        stack1 = stack1[:len(stack1)-1]
        stack2 = append(stack2, curr)

        if curr.Left != nil {
            stack1 = append(stack1, curr.Left)
        }
        if curr.Right != nil {
            stack1 = append(stack1, curr.Right)
        }
    }

    for len(stack2) > 0 {
        curr := stack2[len(stack2)-1]
        stack2 = stack2[:len(stack2)-1]
        out = append(out, curr.Key)
    }

    return
}

層序遍歷利用的是BFS，廣度優(yōu)先搜索。利用隊列，每次訪問完一層，同時將下一層的節(jié)點入隊。

/*iterative level-order traversal with BFS*/
func (t *Tree) LevelOrder() (out [][]int) {
    if t.Root == nil {
        return
    }

    queue := []*TreeNode{t.Root}
    level := 0
    for len(queue) > 0 {
        size := len(queue)
        if size > 0 {
            out = append(out, []int{})
        } //allocate array to store next level
        for ; size > 0; size-- {
            curr := queue[0]
            queue = queue[1:]
            out[level] = append(out[level], curr.Key) //travers node of current level

            //put next level nodes into queue
            if curr.Left != nil {
                queue = append(queue, curr.Left)
            }
            if curr.Right != nil {
                queue = append(queue, curr.Right)
            }
        }
        level++ //increase level
    }

    return
}

本文沒有實現(xiàn)平衡搜索樹，但是BST的平衡性對搜索效率的影響很大，這里實現(xiàn)方法來檢測樹的平衡性，并且利用重構(gòu)BST來平衡。

/*get the height of tree in recursively manner*/
func getHeightRecur(root *TreeNode) int {
    if root == nil {
        return 0
    }
    if root.Left == nil && root.Right == nil {
        return 1
    }
    return Max(getHeightRecur(root.Left), getHeightRecur(root.Right)) + 1
}

/*check if tree is balanced in recursively manner*/
func (t *Tree) IsBalancedRecur() bool {
    if t.Root == nil {
        return true
    }
    return Abs(getHeightRecur(t.Root.Left)-getHeightRecur(t.Root.Right)) < 1
}

/*create and link tree node for a balanced tree*/
func buildBalancedTree(keys []int, start, end int) (root *TreeNode) {
    if start < end {
        return
    }

    mid := start + (end-start)/2
    root = &TreeNode{Key: keys[mid]}
    root.Left = buildBalancedTree(keys, start, mid-1)
    root.Right = buildBalancedTree(keys, mid+1, end)
    return
}

/*rebuild the tree to make it balanced*/
func (t *Tree) MakeBalancedRecur() {
    keys := t.Inorder()
    t.Root = buildBalancedTree(keys, 0, len(keys)-1)
}

最后添加測試用例來進行檢驗

func TreeTest(n int) {
    nums := []int{3, 4, 6, 2, 1, 5}
    tree := NewTree()
    for _, n := range nums {
        tree.Insert(n)
    }
    //visit := tree.Inorder()
    fmt.Println("#", n, "TreeTest", tree.Num)
    fmt.Println("pre-order", tree.Preorder())
    fmt.Println("in-order", tree.Inorder())
    fmt.Println("post-order", tree.Postorder())
    fmt.Println("level-order", tree.LevelOrder())
}

代碼清單：

https://github.com/KevinACoder/Learning/blob/master/ds_go/kit/tree.go

最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時請結(jié)合常識與多方信息審慎甄別。
平臺聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點，簡書系信息發(fā)布平臺，僅提供信息存儲服務。

相關閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容