JavaScript 이진 검색 트리의 정의 및 사용 예

이 글에서는 주로 자바스크립트 데이터 구조의 이진 검색 트리의 정의와 표현 방법을 소개하고, 이진 검색 트리의 개념과 특징, 그리고 이진 검색 트리의 생성, 삽입, 순회 및 기타 동작을 간략하게 설명합니다. 자바스크립트 구현 팁이 필요한 친구들은

을 참고하세요. 이 글에서는 자바스크립트 데이터 구조의 이진 검색 트리의 정의와 표현 방법을 예제를 통해 설명합니다. 참고할 수 있도록 모든 사람과 공유하세요. 자세한 내용은 다음과 같습니다.

Tree는 데이터를 계층적으로 저장하는 비선형 데이터 구조입니다. 트리는 계층적 관계로 데이터를 저장하는 데 사용됩니다. 예를 들어 파일 시스템의 파일은 순서가 지정된 목록을 저장하는 데에도 사용됩니다. 여기서는 특별한 종류의 트리인 이진 트리를 연구합니다. 이진 트리에서 검색하는 것은 매우 빠르고(연결된 목록에서 검색하는 것은 그렇지 않음) 이진 트리에서 요소를 추가하거나 제거하는 것도 매우 빠르기 때문에 이러한 기본 데이터 구조 대신 트리가 선택되었습니다. 배열은 그렇지 않습니다).

트리는 n개의 노드로 구성된 유한 집합입니다. 위쪽이 루트이고, 아래쪽이 루트의 하위 트리입니다. 트리 노드에는 데이터 요소와 해당 하위 트리를 가리키는 여러 가지가 포함되어 있습니다. 노드가 소유한 하위 트리를 노드의 차수라고 합니다. 차수가 0인 노드를 리프 또는 터미널 노드라고 합니다. 0이 아닌 차수를 갖는 노드를 비종단 노드 또는 분기 노드라고 합니다. 트리의 차수는 트리에 있는 각 노드의 차수의 최대값입니다. 노드의 계층 구조는 레벨 0인 루트부터 정의됩니다. 트리에 있는 노드의 최대 수준을 트리의 깊이 또는 높이라고 합니다.

바이너리 트리는 자식 노드가 2개 이하인 특별한 종류의 트리입니다. 이진 트리에는 일부 작업을 매우 효율적으로 만드는 몇 가지 특별한 계산 속성이 있습니다. 자식 노드 수를 2개로 제한함으로써 트리에 데이터를 삽입하고, 찾고, 삭제하는 효율적인 프로그램을 작성할 수 있습니다.

JavaScript를 사용하여 이진 트리를 구축하기 전에 트리에 대한 사전에 두 가지 새로운 용어를 추가해야 합니다. 부모 노드의 두 자식 노드를 각각 왼쪽 노드와 오른쪽 노드라고 합니다. 이진 트리의 일부 구현에서 왼쪽 노드에는 특정 값 집합이 포함되고 오른쪽 노드에는 또 다른 특정 값 집합이 포함됩니다. 이진 검색 트리는 상대적으로 작은 값이 왼쪽 노드에 저장되고, 큰 값이 오른쪽 노드에 저장되는 특별한 이진 트리입니다. 이 기능을 사용하면 단어, 문자열 등 숫자 데이터와 숫자가 아닌 데이터 모두에 대해 매우 효율적으로 검색할 수 있습니다.

이진 검색 트리는 노드로 구성되므로 Node 객체를 정의해야 합니다. 코드는 다음과 같습니다.

function Node(data,left,right){//结点类
    this.data=data;
    this.left=left;
    this.right=right;
    this.show=show;
}
function show(){//显示节点中数据
    return this.data;
}

여기서 왼쪽과 오른쪽은 다음과 같습니다. 각각 왼쪽과 오른쪽 자식 노드를 가리키는 데 사용됩니다.

다음으로 이진 검색 트리 클래스를 생성해야 합니다. 코드는 다음과 같습니다.

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 이진 검색 트리의 정의 및 사용 예의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!