Ağaçlar ve İkili Ağaçlar

package main

import "fmt"

type Node struct {
	Value       int
	Left, Right *Node
}

// build, dilimden tam (complete) bir ikili ağaç kurar.
// Dizi temsilinde: i. düğümün çocukları 2i+1 ve 2i+2'dir.
func build(values []int, i int) *Node {
	if i >= len(values) {
		return nil
	}
	return &Node{
		Value: values[i],
		Left:  build(values, 2*i+1),
		Right: build(values, 2*i+2),
	}
}

// size: düğüm sayısı
func size(n *Node) int {
	if n == nil {
		return 0
	}
	return 1 + size(n.Left) + size(n.Right)
}

// height: kenar cinsinden yükseklik (tek düğümlü ağaç için 0)
func height(n *Node) int {
	if n == nil {
		return -1
	}
	return 1 + max(height(n.Left), height(n.Right))
}

// leaves: yaprak sayısı
func leaves(n *Node) int {
	if n == nil {
		return 0
	}
	if n.Left == nil && n.Right == nil {
		return 1
	}
	return leaves(n.Left) + leaves(n.Right)
}

// isBalanced: her düğümde alt ağaç yükseklik farkı ≤ 1 mi
func isBalanced(n *Node) bool {
	var check func(*Node) (int, bool)
	check = func(n *Node) (int, bool) {
		if n == nil {
			return -1, true
		}
		lh, lok := check(n.Left)
		rh, rok := check(n.Right)
		if !lok || !rok || lh-rh > 1 || rh-lh > 1 {
			return 0, false
		}
		return 1 + max(lh, rh), true
	}
	_, ok := check(n)
	return ok
}

func main() {
	tree := build([]int{1, 2, 3, 4, 5, 6, 7}, 0)

	fmt.Println("düğüm sayısı:", size(tree))
	fmt.Println("yükseklik:", height(tree))
	fmt.Println("yaprak sayısı:", leaves(tree))
	fmt.Println("dengeli mi:", isBalanced(tree))

	// Dejenere ağaç: her düğümün tek çocuğu
	degenerate := &Node{Value: 1,
		Right: &Node{Value: 2,
			Right: &Node{Value: 3,
				Right: &Node{Value: 4}}}}

	fmt.Println()
	fmt.Println("dejenere — düğüm:", size(degenerate), "yükseklik:", height(degenerate))
	fmt.Println("dejenere dengeli mi:", isBalanced(degenerate))
	fmt.Println("boş ağaç yüksekliği:", height(nil))
}

package main

import (
	"fmt"
	"strings"
)

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

func build() *Node {
	return &Node{"A",
		&Node{"B", &Node{"D", nil, nil}, &Node{"E", nil, nil}},
		&Node{"C", &Node{"F", nil, nil}, &Node{"G", nil, nil}},
	}
}

func preorder(n *Node, visit func(string)) {
	if n == nil {
		return
	}
	visit(n.Value) // önce kök
	preorder(n.Left, visit)
	preorder(n.Right, visit)
}

func inorder(n *Node, visit func(string)) {
	if n == nil {
		return
	}
	inorder(n.Left, visit)
	visit(n.Value) // ortada kök
	inorder(n.Right, visit)
}

func postorder(n *Node, visit func(string)) {
	if n == nil {
		return
	}
	postorder(n.Left, visit)
	postorder(n.Right, visit)
	visit(n.Value) // sonda kök
}

// levelOrder: kuyruk kullanır — BFS
func levelOrder(root *Node) [][]string {
	if root == nil {
		return nil
	}
	var levels [][]string
	queue := []*Node{root}

	for len(queue) > 0 {
		var level []string
		var next []*Node
		for _, n := range queue {
			level = append(level, n.Value)
			if n.Left != nil {
				next = append(next, n.Left)
			}
			if n.Right != nil {
				next = append(next, n.Right)
			}
		}
		levels = append(levels, level)
		queue = next
	}
	return levels
}

func collect(walk func(*Node, func(string)), root *Node) string {
	var out []string
	walk(root, func(v string) { out = append(out, v) })
	return strings.Join(out, " ")
}

func main() {
	tree := build()

	fmt.Println("preorder :", collect(preorder, tree))
	fmt.Println("inorder  :", collect(inorder, tree))
	fmt.Println("postorder:", collect(postorder, tree))

	fmt.Println()
	for i, level := range levelOrder(tree) {
		fmt.Printf("seviye %d: %v\n", i, level)
	}
}

package main

import (
	"fmt"
	"strings"
)

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

func build() *Node {
	return &Node{"A",
		&Node{"B", &Node{"D", nil, nil}, &Node{"E", nil, nil}},
		&Node{"C", &Node{"F", nil, nil}, &Node{"G", nil, nil}},
	}
}

// iterativePreorder: yığına önce SAĞ çocuğu koy ki sol önce çıksın
func iterativePreorder(root *Node) []string {
	if root == nil {
		return nil
	}
	var out []string
	stack := []*Node{root}

	for len(stack) > 0 {
		n := stack[len(stack)-1]
		stack = stack[:len(stack)-1]
		out = append(out, n.Value)

		if n.Right != nil {
			stack = append(stack, n.Right)
		}
		if n.Left != nil {
			stack = append(stack, n.Left)
		}
	}
	return out
}

// iterativeInorder: sola in, düğümü işle, sağa geç
func iterativeInorder(root *Node) []string {
	var out []string
	var stack []*Node
	cur := root

	for cur != nil || len(stack) > 0 {
		for cur != nil { // sola git, yol boyunca yığına koy
			stack = append(stack, cur)
			cur = cur.Left
		}
		cur = stack[len(stack)-1]
		stack = stack[:len(stack)-1]
		out = append(out, cur.Value)
		cur = cur.Right
	}
	return out
}

// iterativePostorder: preorder'ın aynasını alıp ters çevir
func iterativePostorder(root *Node) []string {
	if root == nil {
		return nil
	}
	var out []string
	stack := []*Node{root}

	for len(stack) > 0 {
		n := stack[len(stack)-1]
		stack = stack[:len(stack)-1]
		out = append(out, n.Value)

		if n.Left != nil { // sol önce: sonuç ters çevrilecek
			stack = append(stack, n.Left)
		}
		if n.Right != nil {
			stack = append(stack, n.Right)
		}
	}
	// kök-sağ-sol → ters → sol-sağ-kök
	for i, j := 0, len(out)-1; i < j; i, j = i+1, j-1 {
		out[i], out[j] = out[j], out[i]
	}
	return out
}

func main() {
	tree := build()

	fmt.Println("iteratif preorder :", strings.Join(iterativePreorder(tree), " "))
	fmt.Println("iteratif inorder  :", strings.Join(iterativeInorder(tree), " "))
	fmt.Println("iteratif postorder:", strings.Join(iterativePostorder(tree), " "))

	fmt.Println("boş ağaç:", iterativePreorder(nil) == nil)
}

package main

import (
	"fmt"
	"strings"
)

type Node struct {
	Value       int
	Left, Right *Node
}

func build(values []int, i int) *Node {
	if i >= len(values) || values[i] == -1 {
		return nil
	}
	return &Node{values[i], build(values, 2*i+1), build(values, 2*i+2)}
}

// mirror: ağacın aynasını üretir (özgün ağacı değiştirmez)
func mirror(n *Node) *Node {
	if n == nil {
		return nil
	}
	return &Node{Value: n.Value, Left: mirror(n.Right), Right: mirror(n.Left)}
}

// isSymmetric: ağaç kendi aynası mı
func isSymmetric(root *Node) bool {
	var same func(a, b *Node) bool
	same = func(a, b *Node) bool {
		if a == nil || b == nil {
			return a == b
		}
		return a.Value == b.Value && same(a.Left, b.Right) && same(a.Right, b.Left)
	}
	if root == nil {
		return true
	}
	return same(root.Left, root.Right)
}

// maxDepth: en derin yolun düğüm sayısı
func maxDepth(n *Node) int {
	if n == nil {
		return 0
	}
	return 1 + max(maxDepth(n.Left), maxDepth(n.Right))
}

// sumPaths: kökten yaprağa giden tüm yolları toplar
func sumPaths(n *Node, current int, paths *[]string, sum int) {
	if n == nil {
		return
	}
	current = current*10 + n.Value
	if n.Left == nil && n.Right == nil {
		*paths = append(*paths, fmt.Sprint(current))
		return
	}
	sumPaths(n.Left, current, paths, sum)
	sumPaths(n.Right, current, paths, sum)
}

// diameter: ağaçtaki en uzun yolun kenar sayısı (kökten geçmek zorunda değil)
func diameter(root *Node) int {
	best := 0
	var depth func(*Node) int
	depth = func(n *Node) int {
		if n == nil {
			return 0
		}
		l, r := depth(n.Left), depth(n.Right)
		best = max(best, l+r) // bu düğümden geçen en uzun yol
		return 1 + max(l, r)
	}
	depth(root)
	return best
}

func inorderString(n *Node) string {
	if n == nil {
		return ""
	}
	parts := []string{inorderString(n.Left), fmt.Sprint(n.Value), inorderString(n.Right)}
	return strings.TrimSpace(strings.Join(parts, " "))
}

func main() {
	tree := build([]int{1, 2, 3, 4, 5, 6, 7}, 0)
	fmt.Println("özgün inorder:", inorderString(tree))
	fmt.Println("ayna inorder :", inorderString(mirror(tree)))

	fmt.Println("maksimum derinlik:", maxDepth(tree))
	fmt.Println("çap (kenar):", diameter(tree))

	var paths []string
	sumPaths(tree, 0, &paths, 0)
	fmt.Println("kökten yaprağa yollar:", paths)

	// Simetrik ağaç
	sym := build([]int{1, 2, 2, 3, 4, 4, 3}, 0)
	fmt.Println()
	fmt.Println("simetrik ağaç mı:", isSymmetric(sym))
	fmt.Println("özgün ağaç simetrik mi:", isSymmetric(tree))
	fmt.Println("boş ağaç simetrik mi:", isSymmetric(nil))
}