JavaScript 데이터 구조의 두 갈래 찾기 트 리 의 정의 와 표시 방법

본 고의 실례 는 자 바스 크 립 트 데이터 구조의 두 갈래 찾기 트 리 의 정의 와 표시 방법 을 설명 한다.여러분 께 참고 하도록 공유 하 겠 습 니 다.구체 적 으로 는 다음 과 같 습 니 다.
나 무 는 비 선형 데이터 구조 로 층 을 나 누 어 데 이 터 를 저장 합 니 다.트 리 는 파일 시스템 의 파일 과 같은 계층 적 관 계 를 가 진 데 이 터 를 저장 하 는 데 사 용 됩 니 다.나 무 는 서열 표를 저장 하 는 데 도 사용 된다.이곳 에 서 는 특수 한 나무 인 이 진 트 리 를 연구 할 것 이다.기본 적 인 데이터 구조 가 아 닌 트 리 를 선택 하 는 것 은 이 진 트 리 에서 검색 하 는 것 이 매우 빠 르 기 때 문 입 니 다.(링크 에서 찾 는 것 은 그렇지 않 습 니 다)이 진 트 리 에 요 소 를 추가 하거나 삭제 하 는 것 도 매우 빠 릅 니 다.(배열 에 추가 하거나 삭제 하 는 것 은 그렇지 않 습 니 다)
나 무 는 n 개의 결점 의 유한 집합 이다.맨 위의 것 은 뿌리 이 고,아래 는 뿌리 인 나무 다.나무의 노드 는 데이터 요소 와 하위 트 리 를 가리 키 는 가 지 를 포함 합 니 다.결점 이 있 는 자 수 를 결점 의 도 라 고 한다.도 0 의 결점 을 잎 이나 단말기 결점 이 라 고 한다.도 0 이 아 닌 결점 을 비 단말기 결점 이나 지점 결점 이 라 고 한다.나무의 도 는 나무 안의 각 결점 의 도의 최대 치 이다.결점 의 층 차 는 뿌리 부터 정의 하고 뿌리 는 0 층 이다.나무의 결점 의 최대 층 차 를 나무의 깊이 나 높이 라 고 한다.
이 진 트 리 는 특수 한 나무 로 그 하위 노드 의 개 수 는 두 개 를 초과 하지 않 는 다.이 진 트 리 는 특수 한 계산 성질 을 가지 고 있어 서 그들 위 에 있 는 일부 조작 이 매우 효율 적 이다.하위 노드 의 개 수 를 2 로 제한 함으로써 효율 적 인 프로그램 이 트 리 에 데 이 터 를 삽입 하고 찾 으 며 삭제 할 수 있 습 니 다.
자 바스 크 립 트 를 사용 하여 이 진 트 리 를 구축 하기 전에 트 리 에 관 한 사전 에 두 개의 새로운 명 사 를 추가 해 야 합 니 다.한 부모 노드 의 두 개의 키 노드 를 각각 왼쪽 노드 와 오른쪽 노드 라 고 부른다.일부 이 진 트 리 의 실현 에 있어 왼쪽 노드 는 특정한 값 을 포함 하고 오른쪽 노드 는 다른 그룹의 특정한 값 을 포함한다.이 진 트 리 는 특수 한 이 진 트 리 로 상대 적 으로 작은 값 은 왼쪽 노드 에 저장 되 고 큰 값 은 오른쪽 노드 에 저 장 됩 니 다.이 특성 으로 인해 검색 의 효율 이 높 습 니 다.수치 형 과 비 수치 형 데이터,예 를 들 어 단어 와 문자열 등 이 모두 이와 같 습 니 다.
두 갈래 찾기 트 리 는 노드 로 구성 되 어 있 기 때문에 노드 대상 을 정의 해 야 합 니 다.코드 는 다음 과 같 습 니 다.

function Node(data,left,right){//   
    this.data=data;
    this.left=left;
    this.right=right;
    this.show=show;
}
function show(){//       
    return this.data;
}

그 중에서 left 와 right 는 각각 좌우 자 결점 을 가리 키 는 데 쓰 인 다.
다음은 두 갈래 로 트 리 의 종 류 를 찾 아야 합 니 다.코드 는 다음 과 같 습 니 다.

function BST(){//  
    this.root=null;
    this.insert=insert;
    this.inOrder=inOrder;
    this.preOrder=preOrder;
    this.postOrder=postOrder;
}

다음은 노드 를 삽입 하 는 코드 입 니 다.작은 것 은 왼쪽 에 꽂 고 큰 것 은 오른쪽 에 꽂 습 니 다.코드 는 다음 과 같 습 니 다:

function insert(data){//    
    var n=new Node(data,null,null);
    if(this.root==null){//     
      this.root=n;
    }else{
      var current=this.root;//       
      var parent;
      while(true){//                 
        parent=current;
        if(data<current.data){
          current=current.left;
          if(current==null){//       
            parent.left=n;
            break;
          }
        }else{
          current=current.right;
          if(current==null){//       
            parent.right=n;
            break;
          }//      ，   while    ，      parent      
        }
      }
    }
}

자 바스 크 립 트 와 관련 된 내용 에 관심 이 있 는 독자 들 은 본 사이트 의 주 제 를 볼 수 있 습 니 다.,,,JavaScript 데이터 구조 와 알고리즘 기술 총화,JavaScript 수학 연산 용법 총화,JavaScript 정렬 알고리즘 요약,JavaScript 스 트 리밍 알고리즘 및 기술 총화과JavaScript 찾기 알고리즘 기술 총화.
본 고 에서 말 한 것 이 여러분 의 자 바스 크 립 트 프로 그래 밍 에 도움 이 되 기 를 바 랍 니 다.