JS 데이터 구조 와 알고리즘 - 이 진 트 리 와 이 진 트 리 찾기

나 무 는 비 선형 데이터 구조 로 층 을 나 누 어 데 이 터 를 저장 합 니 다.나 무 는 파일 시스템 의 파일 과 같은 계층 적 관 계 를 가 진 구 조 를 저장 하 는 데 사용 된다.나 무 는 서열 표를 저장 하 는 데 도 사용 된다.

이 진 트 리 와 이 진 트 리 는 특수 한 나무 로 그의 하위 노드 의 개 수 는 두 개 를 초과 하지 않 는 다.한 부모 노드 의 두 개의 키 노드 를 각각 왼쪽 노드 와 오른쪽 노드 라 고 부른다.이 진 트 리 (BST) 는 특수 한 이 진 트 리 입 니 다.상대 적 으로 작은 값 은 왼쪽 노드 에 있 고 비교적 큰 값 은 오른쪽 노드 에 저 장 됩 니 다.

js 코드 이 진 트 리 구현

먼저 Node 대상 을 정의 하여 데이터 (data) 를 저장 하고 다른 노드 와 의 링크 (left 와 right) 를 저장 합 니 다.

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

show 방법 정의

function show() {
  return this.data;
}

두 갈래 찾기 트 리 (BST)

를 나타 내 는 클래스 를 만 듭 니 다.

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

insert 방법 정의

function insert(data) {
  //         Node  
  var n = new Node(data,null,null);
  //  BST      ，    ，      ，           
  if(this.root == null) {
    this.root = n;
  }else {
    //       current          （   ）
    var current = this.root;
    var parent;
    while(true) {
      parent = current;
      //                  ，          null，               
      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;
        }
      }
    }
  }
}

이 진 트 리 를 옮 겨 다 니 며 BST 를 옮 겨 다 니 는 세 가지 방식 의 순서 가 있 습 니 다. 중간 순 서 는 노드 의 키 값 에 따라 상승 순 으로 BST 의 모든 노드 를 방문 합 니 다.우선 순위: 먼저 루트 노드 에 접근 한 다음 에 같은 방식 으로 왼쪽 트 리 와 오른쪽 트 리 에 접근 합 니 다.후 순: 후 순 서 는 먼저 잎 노드 (하위 노드 가 없 는 노드) 를 방문 하고 왼쪽 나무 에서 오른쪽 나무, 그리고 뿌리 노드 까지 옮 겨 다 닙 니 다.이 세 가 지 는 하나의 실현 코드 를 이해 하고 다른 것 은 모두 이해 하기 쉬 우 므 로 저 는 js 코드 실현 과정 에 대한 구체 적 인 이 해 를 다시 쓰 겠 습 니 다.

js 코드 는 중간 순서 로 중간 순 서 를 옮 겨 다 니 며 재 귀적 인 방식 으로 트 리 의 모든 노드 를 오름차 로 방문 하고 왼쪽 하위 트 리 를 먼저 방문 하 며 뿌리 노드 를 방문 한 다음 에 오른쪽 하위 트 리 를 방문 합 니 다.

function inOrder(node) {
  if(!(node == null)) {
    inOrder(node.left);
    console.log(node.show());
    inOrder(node.right);      
  }
}
//  ：
var nums = new BST();
nums.insert(56);
nums.insert(22);
nums.insert(81);
nums.insert(10);
nums.insert(30);
nums.insert(77);
nums.insert(92);

inOrder(nums.root); //10 22 30 56 81 77 92

① 왼쪽 트 리 를 끝까지 옮 겨 다 니 며 모든 push 를 하나의 배열 에 넣 고 먼저 이러한 결 과 를 얻 습 니 다 [56, 22, 10].
② 재 귀적 이 완료 되 었 습 니 다. 현재 pop 의 첫 번 째 항목 인 10 부터 오른쪽 트 리 를 옮 겨 다 니 기 시 작 했 습 니 다. undefined 입 니 다.
③ 그리고 pop 은 두 번 째 항목 인 22 를 내 고 오른쪽 트 리 를 옮 겨 다 니 며 30 을 얻 습 니 다. console 은 왼쪽 트 리 를 먼저 옮 겨 인쇄 한 것 이기 때문에 30 을 (push) 56 과 22 사이 에 꽂 았 습 니 다. 결 과 는 [56, 30, 22, 10] 입 니 다.
④ 그리고 pop 은 세 번 째 항목 인 30, undefined 를 낸다.
⑤ 그리고 pop 은 네 번 째 항목 인 56 을 내 고 이 오른쪽 나 무 를 옮 겨 다 니 며 결 과 를 얻 었 다. [92, 81, 56, 30, 22, 10]
⑥ 그리고 pop 은 다섯 번 째 항목 인 81 을 내 는데 왼쪽 트 리 77 이 있 기 때문에 push 가 들 어가 고 console 코드 가 중간 에 있 기 때문에 92 와 81 중간 에 넣 어야 한다. 결과 [92, 81, 77, 56, 30, 22, 10] 그래서 마지막 인쇄 결 과 는 10, 22, 30, 56, 77, 81, 92 이다.
하 나 를 이 해 했 습 니 다. 뒤의 순서 와 뒤 순 서 를 옮 겨 다 니 면 괜 찮 습 니 다. 다만 console 코드 가 놓 인 위치 가 다 릅 니 다.주로 재 귀 를 이해한다.

선착순 옮 겨 다 니 기

function inOrder(node) {
  if(!(node == null)) {
    console.log(node.show());
    inOrder(node.left);
    inOrder(node.right);      
  }
}
inOrder(nums.root);

뒷 차례 옮 겨 다 니 기

function inOrder(node) {
  if(!(node == null)) {
    inOrder(node.left);
    inOrder(node.right);      
    console.log(node.show());
  }
}
inOrder(nums.root);

참고 학습:
《 데이터 구조 와 알고리즘 자 바스 크 립 트 설명 》 《 고도 》.