// 第 14 周 – 用数组表示的二叉树（下标从 1 开始：孩子 2i 和 2i+1，父结点 i/2）
// 运行：go run ./w14/arraytree
package main

import "fmt"

// 不使用第 0 个元素；0 = 空位
var A = []rune{0, 'A', 'B', 'C', 'D', 'E', 0, 'G'}

func exists(i int) bool { return i < len(A) && A[i] != 0 }

func preorder(i int) {
	if !exists(i) {
		return
	}
	fmt.Printf("%c ", A[i])
	preorder(2 * i)
	preorder(2*i + 1)
}

func inorder(i int) {
	if !exists(i) {
		return
	}
	inorder(2 * i)
	fmt.Printf("%c ", A[i])
	inorder(2*i + 1)
}

func show(i int) string {
	if !exists(i) {
		return "-"
	}
	return string(A[i])
}

func main() {
	fmt.Print("preorder: ")
	preorder(1)
	fmt.Print("\ninorder:  ")
	inorder(1)
	fmt.Println()
	for i := 1; i < len(A); i++ {
		if A[i] == 0 {
			continue
		}
		parent := "-"
		if i > 1 {
			parent = string(A[i/2])
		}
		fmt.Printf("  A[%d] = %c, parent: %s, left: %s, right: %s\n", i, A[i], parent, show(2*i), show(2*i+1))
	}
}