在计算机科学中,二叉树是每个结点最多有两个子树的树结构。通常子树被称作“左子树”(left subtree)和“右子树”(right subtree)。二叉树常被用于实现二叉查找树和二叉堆。

一棵深度为k,且有2^k-1个节点的二叉树,称为满二叉树。这种树的特点是每一层上的节点数都是最大节点数。而在一棵二叉树中,除最后一层外,若其余层都是满的,并且最后一层或者是满的,或者是在右边缺少连续若干节点,则此二叉树为完全二叉树。具有n个节点的完全二叉树的深度为floor(log2n)+1。深度为k的完全二叉树,至少有2k-1个叶子节点,至多有2k-1个节点。

Binary Tree

  • 二叉树即是每个节点最多包含左子节点与右子节点这两个节点的树形数据结构。
  • 满二叉树: 树中的每个节点仅包含 0 或 2 个节点。
  • 完美二叉树(Perfect Binary Tree): 二叉树中的每个叶节点都拥有两个子节点,并且具有相同的高度。
  • 完全二叉树: 除最后一层外,每一层上的结点数均达到最大值;在最后一层上只缺少右边的若干结点

Binary Search Tree

  • 二叉搜索树(BST)是一种特殊的二叉树,其任何节点中的值都会大于或者等于其左子树中存储的值并且小于或者等于其右子树中存储的值。
  • 时间复杂度:

    • 索引: O(log(n))
    • 搜索: O(log(n))
    • 插入: O(log(n))
    • 删除: O(log(n))

二叉搜索树数据结构将公开这些方法:

  • Insert(t) 在树中插入Item t
  • Search(t) 如果Item t存在于树中,则返回true
  • InOrderTraverse() 通过后续遍历访问所有节点
  • PreOrderTraverse() 通过先序遍历访问所有节点
  • PostOrderTraverse() 通过中序遍历访问所有节点
  • Min() 返回存储在树中的最小值的Item
  • Max()返回存储在树中的具有最大值的Item
  • Remove(t) 从树中删除Item t
  • String() 打印树

我将创建一个BinarySearchTree通用类型,并发安全,可以生成包含任何类型的树,创建特定于类型的树实现,封装包含数据的实际值特定数据结构。

我将每个TreeNode定义为

type TreeNode struct {
    key   int
    value Item
    left  *TreeNode
    right *TreeNode
}

键值value允许使用任何类型的Item类型,并使用单独的值来计算正确的位置。键值value我用的是整数,但它可以采用任何可以比较的类型。

将Item插入树中需要使用递归,因为我们需要为它找到正确的位置。规则是: 如果节点的键<当前节点树的键,我们将它作为左子节点,如果没有左子节点。否则,我们使用左子节点作为基节点重新计算位置。对于子节点也一样。

我们实现了3种遍历二叉搜索树的方法。

二叉搜索树如图:

tree.png

遍历方法

  • 后续遍历:即左-右-根遍历。在上图中:1 -> 3 -> 2 -> 5 -> 7 -> 6 -> 4 -> 9 -> 11 -> 10 -> 8
  • 先序遍历:即根-左-右遍历。在上图中:8 -> 4 -> 2 -> 1 -> 3 -> 6 -> 5 -> 7 -> 10 -> 9 -> 11
  • 中序遍历:即左-根-右遍历。在上图中:1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10 -> 11

代码实现

import (
    "fmt"
    "sync"
)

type TreeNode struct {
    key   int
    value Item
    left  *TreeNode
    right *TreeNode
}

type BinarySearchTree struct {
    root *TreeNode
    lock sync.RWMutex
}

func (t *BinarySearchTree) Insert(key int, value Item) {
    t.lock.Lock()
    defer t.lock.Unlock()
    n := &TreeNode{key, value, nil, nil}
    if t.root == nil {
        t.root = n
    } else {
        insertNode(t.root, n)
    }
}

func insertNode(node, newNode *TreeNode) {
    // 插入到左子树
    if newNode.key < node.key {
        if node.left == nil {
            node.left = newNode
        } else {
            // 递归查找左边插入
            insertNode(node.left, newNode)
        }
    } else { // 插入到右子树
        if node.right == nil {
            node.right = newNode
        } else {
            // 递归查找右边插入
            insertNode(node.right, newNode)
        }
    }
}

func (t *BinarySearchTree) Search(key int) bool {
    t.lock.Lock()
    defer t.lock.Unlock()
    return search(key, t.root)
}

//寻找插入位置的过程,实际上类似于二分查找
func search(key int, n *TreeNode) bool {
    if n == nil {
        return false
    }
    // 落在左边,向左搜索更小的值
    if key < n.key {
        search(key, n.left)
    }
    // 落在右边,向右搜索更大的值
    if key > n.key {
        search(key, n.right)
    }

    return true
}

func (t *BinarySearchTree) Remove(key int) {
    t.lock.Lock()
    defer t.lock.Unlock()
    remove(key, t.root)
}

func remove(key int, n *TreeNode) *TreeNode {
    if n == nil {
        return nil
    }
    // 要删除的节点在左侧
    if key < n.key {
        n.left = remove(key, n.left)
        return n
    }
    // 要删除的节点在右侧
    if key > n.key {
        n.right = remove(key, n.right)
        return n
    }
    // 若删除的节点是叶子节点,直接删除
    if n.left == nil && n.right == nil {
        n = nil
        return n
    }
    // 若删除的节点只有一个节点,删除自身
    if n.left == nil {
        n = n.right
        return n
    }
    // 若删除的节点只有一个节点,删除自身
    if n.right == nil {
        n = n.left
        return n
    }

    mostLeftNode := n.right
    for {
        // 一直遍历找到最左节点
        if mostLeftNode != nil && mostLeftNode.left != nil {
            mostLeftNode = mostLeftNode.left
        } else {
            break
        }
    }
    // 使用右子树的最左节点替换当前节点,即删除当前节点
    n.key, n.value = mostLeftNode.key, mostLeftNode.value
    n.right = remove(n.key, n.right)

    return n
}

// 获取树中值最小的节点:最左节点
func (t *BinarySearchTree) Min() *Item {
    t.lock.RLock()
    defer t.lock.RUnlock()
    n := t.root
    if n == nil {
        return nil
    }
    for {
        if n.left == nil {
            return &n.value
        }
        n = n.left
    }
}

// 获取树中值最大的节点:最右节点
func (t *BinarySearchTree) Max() *Item {
    t.lock.RLock()
    defer t.lock.RUnlock()
    n := t.root
    if n == nil {
        return nil
    }
    for {
        if n.right == nil {
            return &n.value
        }
        n = n.right
    }
}

// 先序遍历:根节点 -> 左子树 -> 右子树
func (t *BinarySearchTree) PreOrderTraverse(printFunc func(Item)) {
    t.lock.RLock()
    defer t.lock.RUnlock()
    preOrderTraverse(t.root, printFunc)
}

func preOrderTraverse(node *TreeNode, printFunc func(Item)) {
    if node != nil {
        printFunc(node.value)                   // 先打印根结点
        preOrderTraverse(node.left, printFunc)  // 再打印左子树
        preOrderTraverse(node.right, printFunc) // 最后打印右子树
    }
}

// 中序遍历:左子树 -> 根节点 -> 右子树
func (t *BinarySearchTree) PostOrderTraverse(printFunc func(Item)) {
    t.lock.RLock()
    defer t.lock.RUnlock()
    postOrderTraverse(t.root, printFunc)
}

func postOrderTraverse(node *TreeNode, printFunc func(Item)) {
    if node != nil {
        postOrderTraverse(node.left, printFunc)  // 先打印左子树
        postOrderTraverse(node.right, printFunc) // 再打印右子树
        printFunc(node.value)                    // 最后打印根结点
    }
}

// 后续遍历:左子树 -> 右子树 -> 根结点
func (t *BinarySearchTree) InOrderTraverse(printFunc func(Item)) {
    t.lock.RLock()
    defer t.lock.RUnlock()
    inOrderTraverse(t.root, printFunc)
}

func inOrderTraverse(node *TreeNode, printFunc func(Item)) {
    if node != nil {
        inOrderTraverse(node.left, printFunc)  // 先打印左子树
        printFunc(node.value)                  // 再打印根结点
        inOrderTraverse(node.right, printFunc) // 最后打印右子树
    }
}

// 打印树结构
func (t *BinarySearchTree) String() {
    t.lock.Lock()
    defer t.lock.Unlock()
    if t.root == nil {
        println("Tree is empty")
        return
    }
    stringify(t.root, 0)
    println("----------------------------")
}

func stringify(node *TreeNode, level int) {
    if node == nil {
        return
    }

    format := ""
    for i := 0; i < level; i++ {
        format += "\t" // 根据节点的深度决定缩进长度
    }
    format += "----[ "
    level++
    // 先递归打印左子树
    stringify(node.left, level)
    fmt.Printf(format+"%d\n", node.key)
    /// 再递归打印右子树
    stringify(node.right, level)
}

测试

测试上面公开的方法

import (
    "fmt"
    "testing"
)

var bst BinarySearchTree

func fillTree(bst *BinarySearchTree) {
    bst.Insert(8, "8")
    bst.Insert(4, "4")
    bst.Insert(10, "10")
    bst.Insert(2, "2")
    bst.Insert(6, "6")
    bst.Insert(1, "1")
    bst.Insert(3, "3")
    bst.Insert(5, "5")
    bst.Insert(7, "7")
    bst.Insert(9, "9")
}

func TestInsertTreeNode(t *testing.T) {
    fillTree(&bst)
    bst.String()

    bst.Insert(11, "11")
    bst.String()
}

// isSameSlice returns true if the 2 slices are identical
func isSameSlice(a, b []string) bool {
    if a == nil && b == nil {
        return true
    }
    if a == nil || b == nil {
        return false
    }
    if len(a) != len(b) {
        return false
    }
    for i := range a {
        if a[i] != b[i] {
            return false
        }
    }
    return true
}

func TestInOrderTraverse(t *testing.T) {
    var result []string
    bst.InOrderTraverse(func(i Item) {
        result = append(result, fmt.Sprintf("%s", i))
    })
    if !isSameSlice(result, []string{"1", "2", "3", "4", "5", "6", "7", "8", "9", "10", "11"}) {
        t.Errorf("Traversal order incorrect, got %v", result)
    }
}

func TestPreOrderTraverse(t *testing.T) {
    var result []string
    bst.PreOrderTraverse(func(i Item) {
        result = append(result, fmt.Sprintf("%s", i))
    })
    if !isSameSlice(result, []string{"8", "4", "2", "1", "3", "6", "5", "7", "10", "9", "11"}) {
        t.Errorf("Traversal order incorrect, got %v instead of %v", result, []string{"8", "4", "2", "1", "3", "6", "5", "7", "10", "9", "11"})
    }
}

func TestPostOrderTraverse(t *testing.T) {
    var result []string
    bst.PostOrderTraverse(func(i Item) {
        result = append(result, fmt.Sprintf("%s", i))
    })
    if !isSameSlice(result, []string{"1", "3", "2", "5", "7", "6", "4", "9", "11", "10", "8"}) {
        t.Errorf("Traversal order incorrect, got %v instead of %v", result, []string{"1", "3", "2", "5", "7", "6", "4", "9", "11", "10", "8"})
    }
}

func TestMin(t *testing.T) {
    if fmt.Sprintf("%s", *bst.Min()) != "1" {
        t.Errorf("min should be 1")
    }
}

func TestMax(t *testing.T) {
    if fmt.Sprintf("%s", *bst.Max()) != "11" {
        t.Errorf("max should be 11")
    }
}

func TestSearch(t *testing.T) {
    if !bst.Search(1) || !bst.Search(8) || !bst.Search(11) {
        t.Errorf("search not working")
    }
}

func TestRemove(t *testing.T) {
    bst.Remove(1)
    if fmt.Sprintf("%s", *bst.Min()) != "2" {
        t.Errorf("min should be 2")
    }
}
文章目录