이진 트리의 개념
이진 트리는 유한 N (n> = 0) 노드 세트입니다. 이 세트는 빈 세트 (빈 바이너리 트리)이거나 루트 노드와 오른쪽 서브 트리라고하는 루트 노드와 서로 교차하지 않는 2 개의 이진 트리로 구성됩니다.
이진 나무의 특성
각 노드에는 최대 두 개의 하위 트리가 있으므로 이진 트리에 2도가 큰 노드가 없습니다. 이진 트리의 각 노드는 객체이며 각 데이터 노드에는 3 개의 포인터, 즉 부모, 왼쪽 자식 및 오른쪽 자식에 대한 포인터가 있습니다. 각 노드는 포인터를 통해 서로 연결됩니다. 연결된 포인터 사이의 관계는 모든 아버지 아들 관계입니다.
이진 트리 노드의 정의
이진 트리 노드는 다음과 같이 정의됩니다.
코드 사본은 다음과 같습니다.
구조 BinaryTreenode
{
int m_nvalue;
binarytreenode* m_pleft;
binarytreenode* m_pright;
};
이진 나무의 5 가지 기본 형태
빈 바이너리 트리
루트 노드는 하나뿐입니다
루트 노드에는 왼쪽 하위 트리 만 있습니다
루트 노드에는 오른쪽 하위 트리 만 있습니다
루트 노드에는 왼쪽과 오른쪽 하위 트리가 모두 있습니다.
2 ~ 3 개의 노드가있는 평범한 나무에는 두 개의 사례가 있습니다. 그러나 이진 트리는 왼쪽과 오른쪽을 구별해야하므로 다음 5 가지 형태로 발전합니다.
특수 바이너리 트리
경사 나무
위의 두 번째 하위 그림에서 두 번째 및 세 번째 작은 그림에서 볼 수 있듯이.
전체 바이너리 트리
이진 트리에서 모든 분기 노드에 왼쪽 및 오른쪽 서브 트리가 있고 모든 잎이 동일한 층에있는 경우, 이진 트리를 전체 바이너리 트리라고합니다. 아래 그림과 같이 :
완전한 이진 트리
완전히 바이너리 트리는 마지막 층이 왼쪽에 가득 차 있고 오른쪽이 가득 찼거나 나머지 층이 가득 차 있음을 의미합니다. 깊이의 깊이와 다수의 노드가 2^k -1 인 이진 트리는 전체 이진 트리 (완전한 이진 트리)입니다. 그것은 깊이와 공간이없는 나무입니다.
완전히 이진 트리의 특성은 다음과 같습니다.
잎 노드는 가장 낮은 두 층으로 만 나타날 수 있습니다.
가장 낮은 잎은 왼쪽의 연속 위치에 집중되어야합니다.
두 번째 층에서 잎 노드가있는 경우 오른쪽에 연속적인 위치에 있어야합니다.
노드 학위가 1 인 경우 노드에는 왼쪽 자식 만 있습니다.
동일한 노드 트리가있는 이진 트리의 경우 완전한 바이너리 트리는 깊이가 가장 작습니다.
참고 : 전체 바이너리 트리는 완전히 이진 트리 여야하지만 완전히 바이너리 트리는 전체 이진 트리가 아닐 수 있습니다.
알고리즘은 다음과 같습니다.
코드 사본은 다음과 같습니다.
bool is_complete (트리 *루트)
{
대기열 Q;
나무 *ptr;
// 너비 우선 순위 (계층 적 트래버스)를 수행하고 널 노드를 큐에 넣습니다.
Q.push (루트);
while ((ptr = q.pop ())! = null)
{
Q.push (ptr-> 왼쪽);
Q.push (ptr-> 오른쪽);
}
// 액세스되지 않은 노드가 있는지 여부를 결정합니다.
while (! q.is_empty ())
{
ptr = q.pop ();
// 액세스하지 않은 노드가없는 경우 트리에는 공허가 있고 불완전한 바이너리 트리입니다.
if (null! = ptr)
{
거짓을 반환합니다.
}
}
진실을 반환하십시오.
}
이진 나무의 특성
이진 트리의 속성 1 : 이진 트리의 i-th 층에 최대 2^(i-1) 노드가 있습니다 (i> = 1)
이진 트리의 속성 2 : 깊이 k를 가진 이진 트리는 최대 2^k-1 노드 (k> = 1)
이진 트리의 순차적 저장 구조
이진 트리의 순차적 저장 구조는 1 차원 배열을 사용하여 각 노드를 이진 트리에 저장하는 것이며, 노드의 저장 위치는 노드 간의 논리적 관계를 반영 할 수 있습니다.
이진 링크 목록
순차적 인 저장 방법은 그다지 적용 할 수 없으므로 체인 저장 구조를 고려해야합니다. 국제 실습에 따르면 이진 트리 저장소는 일반적으로 체인 저장 구조를 채택합니다.
이진 트리의 각 노드에는 최대 두 명의 어린이가 있으므로 데이터 필드와 두 개의 포인터 필드를 설계하는 것은 자연스러운 아이디어입니다. 우리는 그러한 링크 된 목록을 바이너리 링크 목록이라고합니다.
이진 나무의 횡단
이진 트리를 가로 지르는 것은 이진 트리의 모든 노드에 루트 노드에서 특정 순서로 액세스하여 각 노드가 한 번만 액세스하도록합니다.
다음과 같이 이진 나무를 가로 지르는 세 가지 방법이 있습니다.
(1) 사전 주문 트래버스 (DLR), 먼저 루트 노드에 액세스 한 다음 왼쪽 하위 트리를 가로 지르고 마침내 오른쪽 하위 트리를 가로 지릅니다. 약어 뿌리 - 왼쪽 - 오른쪽.
(2) 순서의 순서 (LDR), 먼저 왼쪽 하위 트리를 트래버스 한 다음 루트 노드에 액세스 한 다음 결국 오른쪽 하위 트리를 가로 질러옵니다. 약어 노트 : 왼쪽 root-right.
(3) 먼저 왼쪽 하위 트리를 통과 한 다음 오른쪽 하위 트리를 가로 지르고 마침내 루트 노드에 액세스합니다. 약식 왼쪽 뿌리.
프리앰블 트래버스 :
이진 트리가 비어 있으면 빈 작업이 반환됩니다. 그렇지 않으면 먼저 루트 노드에 액세스 한 다음 이전 순서에서 왼쪽 하위 트리를 통과 한 다음 이전 순서에서 오른쪽 하위 트리를 통과합니다.
횡단의 순서는 다음과 같습니다. abdhiejcfkg
코드 사본은 다음과 같습니다.
// 정확한 순회
함수 선주문 (노드) {
if (! node == null) {
putstr (node.show ()+ "");
선주문 (node.left);
선주문 (node.right);
}
}
순차적 인 트래버스 :
트리가 비어 있으면 빈 작업이 반환되고 그렇지 않으면 루트 노드에서 시작되고 (루트 노드가 먼저 액세스되지 않음) 루트 노드의 왼쪽 하위 트리가 중간 순서에서 통과되면 루트 노드가 액세스되고 오른쪽 하위 트리가 중간 순서로 이동됩니다.
횡단 순서는 다음과 같습니다. hdibejafkcg
코드 사본은 다음과 같습니다.
// 재귀 메소드를 사용하여 중간수 트래버스를 구현합니다
내부 기능 (노드) {
if (! (node == null)) {
Inder (node.left); // 먼저 왼쪽 하위 트리에 추가합니다
putstr (node.show ()+ ""); // 루트 노드에 다시 추가하십시오
Inder (node.right); // 오른쪽 서브 트리에 마지막으로 액세스합니다
}
}
주문 후 트래버스 :
나무가 비어 있으면 빈 작업이 반환됩니다. 그렇지 않으면 왼쪽 및 오른쪽 하위 트리가 왼쪽에서 오른쪽으로 이동하여 왼쪽 및 오른쪽 하위 트리에 액세스하고 루트 노드에 액세스합니다.
트래버스의 순서는 다음과 같습니다. hidjebkfgca
코드 사본은 다음과 같습니다.
// 주문 후 트래버스
기능 우편 주문형 (노드) {
if (! node == null) {
우체류 (node.left);
우체류 (Node.right);
putstr (node.show ()+ "");
}
}
이진 검색 트리를 구현하십시오
바이너리 룩업 트리 (BST)는 노드로 구성되므로 노드 노드 객체를 다음과 같이 정의합니다.
코드 사본은 다음과 같습니다.
함수 노드 (데이터, 왼쪽, 오른쪽) {
this.data = 데이터;
this.left = 왼쪽; // 왼쪽 노드 링크를 저장합니다
이것은 오른쪽 = 오른쪽;
this.show = show;
}
함수 show () {
this.data; // 노드에 저장된 데이터를 표시합니다
}
최대 및 최소값을 찾으십시오
BST에서 최소 및 최대 값을 찾는 것은 작은 값이 항상 왼쪽 하위 노드에 있고 BST의 최소 값을 찾고 있기 때문에 매우 간단합니다. 마지막 노드가 발견 될 때까지 왼쪽 하위 트리를 가로 지르십시오.
최소값을 찾으십시오
코드 사본은 다음과 같습니다.
함수 getMin () {
var current = this.root;
while (! (current.left == null)) {
current = current.left;
}
return current.data;
}
이 방법은 BST의 왼쪽 하위 트리를 따라 하나씩 BST의 가장 왼쪽 노드로 이동할 때까지 하나씩 이동합니다.
코드 사본은 다음과 같습니다.
current.left = null;
현재 현재 노드에 저장된 값은 최소값입니다.
최대 값을 찾으십시오
BST에서 최대 값을 찾으려면 마지막 노드가 발견 될 때까지 오른쪽 서브 트리를 가로 지르고 해당 노드에 저장된 값은 최대 값입니다.
코드 사본은 다음과 같습니다.
함수 getMax () {
var current = this.root;
while (! (current.right == null)) {
current = current.right;
}
return current.data;
}