Golang Algorithm - binaryTree (이진트리)

이진트리란?

이진 트리는 각각의 노드가 최대 두 개의 자식 노드를 가지는 자료구조를 뜻한다.

https://ko.wikipedia.org/wiki/%EC%9D%B4%EC%A7%84_%ED%8A%B8%EB%A6%AC

이진 트리 - 위키백과, 우리 모두의 백과사전

구조체와 함수의 역할

BinaryTree 구조체 : 이진트리를 나타내고 해당 트리의 루트노드(최상위 노드, root node)를 필드로 가진다. 
BinaryNode 구조체 : 이진트리의 노드를 나타내고 left(왼쪽 자식), right(오른쪽 자식), data(노드에 저장할 데이터)를 필드로 가진다. 
BinaryTree insert 메서드 :  루트노드가 없으면 루트노드를 만들고 루트노드가 있을 경우 insert 메서드를 호출해서 데이터 삽입

BinaryNode insert 메서드 : data를 입력받아 이진트리의 적절한 위치에 노드를 추가하는 함수 

 

 

go로 구현한 이진트리 

package main

import (
	"fmt"
	"io"
	"os"
)

//바이너리 트리 구조체 
type BinaryTree struct {
    root *BinaryNode //이진트리의 루트노드를 필드로 가짐 
}

//바이너리 노드 구조체
type BinaryNode struct {
    left  *BinaryNode //왼쪽 자식 노드 
    right *BinaryNode //오른쪽 자식 노드 
    data  int64 //노드에 저장할 데이터 
}
 
 
//BinaryTree 구조체에 insert 메서드를 정의한다.
func (t *BinaryTree) insert(data int64) *BinaryTree {
    if t.root == nil { 
        t.root = &BinaryNode{data: data, left: nil, right: nil}
    } else {
        t.root.insert(data)
    }
    return t
}
 

//바이너리 노드 구조체에도 insert 메서드를 정의한다. 
func (n *BinaryNode) insert(data int64) {
    if n == nil {
        return
    } else if data <= n.data {
        if n.left == nil {
            n.left = &BinaryNode{data: data, left: nil, right: nil}
        } else {
            n.left.insert(data)
        }
    } else {
        if n.right == nil {
            n.right = &BinaryNode{data: data, left: nil, right: nil}
        } else {
            n.right.insert(data)
        }
    }   
}


//입력받은 노드를 루트로 하는 이진트리를 출력한다. 
func print(w io.Writer, node *BinaryNode, ns int, ch rune) {
    if node == nil {
        return
    }
 
    for i := 0; i < ns; i++ {
        fmt.Fprint(w, " ")
    }
    fmt.Fprintf(w, "%c:%v\n", ch, node.data)
    print(w, node.left, ns+2, 'L')
    print(w, node.right, ns+2, 'R')
}
 
func main() {
    tree := &BinaryTree{}
    tree.insert(100).
        insert(-20).
		insert(-50).
		insert(-15).
		insert(-60).
        insert(50).
		insert(60).
		insert(55).
        insert(85).
		insert(15).
		insert(5).
        insert(-10)
    print(os.Stdout, tree.root, 0, 'M')
}

go 로그

go run ../algorithm/binary_tree.go 
M:100
  L:-20
    L:-50
      L:-60
    R:-15
      R:50
        L:15
          L:5
            L:-10
        R:60
          L:55
          R:85

 

 

 

go로 구현한 이진트리 2번째 코드

각 함수의 역할

type TreeNode struct : 트리노드 구조체 정의 (밸류, left 노드, right 노드)

func insert() : 루트노드의 밸류에 따라 insert 함수를 호출해서 루트보다 작으면 left, 크면 right로 삽입

func search() : 루트 노드 밸류에 따라 작으면 left search, 크면 right search하는 함수

func delete() : 루트 노드의 값에 따라 삭제하고 minNode를 관리하는 함수

 

package main

import "fmt"

type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

func insert(root *TreeNode, val int) *TreeNode {
    if root == nil {
        return &TreeNode{Val: val}
    }

    if val < root.Val {
        root.Left = insert(root.Left, val)
    } else {
        root.Right = insert(root.Right, val)
    }

    return root
}

func search(root *TreeNode, val int) bool {
    if root == nil {
        return false
    }

    if root.Val == val {
        return true
    } else if val < root.Val {
        return search(root.Left, val)
    } else {
        return search(root.Right, val)
    }
}

func delete(root *TreeNode, val int) *TreeNode {
    if root == nil {
        return root
    }

    if val < root.Val {
        root.Left = delete(root.Left, val)
    } else if val > root.Val {
        root.Right = delete(root.Right, val)
    } else {
        if root.Left == nil {
            return root.Right
        } else if root.Right == nil {
            return root.Left
        }

        minNode := root.Right
        for minNode.Left != nil {
            minNode = minNode.Left
        }

        root.Val = minNode.Val
        root.Right = delete(root.Right, minNode.Val)
    }

    return root
}

func main() {
    root := &TreeNode{Val: 5}
    insert(root, 3)
    insert(root, 7)
    insert(root, 1)
    insert(root, 9)

    fmt.Println(search(root, 7))
    fmt.Println(search(root, 4))

    root = delete(root, 5)

    fmt.Println(search(root, 5))
}

 

go 출력 로그

go run ../algorithm/binary_tree_ologn.go 
true
false
false