二分木をいい感じに印字する奴

package main

import (
    "errors"
    "fmt"
    "log"
)

type Node struct {
    Value string
    Data string
    Left *Node
    Right *Node
}

// `Insert()` inserts a new data into the tree, at the position which is determined by the inserted value.
//
// 1. Start at the root node.
// 2. Compare the new value with the current node's value...
//     - If it is the same, stop. We have that value already.
//     - If it is smaller, repeat 2. with the left child node. If there is no left child node, then add a new one with the new value and stop.
//     - If it is greater, repeat 2. with the right child node. If there is no right child node, then add a new one with the new value and stop.
func (n *Node) Insert(value, data string) error {
    if n == nil {
        return errors.New("Cannot insert a value into a nil tree")
    }
    switch  {
    case value == n.Value:
        return nil
    case value < n.Value:
        if n.Left == nil {
            n.Left = &Node{Value:value, Data:data}
            return nil
        }
        return n.Left.Insert(value, data)
    case value > n.Value:
        if n.Right == nil {
            n.Right = &Node{Value:value, Data: data}
            return nil
        }
        return n.Right.Insert(value, data)
    }
    return nil
}

func (n *Node) IterativeInsert(value, data string) error {
    var parent *Node
    current := n
    if current == nil {
        return errors.New("Cannot insert a value into a nil tree")
    }
    for current != nil {
        parent = current
        if value < current.Value {
            current = current.Left
        } else {
            current = current.Right
        }
    }
    if value < parent.Value {
        parent.Left = &Node{Value:value, Data:data}
    } else {
        parent.Right = &Node{Value:value, Data:data}
    }
    return nil
}

// `Search()` searches the given data from the tree.
func (n *Node) Search(s string) (string, bool) {
    if n == nil {
        return "", false
    }
    switch {
    case s == n.Value:
        return n.Data, true
    case s < n.Value:
        return n.Left.Search(s)
    default:
        return n.Right.Search(s)
    }
}

func (n *Node) IterativeSearch(s string) (string, bool) {
    var result, p *Node
    p = n
    for p != nil {
        if s == p.Value {
            result = p
            p = nil
        } else {
            if s < p.Value {
                p = p.Left
            } else {
                p = p.Right
            }
        }
    }
    if result == nil {
        return "", false
    } else {
        return result.Data, true
    }
}

// `findMax()` finds the maximum element in a (sub-)tree and returns the node itself and its parent node.
func (n *Node) findMax(parent *Node) (*Node, *Node) {
    if n == nil {
        return nil, parent
    }
    if n.Right == nil {
        return n, parent
    }
    return n.Right.findMax(n)
}

// `replace()` replaces the `parent`'s child pointer to `n` with a pointer to the `replacement`node.
func (n *Node)replace(parent, replacement *Node) error {
    if n == nil {
        return errors.New("`replace()` is not allowed on a nil node")
    }
    if n == parent.Left {
        parent.Left = replacement
        return nil
    }
    parent.Right = replacement
    return nil
}

// `Delete()` deletes the given element from the tree.
// It is an error to try deleting an element that does not exist in the tree.
// In order to remove an element properly, `Delete` needs to know the to-be-deleted node's parent.
//
// Delete
// 1. Delete a leaf node.
//     - Just set the parent's child pointer to `nil`
// 2. Delete a half-lead node.
//     - Just replace the node by its child node.
// 3. Delete an inner node.
//     - The to-be-deleted node has two children, and we cannot assign both to the to-be-deleted node's parent node.
//     - In the to-be-deleted node's left subtree, find the node with the largest value. Let me call this "Node A"
//     - Replace the to-be-deleted node's value with A's value.
//     - If A is a leaf node or a half-leaf node, delete Node A as described above for the leaf and half-leaf cases.
//     - If A is an inner node, recursively call this `Delete()` on this node.
func (n *Node) Delete(s string, parent *Node) error {
    if n == nil {
        return errors.New("Value to be deleted does not exist in the tree")
    }
    switch {
    case s < n.Value:
        return n.Left.Delete(s, n)
    case s > n.Value:
        return n.Right.Delete(s, n)
    default:
        // We find the to-be-deleted node.
        // If the node has no children, just remove it from its parent.
        if n.Left == nil && n.Right == nil {
            n.replace(parent, nil)
            return nil
        }

        // If the node has one children, replace the node with its child.
        if n.Left == nil {
            n.replace(parent, n.Right)
            return nil
        }
        if n.Right == nil {
            n.replace(parent, n.Left)
            return nil
        }

        // If the node has two children, we have to find the node which has the maximum value, in the left subtree of the to-be-deleted node.
        replacement, replParent := n.Left.findMax(n)
        // Replace the node's value.
        n.Value = replacement.Value
        n.Data = replacement.Data
        // Remove the replaced node.
        return replacement.Delete(replacement.Value, replParent)
    }
}

type Tree struct {
    Root *Node
}

func (t *Tree) Insert(value, data string) error {
    if t.Root == nil {
        t.Root = &Node{Value:value, Data:data}
        return nil
    }
    return t.Root.Insert(value, data)
}

func (t *Tree) IterativeInsert(value, data string) error {
    if t.Root == nil {
        t.Root = &Node{Value:value, Data:data}
        return nil
    }
    return t.Root.IterativeInsert(value, data)
}

func (t *Tree) Search(s string) (string, bool) {
    if t.Root == nil {
        return "", false
    }
    return t.Root.Search(s)
}

func (t *Tree) IterativeSearch(s string) (string, bool) {
    if t.Root == nil {
        return "", false
    }
    return t.Root.IterativeSearch(s)
}

func (t *Tree) Delete(s string) error {
    if t.Root == nil {
        return errors.New("Cannot delete from an empty tree")
    }
    // We have to call `Delete()` with fake node in order to avoid having to treat the root node as a special case.
    fakeRoot := &Node{Right: t.Root}
    err := t.Root.Delete(s, fakeRoot)
    if err != nil {
        return err
    }
    // If the root node is the only node in the tree and if it is deleted, `t.Root` still points to the old node, so we have to rectify this by setting `t.Root` to `nil`.
    if fakeRoot.Right == nil {
        t.Root = nil
    }
    return nil
}

func (t *Tree) PreorderTraverse(n *Node, f func(*Node)) {
    if n == nil {
        return
    }
    f(n)
    t.PreorderTraverse(n.Left, f)
    t.PreorderTraverse(n.Right, f)
}

func (t *Tree) InorderTraverse(n *Node, f func(*Node)) {
    if n == nil {
        return
    }
    t.InorderTraverse(n.Left, f)
    f(n)
    t.InorderTraverse(n.Right, f)
}

func (t *Tree) PostorderTraverse(n *Node, f func(*Node)) {
    if n == nil {
        return
    }
    t.PostorderTraverse(n.Left, f)
    t.PostorderTraverse(n.Right, f)
    f(n)
}

func PrintTree(root *Node) {
    if root == nil {
        return
    }
    fmt.Println(root.Value)
    PrintSubTree(root, "")
    fmt.Println()
}

func PrintSubTree(root *Node, prefix string) {
    if root == nil {
        return
    }
    hasLeft, hasRight := false, false
    if root.Left != nil {
        hasLeft = true
    }
    if root.Right != nil {
        hasRight = true
    }
    if !hasLeft && !hasRight {
        return
    }
    fmt.Print(prefix)
    if hasLeft && hasRight {
        fmt.Print("├── ")
    } else {
        fmt.Print("")
    }
    if !hasLeft && hasRight {
        fmt.Print("└── ")
    } else {
        fmt.Print("")
    }
    if hasRight {
        printStrand := hasLeft && hasRight && (root.Right.Right != nil ||root.Right.Left != nil)
        newPrefix := ""
        if printStrand {
            newPrefix = prefix + "│   "
        } else {
            newPrefix = prefix + "    "
        }
        fmt.Println(root.Right.Value)
        PrintSubTree(root.Right, newPrefix)
    }
    if hasLeft {
        if hasRight {
            fmt.Print(prefix)
            fmt.Print("└── ")
            fmt.Print(root.Left.Value)
            fmt.Println()
        } else {
            fmt.Print("")
            fmt.Print("└── ")
            fmt.Print(root.Left.Value)
            fmt.Println()
        }
        PrintSubTree(root.Left, prefix + "    ")
    }
}

func main() {
    values := []string{"r", "s", "a", "e", "o", "h", "k", "d", "l", "z", "w", "q", "t", "y", "m", "c", "f", "n", "j", "b", "p", "i", "x", "g", "u", "v"}
    data := []string{"0", "1", "2", "3", "4", "5", "6", "7", "8", "9", "10", "11", "12", "13", "14", "15", "16", "17", "18", "19", "20", "21", "22", "23", "24", "25", "26"}

    // Create tree
    tree := &Tree{}
    for i := 0; i < len(values); i++ {
        err := tree.Insert(values[i], data[i])
        if err != nil {
            log.Fatal("Error inserting value `", values[i], "`: ", err)
        }
    }

    PrintTree(tree.Root)

    // Inorder traverse from root
    fmt.Print("Sorted values: | ")
    tree.InorderTraverse(tree.Root,
        func(n *Node) {
            fmt.Print(n.Value, ": ", n.Data, " | ")
        })
    fmt.Println()

    // Search
    s := "d"
    fmt.Print("Find node '", s, "': ")
    d, found := tree.Search(s)
    if !found {
        log.Fatal("Cannot find '" + s + "'")
    }
    fmt.Println("Found " + s + ": '" + d + "'")

    // Delete
    err := tree.Delete(s)
    if err != nil {
        log.Fatal("Error deleting "+s+": ", err)
    }
    fmt.Print("After deleting '" + s + "': ")
    tree.InorderTraverse(tree.Root,
        func(n *Node) {
            fmt.Print(n.Value, ": ", n.Data, " | ")
        })
    fmt.Println()
}