树

二叉树

// TreeNode 表示二叉树中的一个节点。
// Value 是当前节点保存的数据。
// Left 和 Right 分别指向左子节点、右子节点。
type TreeNode struct {
    Value int
    Left  *TreeNode
    Right *TreeNode
}

// BinaryTree 表示一棵二叉树。
// Root 指向根节点，也就是整棵树的入口。
type BinaryTree struct {
    Root *TreeNode
}

func NewBinaryTree() *BinaryTree {
    return &BinaryTree{}
}

// Insert 按照二叉搜索树的规则插入数据。
// 规则是：
// 1. 比当前节点小，放到左子树
// 2. 比当前节点大，放到右子树
// 3. 如果值相等，这里不重复插入
func (t *BinaryTree) Insert(value int) {
    newNode := &TreeNode{Value: value}

    if t.Root == nil {
        t.Root = newNode
        return
    }

    current := t.Root
    for {
        if value < current.Value {
            if current.Left == nil {
                current.Left = newNode
                return
            }
            current = current.Left
            continue
        }

        if value > current.Value {
            if current.Right == nil {
                current.Right = newNode
                return
            }
            current = current.Right
            continue
        }

        // 值相同则直接结束，不重复插入。
        return
    }
}

// PreOrder 前序遍历。
// 顺序是：根 -> 左 -> 右。
func (t *BinaryTree) PreOrder() []int {
    result := make([]int, 0)
    preOrder(t.Root, &result)
    return result
}

func preOrder(node *TreeNode, result *[]int) {
    if node == nil {
        return
    }

    *result = append(*result, node.Value)
    preOrder(node.Left, result)
    preOrder(node.Right, result)
}

// InOrder 中序遍历。
// 顺序是：左 -> 根 -> 右。
// 对二叉搜索树来说，中序遍历的结果会是升序。
func (t *BinaryTree) InOrder() []int {
    result := make([]int, 0)
    inOrder(t.Root, &result)
    return result
}

func inOrder(node *TreeNode, result *[]int) {
    if node == nil {
        return
    }

    inOrder(node.Left, result)
    *result = append(*result, node.Value)
    inOrder(node.Right, result)
}

// PostOrder 后序遍历。
// 顺序是：左 -> 右 -> 根。
func (t *BinaryTree) PostOrder() []int {
    result := make([]int, 0)
    postOrder(t.Root, &result)
    return result
}

func postOrder(node *TreeNode, result *[]int) {
    if node == nil {
        return
    }

    postOrder(node.Left, result)
    postOrder(node.Right, result)
    *result = append(*result, node.Value)
}

// LevelOrder 层序遍历，也就是广度优先遍历。
// 它会一层一层地从上往下、从左往右访问节点。
func (t *BinaryTree) LevelOrder() []int {
    result := make([]int, 0)
    if t.Root == nil {
        return result
    }

    // 使用切片模拟队列。
    queue := make([]*TreeNode, 0)
    queue = append(queue, t.Root)

    for len(queue) > 0 {
        current := queue[0]
        queue = queue[1:]

        result = append(result, current.Value)

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

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

    return result
}

多叉树

// MultiTreeNode 表示多叉树中的一个节点。
// 和二叉树不同，多叉树的每个节点不再只有 Left 和 Right 两个分支，
// 而是可以拥有任意数量的子节点。
type MultiTreeNode struct {
    Value    string
    Children []*MultiTreeNode
}

// AddChild 给当前节点添加一个子节点。
// 添加完成后返回新创建的子节点，方便继续往下挂更多节点。
func (n *MultiTreeNode) AddChild(value string) *MultiTreeNode {
    child := &MultiTreeNode{
        Value:    value,
        Children: make([]*MultiTreeNode, 0),
    }

    n.Children = append(n.Children, child)
    return child
}

// MultiTree 表示一棵多叉树。
// Root 是整棵树的根节点。
type MultiTree struct {
    Root *MultiTreeNode
}

func NewMultiTree(rootValue string) *MultiTree {
    return &MultiTree{
        Root: &MultiTreeNode{
            Value:    rootValue,
            Children: make([]*MultiTreeNode, 0),
        },
    }
}

// DepthFirstTraversal 深度优先遍历。
// 这里使用前序方式：先访问当前节点，再依次访问所有子节点。
func (t *MultiTree) DepthFirstTraversal() []string {
    result := make([]string, 0)
    if t.Root == nil {
        return result
    }

    depthFirstTraversal(t.Root, &result)
    return result
}

func depthFirstTraversal(node *MultiTreeNode, result *[]string) {
    if node == nil {
        return
    }

    *result = append(*result, node.Value)

    for _, child := range node.Children {
        depthFirstTraversal(child, result)
    }
}

// BreadthFirstTraversal 广度优先遍历，也就是层序遍历。
// 它会先访问第一层，再访问第二层，然后依次向下。
func (t *MultiTree) BreadthFirstTraversal() []string {
    result := make([]string, 0)
    if t.Root == nil {
        return result
    }

    // 使用切片模拟队列。
    queue := make([]*MultiTreeNode, 0)
    queue = append(queue, t.Root)

    for len(queue) > 0 {
        current := queue[0]
        queue = queue[1:]

        result = append(result, current.Value)

        for _, child := range current.Children {
            queue = append(queue, child)
        }
    }

    return result
}

红黑树

重要

这里不提供代码。红黑树，几乎是面试能考的数据结构最复杂的一个。