数据结构算法一：二叉树

参考：https://mp.weixin.qq.com/s/8YoAg2DVBwjl8THocYHnmg

特点

根节点比左子树上的所有节点都大，比右子树的所有节点都小。主要是通过递归的思想实现。

如图所示（图片来源于网络截图） 二叉树结构展示

• 节点定义

//定义节点
type Node struct {
    Value int
    Left  *Node
    Right *Node
}
//定义数据类型
type BST struct {
    root *Node
}

• 插入

//插入
func (bst *BST) Insert(value int) {
    newNode := &Node{
        Value: value,
    }
    if bst.root == nil {
        bst.root = newNode
    } else {
        insertNode(bst.root, newNode)
    }
}

func insertNode(root, newNode *Node) {
    if newNode.Value < root.Value {
        if root.Left == nil {
            root.Left = newNode
        } else {
            insertNode(root.Left, newNode)
        }
    } else if newNode.Value > root.Value {
        if root.Right == nil {
            root.Right = newNode
        } else {
            insertNode(root.Right, newNode)
        }
    }
}

• 搜索

func (bst *BST) Search(value int) bool {
    return search(bst.root, value)
}

func search(root *Node, value int) bool {
    if root == nil {
        return false
    }
    if value < root.Value {
        return search(root.Left, value)
    }
    if value > root.Value {
        return search(root.Right, value)
    }
    return true
}

• 遍历

//遍历-前序遍历
func (bst *BST) PreOrderTraverse(f func(int)) {
    preOrderTraverse(bst.root, f)
}
func preOrderTraverse(root *Node, f func(int)) {
    if root != nil {
        f(root.Value)
        preOrderTraverse(root.Left, f)
        preOrderTraverse(root.Right, f)
    }
}

//遍历-后序遍历
func (bst *BST) PostOrderTraverse(f func(int)) {
    postOrderTraverse(bst.root, f)
}
func postOrderTraverse(root *Node, f func(int)) {
    if root != nil {
        postOrderTraverse(root.Left, f)
        postOrderTraverse(root.Right, f)
        f(root.Value)
    }
}

• 删除

//删除
func (bst *BST) Remove(value int) bool {
    _, existed := remove(bst.root, value)
    return existed
}
func remove(root *Node, value int) (*Node, bool) {
    if root == nil {
        return nil, false
    }
    var existed bool
    //从左边找
    if value < root.Value {
        root.Left, existed = remove(root.Left, value)
        return root, existed
    }
    //从右边找
    if value > root.Value {
        root.Right, existed = remove(root.Right, value)
        return root, existed
    }

    //存在
    existed = true
    if root.Left == nil && root.Right == nil {
        root = nil
        return root, existed
    }
    if root.Left == nil {
        root = root.Left
        return root, existed
    }
    if root.Right == nil {
        root = root.Right
        return root, existed
    }

    smallestRight, _ := min(root.Right)
    root.Value = smallestRight
    root.Right, _= remove(root.Right, smallestRight)
    return root, existed
}

func min(node *Node) (int, bool) {
    if node == nil {
        return 0, false
    }
    n := node
    // 从左边找
    for {
        if n.Left == nil {
            return n.Value, true
        }
        n = n.Right
    }
}