Membuat Binary Tree Dari Flat Data Di Golang

Apa itu binary tree?

Binary tree adalah struktur data berhierarki dalam ilmu komputer dan struktur data, yang terdiri dari simpul-simpul atau node-node yang diatur dalam suatu hierarki. Setiap node dalam binary tree memiliki setidaknya dua cabang atau anak-anak, yang dikenal sebagai sub-pohon kiri dan sub-pohon kanan.

Contoh penggunaan binary tree

  Pada contoh ini kita akan membuat struktur data Menu dimana ada parent dan child yang saling berelasi satu sama lain.

Kita akan menggunakan bahasa pemrograman golang untuk membuat struktur binary tree dari Flat akan diubah menjadi struktur tree.

Buat struct untuk Menu

type Menu struct {
	ID       int
	ParentID int
	MenuName string `json:"menu_name"`
	MenuPath string `json:"menu_path"`
	Children []*Menu
}
}

Source yang akan kita gunakan adalah

menus := []*Menu{
		{
			ID:       1,
			ParentID: 0,
			MenuName: "Home 1",
		},
		{
			ID:       2,
			ParentID: 1,
			MenuName: "Home 2",
		},
		{
			ID:       3,
			ParentID: 2,
			MenuName: "Home 3",
		},
		{
			ID:       4,
			ParentID: 0,
			MenuName: "Dashboard 1",
		},
		{
			ID:       5,
			ParentID: 4,
			MenuName: "Dashboard 2",
		},
		{
			ID:       6,
			ParentID: 5,
			MenuName: "Dashboard 3",
		},
		{
			ID:       7,
			ParentID: 6,
			MenuName: "Dashboard 4",
		},
		{
			ID:       8,
			ParentID: 7,
			MenuName: "Dashboard 5",
		},
		{
			ID:       9,
			ParentID: 8,
			MenuName: "Dashboard 6",
		},
		{
			ID:       10,
			ParentID: 9,
			MenuName: "Dashboard 7",
		},
	}

Buat file main.go

Buat fungsi creatreTree

func createTree(nodes []*Menu) []*Menu {
	nodeMap := make(map[int]*Menu)

	// Create a mapping of ID to Menu
	for _, node := range nodes {
		nodeMap[node.ID] = node
	}

	// Iterate through nodes to build the tree
	var root []*Menu
	for _, node := range nodes {
		parentID := node.ParentID
		if parentID == 0 {
			// Node is the root
			root = append(root, node)
		} else {
			// Node has a parent, add it to the parent's children
			parentNode := nodeMap[parentID]
			if parentNode != nil {
				parentNode.Children = append(parentNode.Children, node)
			}
		}
	}

	return root
}

Kemudian buat fungsi main

func main() {
	menus := []*Menu{
		{
			ID:       1,
			ParentID: 0,
			MenuName: "Home 1",
		},
		{
			ID:       2,
			ParentID: 1,
			MenuName: "Home 2",
		},
		{
			ID:       3,
			ParentID: 2,
			MenuName: "Home 3",
		},
		{
			ID:       4,
			ParentID: 0,
			MenuName: "Dashboard 1",
		},
		{
			ID:       5,
			ParentID: 4,
			MenuName: "Dashboard 2",
		},
		{
			ID:       6,
			ParentID: 5,
			MenuName: "Dashboard 3",
		},
		{
			ID:       7,
			ParentID: 6,
			MenuName: "Dashboard 4",
		},
		{
			ID:       8,
			ParentID: 7,
			MenuName: "Dashboard 5",
		},
		{
			ID:       9,
			ParentID: 8,
			MenuName: "Dashboard 6",
		},
		{
			ID:       10,
			ParentID: 9,
			MenuName: "Dashboard 7",
		},
	}

	trees := createTree(menus)

	b, _ := json.Marshal(trees)

	fmt.Println(string(b))
}

Full Code

package main

import (
	"encoding/json"
	"fmt"
)

type Menu struct {
	ID       int
	ParentID int
	MenuName string `json:"menu_name"`
	MenuPath string `json:"menu_path"`
	Children []*Menu
}

func createTree(nodes []*Menu) []*Menu {
	nodeMap := make(map[int]*Menu)

	// Create a mapping of ID to Menu
	for _, node := range nodes {
		nodeMap[node.ID] = node
	}

	// Iterate through nodes to build the tree
	var root []*Menu
	for _, node := range nodes {
		parentID := node.ParentID
		if parentID == 0 {
			// Node is the root
			root = append(root, node)
		} else {
			// Node has a parent, add it to the parent's children
			parentNode := nodeMap[parentID]
			if parentNode != nil {
				parentNode.Children = append(parentNode.Children, node)
			}
		}
	}

	return root
}

func main() {
	menus := []*Menu{
		{
			ID:       1,
			ParentID: 0,
			MenuName: "Home 1",
		},
		{
			ID:       2,
			ParentID: 1,
			MenuName: "Home 2",
		},
		{
			ID:       3,
			ParentID: 2,
			MenuName: "Home 3",
		},
		{
			ID:       4,
			ParentID: 0,
			MenuName: "Dashboard 1",
		},
		{
			ID:       5,
			ParentID: 4,
			MenuName: "Dashboard 2",
		},
		{
			ID:       6,
			ParentID: 5,
			MenuName: "Dashboard 3",
		},
		{
			ID:       7,
			ParentID: 6,
			MenuName: "Dashboard 4",
		},
		{
			ID:       8,
			ParentID: 7,
			MenuName: "Dashboard 5",
		},
		{
			ID:       9,
			ParentID: 8,
			MenuName: "Dashboard 6",
		},
		{
			ID:       10,
			ParentID: 9,
			MenuName: "Dashboard 7",
		},
	}

	trees := createTree(menus)

	b, _ := json.Marshal(trees)

	fmt.Println(string(b))
}

Jalankan perintah go run . untuk menjalankan log

fungsi diatas akan menghasilkan data seperti berikut:

[
    {
        "ID": 1,
        "ParentID": 0,
        "menu_name": "Home 1",
        "menu_path": "",
        "Children": [
            {
                "ID": 2,
                "ParentID": 1,
                "menu_name": "Home 2",
                "menu_path": "",
                "Children": [
                    {
                        "ID": 3,
                        "ParentID": 2,
                        "menu_name": "Home 3",
                        "menu_path": "",
                        "Children": null
                    }
                ]
            }
        ]
    },
    {
        "ID": 4,
        "ParentID": 0,
        "menu_name": "Dashboard 1",
        "menu_path": "",
        "Children": [
            {
                "ID": 5,
                "ParentID": 4,
                "menu_name": "Dashboard 2",
                "menu_path": "",
                "Children": [
                    {
                        "ID": 6,
                        "ParentID": 5,
                        "menu_name": "Dashboard 3",
                        "menu_path": "",
                        "Children": [
                            {
                                "ID": 7,
                                "ParentID": 6,
                                "menu_name": "Dashboard 4",
                                "menu_path": "",
                                "Children": [
                                    {
                                        "ID": 8,
                                        "ParentID": 7,
                                        "menu_name": "Dashboard 5",
                                        "menu_path": "",
                                        "Children": [
                                            {
                                                "ID": 9,
                                                "ParentID": 8,
                                                "menu_name": "Dashboard 6",
                                                "menu_path": "",
                                                "Children": [
                                                    {
                                                        "ID": 10,
                                                        "ParentID": 9,
                                                        "menu_name": "Dashboard 7",
                                                        "menu_path": "",
                                                        "Children": null
                                                    }
                                                ]
                                            }
                                        ]
                                    }
                                ]
                            }
                        ]
                    }
                ]
            }
        ]
    }
]