자바 이 진 트 리 기초 원리 및 구현 방법 상세 설명

이 글 의 사례 는 자바 이 진 트 리 의 기초 원리 와 실현 방법 을 서술 하 였 다.여러분 께 참고 하도록 공유 하 겠 습 니 다.구체 적 으로 는 다음 과 같 습 니 다.
앞에서 말 했 듯 이 본 고 는 먼저 이 진 트 리 기초 지식 을 알 아 본 다음 에 2 분 검색 트 리 를 배 우 는 것 으로 바 뀌 었 다.
나무
1.1 트 리 정의
나무(Tree)는n（n>=0)개 노드 의 유한 집합 이다n=0시 를 빈 나무 라 고 부른다.임의의 빈 나무 중:
(1)뿌리(Root)라 고 불 리 는 특정한 노드 만 있다.
(2)4.567914.1 일 때 나머지 노드 는 4n>서로 교차 하지 않 는 유한 집 으로 나 눌 수 있다m(m>0)그 중에서 모든 집합 자 체 는 나무 이 고 뿌리 라 고 부른다.
그 밖 에 나무의 정 의 는 다음 과 같은 두 가 지 를 강조해 야 한다.
(3)T1、T2、......、Tn시 뿌리 노드 는 유일한 것 이 고 여러 개의 노드 가 존재 할 수 없 으 며 데이터 구조 중의 나 무 는 한 개의 노드 만 있 을 수 있다.
(4)n>0시 자나무 의 개 수 는 제한 이 없 지만 서로 교차 하지 않 을 것 이다.
아래 그림 은 10 개의 노드 가 있 는 일반 나무의 구조 이다.

나무의 정 의 를 통 해 알 수 있 듯 이 나무의 정 의 는 재 귀적 인 방식 을 사용 했다.나무의 학습 과정 에서 중요 한 역할 을 한다.
이 진 트 리
2.1 이 진 트 리 정의
이 진 트 리 는m>0개 노드 의 유한 한 집합 으로 이 집합 또는 공 집(공 이 진 트 리 라 고 함)또는 한 개의 노드 와 두 그루 가 서로 교차 하지 않 고 각각 뿌리 노드 라 고 부 르 는 왼쪽 나무 와 오른쪽 나무 로 구성 된다.
그림 2.1 은 일반 이 진 트 리 구 조 를 보 여 준다.

2.2 이 진 트 리 특징
 이 진 트 리 의 정의 와 그림 분석 을 통 해 이 진 트 리 는 다음 과 같은 특징 이 있다.
(1)각 노드 에 최대 두 개의 서브 트 리 가 있 기 때문에 이 진 트 리 에는 2 보다 큰 노드 가 존재 하지 않 는 다.
(2)왼쪽 나무 와 오른쪽 나 무 는 순서 가 있 기 때문에 순서 가 임의로 뒤 바 뀌 어 서 는 안 된다.
(3)나무의 한 노드 에 한 그루 의 나무 만 있어 도 왼쪽 나무 인지 오른쪽 나무 인지 구분 해 야 한다.
이 진 트 리 는 동적 데이터 구조 이다.
코드 로 트 리 노드 를 표시 할 수 있 습 니 다.

class Node<E>{
  E e;
 Node left;
 Node right;
}

2.2.1 특성
1.이 진 트 리 는 천연 적 인 재 귀 구 조 를 가지 고 있다.
이것 은 각 노드 의 왼쪽 나무 와 오른쪽 나무 가 모두 이 진 트 리 이기 때문이다(어떤 경우).그림 과 같다.

2.2.2 2 분 트 리 종류(전시)
유형 1:

유형 2:

유형 3:

유형 4:

형식 5:

3.이 진 트 리 검색
3.1 정의
이 진 트 리(Binary Search Tree)는 질서 있 는 이 진 트 리(ordered binary tree),정렬 이 진 트 리(sorted binary tree)라 고도 부 릅 니 다.빈 트 리 나 다음 과 같은 성질 을 가 진 이 진 트 리 를 말 합 니 다.
1.임의의 노드 의 왼쪽 나무 가 비어 있 지 않 으 면 왼쪽 나무 에 있 는 모든 노드 의 값 은 뿌리 노드 의 값 보다 작 습 니 다.
2.임의의 노드 의 오른쪽 나무 가 비어 있 지 않 으 면 오른쪽 나무 에 있 는 모든 노드 의 값 은 그의 뿌리 노드 의 값 보다 크다.
3.임의의 노드 의 왼쪽,오른쪽 트 리 도 각각 두 갈래 로 나 무 를 찾는다.
4.키 가 같은 노드(no duplicate nodes)가 없습니다.
따라서 이 진 트 리 로 저 장 된 요 소 는 비교 가 가능 해 야 합 니 다.

3.2 두 갈래 검색 트 리 의 성질:
이 진 트 리 는 본질 적 으로 이 진 트 리 이기 때문에 위의 장 에서 말 한 이 진 트 리 의 성질 을 그 는 모두 가지 고 있다.
3.3 2 분 검색 트 리 의 사상:
이 진 트 리 의 검색 과정 은 차 우 이 진 트 리 와 유사 하 며,일반적으로 이 진 트 리 를 이 진 트 리 의 저장 구조 로 한다.중간 순서 로 이 진 트 리 를 옮 겨 다 니 면 키워드 의 질서 있 는 서열 을 얻 을 수 있 습 니 다.하나의 무질서 한 서열 은 이 진 트 리 를 구성 하여 질서 있 는 서열 로 바 꿀 수 있 습 니 다.트 리 를 구성 하 는 과정 은 바로 무질서 한 서열 을 정렬 하 는 과정 입 니 다.매번 삽 입 된 새로운 결점 은 이 진 정렬 트 리 에 있 는 새로운 잎 결점 입 니 다.삽입 작업 을 할 때 다른 결점 을 이동 할 필요 가 없습니다.특정한 결점 의 지침 을 바 꾸 고 빈 것 에서 비 어 있 는 것 으로 바 꾸 면 됩 니 다.검색,삽입,삭제 의 복잡 도 는 나무 높이 와 같 습 니 다n(n>=0)추 후 하나씩 학습 합 니 다.
4.프로 그래 밍 으로 두 갈래 검색 트 리 구현
4.1 기본 코드
이 진 트 리 에 저 장 된 요 소 는 비교 가능성 이 있어 야 하기 때문에 구현 시 BST 클래스 계승 Comparable 이 필요 합 니 다.

package BST;

public class BST<E extends Comparable<E>> {

  //     
  private class Node {
    public E e;
    public Node left, right;

    public Node(E e) {
      this.e = e;
      left = null;
      right = null;
    }
  }

  private Node root;//   
  private int size;

  public BST() {
    root = null;
    size = 0;
  }

  //           
  public int size() {
    return size;
  }

  //             
  public boolean isEmpty() {
    return size == 0;
  }
}

이 절 은 이 진 트 리 의 입문 이 라 고 할 수 있 으 며 추 후 계속 보완 되 고 업 데 이 트 될 것 입 니 다.
자바 알고리즘 과 관련 된 내용 에 관심 이 있 는 독자 들 은 본 사이트 의 주 제 를 볼 수 있 습 니 다.
본 고 에서 말 한 것 이 여러분 의 자바 프로 그래 밍 에 도움 이 되 기 를 바 랍 니 다.