이진 트리(binary tree) 생성하기

이진 트리에 대한 작업을 확인할 때, test로 사용할 이진 트리를 생성하는 것이 귀찮을 때가 많다 (특히, 트리의 높이가 높을 수록...).  트리를 구성하는 노드값과 해당 노드 값을 이용해 노드간의 부모/자식 관계를 명시하여 트리를 간단히 생성하는 방법을 소개한다. 단, 이 방식은 모든 노드의 값이 정수이고, distinct한 경우에만 올바르게 동작한다.

노드값과 노드간의 관계는 TreeDesc를 사용하여 기술하고, 이를 buildTree에 넘겨 이진 트리를 생성한다. TreeDesc를 기술할 때, 루트 노드가 반드시 첫번째에 위치하지 않아도 상관 없다 (Go의 map 특성상 iteration의 순서가 보장되지도 않는다).

======================================================

type NodeVal int

type Node struct {

  Val NodeVal

  Left *Node

  Right *Node

}

type TreeDesc map[NodeVal]struct{Left, Right NodeVal}

func main() {

  tree := TreeDesc{

    1: {2, 3},

    2: {4, 5},

    3: {-1, -1},

    4: {-1, -1},

    5: {-1, -1},

  }

  

  root := buildTree(tree)

  // use root

}

func buildTree(tree TreeDesc) *Node {

  visited := map[NodeVal]*Node{}

  topology := []NodeVal{}

  for key, _ := range tree {

    createNode(key, tree, visited, &topology)

  }

  return visited[topology[len(topology) - 1]]

}

func createNode(key NodeVal, tree TreeDesc, visited map[NodeVal]*Node, topology *[]NodeVal) *Node {

  if key == -1 {

    return nil

  }

  if visited[key] != nil {

    return visited[key]

  }

  newNode := &Node{

    Val: key,

  }

  visited[key] = newNode

  newNode.Left = createNode(tree[key].Left, tree, visited, topology)

  newNode.Right = createNode(tree[key].Right, tree, visited, topology)

  *topology = append(*topology, key)

  return newNode

}