去二进制搜索树

二叉搜索树（BST）是一个非常重要的数据结构，它涵盖了浅层和深层，涵盖了数据结构和算法中的许多问题. 为了练习Go编程，本文使用Go来实现BST. 这是一个初步的实现，它不考虑树的平衡并且不删除树节点.

首先定义BST的结构，这就是Go的优势所在. 由于Go为每种基本数据类型定义了初始零值，例如int类型为0，指针* TreeNode为nil二叉排序树实现，所以我们不需要编写复杂的构造函数以生成新节点.

type TreeNode struct {
    Left, Right *TreeNode
    Key         int
}
type Tree struct {
    Root *TreeNode
    Num  int
}
func NewTree() (t *Tree) {
    t = &Tree{}
    return
}

BST由于其数据组织特性，因此可以自然地使用递归来实现许多方法. 递归实现过于直观，因此在此不再赘述. 可以使用迭代来实现所有递归函数，并且递归需要占用函数调用堆栈. 一旦递归层过多，就很容易发生堆栈溢出. 因此，对于具有大数据量的输入，迭代实现是可靠的.

首先，插入节点以实现BST的节点顺序二叉排序树实现，即Key（左）

/*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++
}

比较插入节点的递归实现

/*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
}

然后迭代地实现BST，中阶遍历，前阶遍历，后阶遍历和逐层遍历的几种遍历方法.

中阶遍历的输出是键值数组的序列. 中间顺序遍历是使用堆栈来实现的，该堆栈从根节点开始，从上到下，依次将左子节点推入堆栈，直到左子节点为空. 然后弹出栈顶，访问的第一个节点是最左边的子节点. 访问根节点后，以相同的方式访问正确的子树.

/*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
}

预遍历首先访问根节点，然后访问左右子树，因此可以使用队列来实现.

/*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
}

后顺序遍历的递归实现比前顺序和中顺序更复杂，并且可以使用两个堆栈来实现. 在堆栈1中，按照root-> left-> right的顺序将节点压入堆栈，同时将根压入堆栈2，最后将堆栈2压出，结果是后遍历.

/*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，即广度优先搜索. 使用队列，每次访问图层时，您都将加入下一层的节点.

/*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
}

本文没有实现平衡的搜索树，但是BST的平衡对搜索效率有很大的影响. 这里我们实现了一种检测树平衡的方法，并使用重建的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://www.pc-fly.com/a/jisuanjixue/article-220573-1.html