グラフと走査

二分木

• 木構造は、再帰的なデータ構造の典型例
• 各頂点の子の数が高々2であるような順序木
• 走査
  • PreOrder
  • InOrder
  • PostOrder

package main

import "fmt"

type Node struct {
	val string
	left, right *Node
}

func (n *Node) PreOrder() {
	if n != nil {
		fmt.Println("val: ", n.val)
		n.left.PreOrder()
		n.right.PreOrder()
	}
}

func (n *Node) InOrder() {
	if n != nil {
		n.left.InOrder()
		fmt.Println("val: ", n.val)
		n.right.InOrder()
	}
}

func (n *Node) PostOrder() {
	if n != nil {
		n.left.PostOrder()
		n.right.PostOrder()
		fmt.Println("val: ", n.val)
	}
}

type BinaryTree struct {
	root *Node
}

func NewNode(val string) *Node {
	return &Node{val: val, left: nil, right: nil}
}

func NewBinaryTree() *BinaryTree {
	return &BinaryTree{root: nil}
}

func main() {
	b := NewBinaryTree()
	b.root = NewNode("*")
	b.root.left = NewNode("+")
	b.root.right = NewNode("-")
	b.root.left.left = NewNode("a")
	b.root.left.right = NewNode("b")
	b.root.right.left = NewNode("c")
	b.root.right.right = NewNode("/")
	b.root.right.right.left = NewNode("d")
	b.root.right.right.right = NewNode("e")
	fmt.Println("PreOrder")
	b.root.PreOrder()
	fmt.Println()

	fmt.Println("InOrder")
	b.root.InOrder()
	fmt.Println()

	fmt.Println("PostOrder")
	b.root.PostOrder()
	fmt.Println()
}