binary tree data structure c
C ++의 이진 트리에 대한이 심층 자습서에서는 C ++에서 이진 트리의 유형, 표현, 탐색, 응용 프로그램 및 구현에 대해 설명합니다.
이진 트리는 널리 사용되는 트리 데이터 구조입니다. 트리의 각 노드에 최대 2 개의 자식 노드가있는 경우 트리를 이진 트리라고합니다.
따라서 일반적인 이진 트리에는 다음 구성 요소가 있습니다.
- 왼쪽 하위 트리
- 루트 노드
- 올바른 하위 트리
=> 이 시리즈의 전체 C ++ 자습서 목록을 확인하십시오.
학습 내용 :
C ++의 이진 트리
이진 트리의 그림 표현은 다음과 같습니다.
주어진 이진 트리에서 모든 수준의 최대 노드 수는 2입니다.l-1여기서‘l’은 레벨 번호입니다.
따라서 레벨 1의 루트 노드의 경우 최대 노드 수 = 21-1= 20= 1
이진 트리의 모든 노드에는 최대 2 개의 노드가 있으므로 다음 수준의 최대 노드는 2 * 2입니다.l-1.
최고의 파일 복구 소프트웨어 Windows 10
깊이 또는 높이가 h 인 이진 트리가 주어지면 높이가 h = 2 인 이진 트리의 최대 노드 수h- 1.
따라서 높이가 3 인 이진 트리 (위에 표시됨)에서 최대 노드 수 = 2삼-1 = 7.
이제 다양한 유형의 이진 트리에 대해 논의하겠습니다.
이진 트리의 유형
다음은 가장 일반적인 이진 트리 유형입니다.
# 1) 전체 이진 트리
모든 노드에 0 개 또는 2 개의 자식이있는 이진 트리를 전체 이진 트리라고합니다.
위에 표시된 것은 리프 노드를 제외한 모든 노드에 두 개의 자식이 있음을 볼 수있는 완전한 이진 트리입니다. L이 리프 노드의 수이고 'l'이 내부 또는 리프가 아닌 노드의 수이면 전체 이진 트리의 경우 L = l + 1입니다.
# 2) 완전한 이진 트리
완전한 이진 트리에는 마지막 레벨을 제외한 모든 레벨이 채워져 있고 마지막 레벨에는 왼쪽만큼 모든 노드가 있습니다.
위에 표시된 트리는 완전한 이진 트리입니다. 완전한 이진 트리의 일반적인 예는 이진 힙입니다.이 힙은 이후 자습서에서 설명합니다.
# 3) 완벽한 이진 트리
이진 트리는 모든 내부 노드에 두 개의 자식이 있고 모든 리프 노드가 동일한 수준에있을 때 완벽하다고합니다.
위에 표시된 이진 트리 예제는 각 노드에 두 개의 자식이 있고 모든 리프 노드가 동일한 수준에 있으므로 완벽한 이진 트리입니다.
높이 h의 완벽한 이진 트리에는 2가 있습니다.h– 1 개의 노드.
# 4) 퇴화 된 나무
각 내부 노드에 자식이 하나만있는 이진 트리를 퇴화 트리라고합니다.
위에 표시된 나무는 퇴화 나무입니다. 이 트리의 성능에 관한 한 퇴화 트리는 링크드리스트와 동일합니다.
# 5) 균형 잡힌 이진 트리
모든 노드의 두 하위 트리의 깊이가 1 이상 차이가없는 이진 트리를 균형 이진 트리라고합니다.
위에 표시된 이진 트리는 모든 노드의 두 하위 트리의 깊이가 1 이하이므로 균형 이진 트리입니다. 이후 자습서에서 논의 할 AVL 트리는 일반적인 균형 트리입니다.
이진 트리 표현
이진 트리에는 두 가지 방법으로 메모리가 할당됩니다.
# 1) 순차적 표현
이것은 트리 데이터 구조를 저장하는 가장 간단한 기술입니다. 배열은 트리 노드를 저장하는 데 사용됩니다. 트리의 노드 수는 배열의 크기를 정의합니다. 트리의 루트 노드는 배열의 첫 번째 인덱스에 저장됩니다.
일반적으로 노드가 i에 저장되면일위치는 왼쪽과 오른쪽 자식이 각각 2i 및 2i + 1 위치에 저장됩니다.
다음 이진 트리를 고려하십시오.
위의 이진 트리의 순차적 표현은 다음과 같습니다.
도움 데스크 인터뷰 질문 및 답변
위의 표현에서 각 노드의 왼쪽 및 오른쪽 자식이 각각 위치 2 * (node_location) 및 2 * (node_location) +1에 저장되어 있음을 알 수 있습니다.
예를 들어, 배열에서 노드 3의 위치는 3입니다. 따라서 왼쪽 자식은 2 * 3 = 6에 배치됩니다. 오른쪽 자식은 2 * 3 +1 = 7 위치에 있습니다. 배열에서 볼 수 있듯이 자식 6과 7 인 3 개 중 3 개는 어레이의 6 및 7 위치에 배치됩니다.
트리 노드를 저장하는 데 사용되는 배열이 메모리에서 많은 공간을 차지하므로 트리의 순차적 표현은 비효율적입니다. 트리가 커지면이 표현은 비효율적이고 관리하기 어려워집니다.
이 단점은 연결 목록에 트리 노드를 저장함으로써 극복됩니다. 트리가 비어 있으면 루트 노드를 저장하는 첫 번째 위치가 0으로 설정됩니다.
# 2) 링크드리스트 표현
이 유형의 표현에서 연결 목록은 트리 노드를 저장하는 데 사용됩니다. 여러 노드가 인접하지 않은 위치의 메모리에 흩어져 있으며 노드는 트리와 같은 부모-자식 관계를 사용하여 연결됩니다.
다음 다이어그램은 트리에 대한 연결 목록 표현을 보여줍니다.
위의 표현에서 볼 수 있듯이 각 연결 목록 노드에는 세 가지 구성 요소가 있습니다.
- 왼쪽 포인터
- 데이터 부분
- 오른쪽 포인터
왼쪽 포인터에는 노드의 왼쪽 자식에 대한 포인터가 있습니다. 오른쪽 포인터에는 노드의 오른쪽 자식에 대한 포인터가있는 반면 데이터 부분에는 노드의 실제 데이터가 포함됩니다. 주어진 노드 (리프 노드)에 대한 자식이 없으면 위 그림과 같이 해당 노드의 왼쪽 및 오른쪽 포인터가 null로 설정됩니다.
C ++에서 이진 트리 구현
다음으로 C ++에서 연결 목록 표현을 사용하여 이진 트리 프로그램을 개발합니다. 구조를 사용하여 단일 노드를 선언 한 다음 클래스를 사용하여 연결된 노드 목록을 개발합니다.
#include using namespace std; struct bintree_node{ bintree_node *left; bintree_node *right; int data; } ; class bst{ bintree_node *root; public: bst(){ root=NULL; } int isempty() { return(root==NULL); } void insert(int item); void displayBinTree(); void printBinTree(bintree_node *); }; void bst::insert(int item){ bintree_node *p=new bintree_node; bintree_node *parent; p->data=item; p->left=NULL; p->right=NULL; parent=NULL; if(isempty()) root=p; else{ bintree_node *ptr; ptr=root; while(ptr!=NULL){ parent=ptr; if(item>ptr->data) ptr=ptr->right; else ptr=ptr->left; } if(itemdata) parent->left=p; else parent->right=p; } } void bst::displayBinTree(){ printBinTree(root); } void bst::printBinTree(bintree_node *ptr){ if(ptr!=NULL){ printBinTree(ptr->left); cout<<' '<data<<' '; printBinTree(ptr->right); } } int main(){ bst b; b.insert(20); b.insert(10); b.insert(5); b.insert(15); b.insert(40); b.insert(45); b.insert(30); cout<<'Binary tree created: '< 산출:
생성 된 이진 트리 :
5 10 15 20 30 40 45
이진 트리 순회
트리에 대한 기본 튜토리얼에서 이미 순회에 대해 논의했습니다. 이 섹션에서는 이진 트리에 노드를 삽입하는 프로그램을 구현하고 이진 트리에 대한 세 가지 순회, 즉 inorder, preorder 및 postorder를 모두 보여줍니다.
#include using namespace std; //binary tree node declaration struct bintree_node{ bintree_node *left; bintree_node *right; char data; } ; class bintree_class{ bintree_node *root; public: bintree_class(){ root=NULL; } int isempty() { return(root==NULL); } void insert_node(int item); void inorder_seq(); void inorder(bintree_node *); void postorder_seq(); void postorder(bintree_node *); void preorder_seq(); void preorder(bintree_node *); }; void bintree_class::insert_node(int item){ bintree_node *p=new bintree_node; bintree_node *parent; p->data=item; p->left=NULL; p->right=NULL; parent=NULL; if(isempty()) root=p; else{ bintree_node *ptr; ptr=root; while(ptr!=NULL) { parent=ptr; if(item>ptr->data) ptr=ptr->right; else ptr=ptr->left; } if(itemdata) parent->left=p; else parent->right=p; } } void bintree_class::inorder_seq() { inorder(root); } void bintree_class::inorder(bintree_node *ptr) { if(ptr!=NULL){ inorder(ptr->left); cout<<' '<data<<' '; inorder(ptr->right); } } void bintree_class::postorder_seq() { postorder(root); } void bintree_class::postorder(bintree_node *ptr) { if(ptr!=NULL){ postorder(ptr->left); postorder(ptr->right); cout<<' '<data<<' '; } } void bintree_class::preorder_seq() { preorder(root); } void bintree_class::preorder(bintree_node *ptr) { if(ptr!=NULL){ cout<<' '<data<<' '; preorder(ptr->left); preorder(ptr->right); } } int main() { bintree_class bintree; bintree.insert_node('A'); bintree.insert_node('B'); bintree.insert_node('C'); bintree.insert_node('D'); bintree.insert_node('E'); bintree.insert_node('F'); bintree.insert_node('G'); cout<<'Inorder traversal:'< 산출:
순서 순회 :
A B C D E F G
우편 주문 순회 :
G F E D C B A
선주문 순회 :
A B C D E F G
이진 트리의 응용
이진 트리는 데이터 저장을 위해 많은 응용 프로그램에서 사용됩니다.
이진 트리의 중요한 응용 프로그램 중 일부는 다음과 같습니다.
- 이진 검색 트리 : 이진 트리는 많은 언어 라이브러리의 집합 및 맵과 같은 많은 검색 응용 프로그램에서 사용되는 이진 검색 트리를 구성하는 데 사용됩니다.
- 해시 트리 : 주로 특수한 이미지 서명 응용 프로그램에서 해시를 확인하는 데 사용됩니다.
- 힙 : 힙은 라우터, 운영 체제의 프로세서 스케줄링 등에 사용되는 우선 순위 대기열을 구현하는 데 사용됩니다.
- Huffman 코딩 : Huffman 코딩 트리는 압축 알고리즘 (예 : 이미지 압축) 및 암호화 애플리케이션에 사용됩니다.
- 구문 트리 : 컴파일러는 종종 프로그램에서 사용되는 표현식을 구문 분석하기 위해 이진 트리에 불과한 구문 트리를 구성합니다.
결론
바이너리 트리는 소프트웨어 업계에서 널리 사용되는 데이터 구조입니다. 이진 트리는 노드에 최대 2 개의 자식 노드가있는 트리입니다. 우리는 완전한 이진 트리, 완전한 이진 트리, 완벽한 이진 트리, 퇴행 된 이진 트리, 균형 이진 트리 등과 같은 다양한 유형의 이진 트리를 보았습니다.
바이너리 트리 데이터는 이전 튜토리얼에서 보았던 inorder, preorder 및 postorder 순회 기술을 사용하여 순회 할 수도 있습니다. 메모리에서 이진 트리는 연결 목록 (비 연속 메모리) 또는 배열 (순차적 표현)을 사용하여 표현 될 수 있습니다.
연결된 목록 표현은 배열이 많은 공간을 차지하기 때문에 배열과 비교할 때 더 효율적입니다.
=> 여기에서 최고의 C ++ 교육 자습서를 확인하십시오.
추천 도서