|
|
// ====================================================
|
|
|
// Data-Structures-with-Go Copyright(C) 2017 Furkan Türkal
|
|
|
// This program comes with ABSOLUTELY NO WARRANTY; This is free software,
|
|
|
// and you are welcome to redistribute it under certain conditions; See
|
|
|
// file LICENSE, which is part of this source code package, for details.
|
|
|
// ====================================================
|
|
|
|
|
|
package main
|
|
|
|
|
|
import "fmt"
|
|
|
|
|
|
type Node struct {
|
|
|
data int
|
|
|
left *Node
|
|
|
right *Node
|
|
|
}
|
|
|
|
|
|
//Returns an initialized list
|
|
|
func (n *Node) Init(data int) *Node {
|
|
|
n.data = data
|
|
|
n.left = nil
|
|
|
n.right = nil
|
|
|
return n
|
|
|
}
|
|
|
|
|
|
//Returns an new list
|
|
|
func New(data int) *Node {
|
|
|
return new(Node).Init(data)
|
|
|
}
|
|
|
|
|
|
/* Compute the "height" of a tree -- the number of
|
|
|
nodes along the longest path from the root node
|
|
|
down to the farthest leaf node.*/
|
|
|
func GetHeight(node *Node) int {
|
|
|
//1. Check if the given node is NULL
|
|
|
if node == nil {
|
|
|
return 0
|
|
|
}
|
|
|
|
|
|
//2. Compute the height of each subtree
|
|
|
lheight := GetHeight(node.left)
|
|
|
rheight := GetHeight(node.right)
|
|
|
|
|
|
//3. Use the larger one
|
|
|
if lheight > rheight {
|
|
|
return lheight + 1
|
|
|
}
|
|
|
return rheight + 1
|
|
|
}
|
|
|
|
|
|
/* Print nodes at a given level */
|
|
|
func PrintGivenLevel(root *Node, level int) {
|
|
|
//1. Check if the given root is NULL
|
|
|
if root == nil {
|
|
|
return
|
|
|
}
|
|
|
|
|
|
if level == 1 {
|
|
|
fmt.Printf("%d ", root.data)
|
|
|
} else if level > 1 {
|
|
|
PrintGivenLevel(root.left, level-1)
|
|
|
PrintGivenLevel(root.right, level-1)
|
|
|
}
|
|
|
}
|
|
|
|
|
|
/* Function to print level order traversal a tree*/
|
|
|
func PrintLevelOrder(root *Node) {
|
|
|
//1. Check if the given root is NULL
|
|
|
if root == nil {
|
|
|
fmt.Println("The given root node cannot be NULL")
|
|
|
return
|
|
|
}
|
|
|
|
|
|
h := GetHeight(root)
|
|
|
|
|
|
for i := 1; i <= h; i++ {
|
|
|
PrintGivenLevel(root, i)
|
|
|
}
|
|
|
}
|
|
|
|
|
|
func main() {
|
|
|
|
|
|
//To allocate dynamically a new Node in C language : root = (struct Node*) malloc(sizeof(struct Node));
|
|
|
root := New(1)
|
|
|
|
|
|
root.left = New(2)
|
|
|
root.right = New(3)
|
|
|
|
|
|
root.left.left = New(4)
|
|
|
root.left.right = New(5)
|
|
|
|
|
|
fmt.Println("\nLevel Order traversal of binary tree is :")
|
|
|
PrintLevelOrder(root)
|
|
|
}
|