golang 두 갈래 검색 트 리 구현

이 진 트 리 가 무엇 인지 잘 모 르 는 학생 들 은 제 가 쓴 이 데이터 구조 와 알고리즘 사 이 트 를 보 러 갈 수 있 습 니 다.
데이터 구조
우선 필요 한 데이터 구 조 를 정의 합 니 다.트 리 노드 의 좌우 노드 는 모두 * 트 리 노드 type 이 고 트 리 는 루트 데이터 필드 만 있 습 니 다. * 트 리 노드 type 입 니 다.

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

type BinarySearchTree struct {
  Root *TreeNode
}

Insert
트 리 에 요 소 를 삽입 하려 면 먼저 삽 입 된 위 치 를 찾 은 다음 삽입 해 야 합 니 다.여기 서 우리 의 실현 방법 은 TreeNode 와 Binary SearchTree 라 는 두 type 에 방법 을 추가 하 는 것 입 니 다.type 에 방법 을 추가 하 는 방식 에 주의해 야 하 며, 방법 호출 자 를 바 꾸 려 면 지침 을 사용 해 야 합 니 다.

func (tree BinarySearchTree) Insert (v int) {
  tree.Root.Insert(v)
}

func (node *TreeNode) Insert (v int){
  if v < node.Value {
    if node.Left != nil{
      node.Left.Insert(v)
    }else{
      node.Left = &TreeNode{v, nil, nil}
    }
  }else {
    if node.Right != nil{
      node.Right.Insert(v)
    }else{
      node.Right = &TreeNode{v, nil, nil}
    }
  }
}

두루
나무의 역 사 는 앞 순서, 뒤 순서, 중간 순서 등 이 있다.여 기 는 중 서 를 예 로 들 자.slice 와 slice 지침 의 차이 에 주의 하 세 요.

func (tree BinarySearchTree) InOrder() []int{
  var res []int
  tree.Root.InOrder(&res)
  return res
}

func (node *TreeNode) InOrder(result *[]int) {
  if node.Left != nil{
    node.Left.InOrder(result)
  }
  *result = append(*result, node.Value)
  if node.Right != nil{
    node.Right.InOrder(result)
  }
}

최대 최소 값

func (tree BinarySearchTree) FindMin() int {
  node := tree.Root
  for {
    if node.Left != nil {
      node = node.Left
    }else{
      return node.Value
    }
  }
}

func (tree BinarySearchTree) FindMax() int {
  node := tree.Root
  for {
    if node.Right != nil {
      node = node.Right
    }else{
      return node.Value
    }
  }
}

찾다

func (tree BinarySearchTree) Contains(v int) bool {
  node := tree.Root
  for {
    if node == nil{
      return false
    }else if (node.Value == v) {
      return true
    }else if (node.Value > v){
      node = node.Left
    }else{
      node = node.Right
    }
  }
}