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

```go
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()
}
```