trees c basic terminology
C ++ 트리에 대한이 심층 자습서에서는 트리 유형, 트리 탐색 기법 및 그림 및 예제 프로그램을 사용한 기본 용어를 설명합니다.
이 C ++ 시리즈에서 지금까지 우리는 정적 및 동적 특성의 선형 데이터 구조를 보았습니다. 이제 우리는 비선형 데이터 구조를 진행할 것입니다. 이 범주의 첫 번째 데이터 구조는 '트리'입니다.
트리는 비선형 계층 적 데이터 구조입니다. 트리는 방향이 있거나 방향이없는 '가장자리'를 통해 서로 연결된 노드 모음입니다. 노드 중 하나는 '루트 노드'로 지정되고 나머지 노드는 자식 노드 또는 루트 노드의 리프 노드라고합니다.
일반적으로 각 노드는 많은 하위 노드를 가질 수 있지만 상위 노드는 하나만 가질 수 있습니다.
트리의 노드는 자매 노드라고하는 동일한 수준에 있거나 부모-자식 관계를 가질 수 있습니다. 부모가 동일한 노드는 형제 노드입니다.
학습 내용 :
C ++의 트리
다음은 다양한 부분이있는 예제 트리입니다.
나무에 사용하는 몇 가지 기본 용어에 대한 정의를 살펴 보겠습니다.
- 루트 노드 : 이것은 트리 계층 구조에서 최상위 노드입니다. 위의 다이어그램에서 노드 A는 루트 노드입니다. 루트 노드에는 상위 노드가 없습니다.
- 리프 노드 : 트리 계층 구조에서 최하위 노드입니다. 리프 노드는 자식 노드가없는 노드입니다. 외부 노드라고도합니다. 위 트리의 노드 E, F, G, H 및 C는 모두 리프 노드입니다.
- 하위 트리 : 하위 트리는 루트가 null이 아닐 때 노드의 다양한 하위 항목을 나타냅니다. 트리는 일반적으로 루트 노드와 하나 이상의 하위 트리로 구성됩니다. 위 다이어그램에서 (B-E, B-F) 및 (D-G, D-H)는 하위 트리입니다.
- 부모 노드 : 자식 노드가 있고 부모쪽으로 위쪽 가장자리가있는 루트 노드를 제외한 모든 노드.
- Ancestor Node : 루트에서 해당 노드로의 경로에있는 선행 노드입니다. 루트에는 조상이 없습니다. 위의 다이어그램에서 A와 B는 E의 조상입니다.
- 키: 노드의 값을 나타냅니다.
- 수평: 노드의 생성을 나타냅니다. 루트 노드는 항상 레벨 1에 있습니다. 루트의 하위 노드는 레벨 2에 있고 루트의 손자는 레벨 3에 있습니다. 일반적으로 각 노드는 상위 노드보다 높은 수준에 있습니다.
- 통로: 경로는 연속 된 가장자리의 시퀀스입니다. 위의 다이어그램에서 E의 경로는 A => B-> E입니다.
- 정도: 노드의 정도는 노드에있는 자식의 수를 나타냅니다. 위의 다이어그램에서 B와 D의 차수는 각각 2이고 C의 차수는 0입니다.
C ++ 트리 유형
트리 데이터 구조는 아래 다이어그램과 같이 다음과 같은 하위 유형으로 분류 할 수 있습니다.
# 1) 일반 나무
일반 트리는 트리의 기본 표현입니다. 하나의 노드와 하나 이상의 자식 노드가 있습니다. 최상위 노드, 즉 루트 노드는 수준 1에 있고 다른 모든 노드는 다양한 수준에있을 수 있습니다.
일반 트리는 아래 그림과 같습니다.
위 그림에서 볼 수 있듯이 일반 트리에는 여러 하위 트리가 포함될 수 있습니다. 노드 B, C 및 D는 레벨 2에 있으며 형제 노드입니다. 마찬가지로 노드 E, F, G 및 H도 형제 노드입니다.
네트워크 엔지니어 인터뷰 질문 250 + 질문 및 답변 설명 pdf
다른 수준에있는 노드는 부모-자식 관계를 나타낼 수 있습니다. 위 그림에서 노드 B, C 및 D는 A의 자식입니다. 노드 E와 F는 B의 자식이고 노드 G와 H는 D의 자식입니다.
일반적인 트리는 C ++ 구현을 사용하여 아래에 설명되어 있습니다.
#include using namespace std; //declaration for new tree node struct node { int data; struct node *left; struct node *right; }; //allocates new node struct node* newNode(int data) { // declare and allocate new node struct node* node = new struct node(); node->data = data; // Assign data to this node // Initialize left and right children as NULL node->left = NULL; node->right = NULL; return(node); } int main() { /*create root node*/ struct node *rootNode = newNode(10); cout<<'General tree created is as follows:'<data<left = newNode(20); rootNode->right = newNode(30); cout<<' '<left->data<<' '<right->data; cout<left->left = newNode(40); cout<<' '<<'/'<left->left->data; return 0; } 산출:
생성되는 일반 트리는 다음과 같습니다.
10
/
20 30
makefile C ++ 만들기
/
40
# 2) 숲
트리에서 루트 노드를 삭제하고 다음 레벨 요소와 루트를 연결하는 가장자리를 삭제할 때마다 아래와 같이 분리 된 트리 세트를 얻습니다.
위 그림에서 루트 노드 A와 루트 노드를 노드 B, C, D에 연결하는 세 개의 에지를 삭제하여 두 개의 포리스트를 얻었습니다.
# 3) 이진 트리
각 노드에 최대 2 개의 자식 노드가있는 트리 데이터 구조를 이진 트리라고합니다. 이진 트리는 가장 널리 사용되는 트리 데이터 구조이며 표현식 평가, 데이터베이스 등과 같은 다양한 응용 프로그램에서 사용됩니다.
다음 그림은 이진 트리를 보여줍니다.
위 그림에서 노드 A, B, D에는 각각 두 개의 자식이 있습니다. 각 노드에 정확히 0 개 또는 두 개의 자식이있는 이진 트리를 전체 이진 트리라고합니다. 이 트리에는 자식이 하나 인 노드가 없습니다.
완전한 이진 트리에는 왼쪽에서 오른쪽으로 채워지는 최하위 레벨을 제외하고 완전히 채워진 이진 트리가 있습니다. 위에 표시된 이진 트리는 완전한 이진 트리입니다.
다음은 이진 트리를 보여주는 간단한 프로그램입니다. 트리의 출력은 입력 트리의 순회 순회 시퀀스입니다.
#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
# 4) 이진 검색 트리
정렬 된 이진 트리를 이진 검색 트리라고합니다. 이진 검색 트리에서 왼쪽의 노드는 루트 노드보다 작은 반면 오른쪽의 노드는 루트 노드보다 크거나 같습니다.
이진 검색 트리의 예는 다음과 같습니다.
위 그림에서 왼쪽 노드가 모두 루트 요소 인 20 개 미만임을 알 수 있습니다. 반면 오른쪽 노드는 루트 노드보다 큽니다. 이진 검색 트리는 검색 및 정렬 기술에 사용됩니다.
# 5) 표현식 트리
간단한 산술 표현식을 평가하는 데 사용되는 이진 트리를 표현식 트리라고합니다.
간단한 표현식 트리가 아래에 나와 있습니다.
위의 샘플 표현식 트리에서 (a + b) / (a-b) 표현식을 나타냅니다. 위 그림에서 볼 수 있듯이 트리의 리프가 아닌 노드는 표현식의 연산자를 나타내고 리프 노드는 피연산자를 나타냅니다.
Windows 10을위한 최고의 디스크 클리너
표현식 트리는 주로 대수 표현식을 해결하는 데 사용됩니다.
트리 순회 기법
배열, 연결 목록, 스택, 큐 등과 같은 선형 데이터 구조를 보았습니다. 이러한 모든 데이터 구조는 구조를 한 방향, 즉 선형으로 만 순회하는 공통 순회 기술을 가지고 있습니다.
그러나 트리의 경우 아래와 같이 다른 순회 기술이 있습니다.
# 1) 순서대로 : 이 순회 기법에서는 왼쪽 하위 트리에 더 이상 노드가 없을 때까지 왼쪽 하위 트리를 먼저 순회합니다. 그런 다음 루트 노드를 방문한 다음 오른쪽 하위 트리에서 탐색 할 노드가 더 이상 없을 때까지 오른쪽 하위 트리를 탐색합니다. 따라서 inOrder 순회 순서는 left-> root-> right입니다.
# 2) 선주문 : 사전 주문 순회 기법의 경우 루트 노드를 먼저 처리 한 다음 전체 왼쪽 하위 트리를 순회하고 마지막으로 오른쪽 하위 트리를 순회합니다. 따라서 사전 주문 순회 순서는 루트-> 왼쪽-> 오른쪽입니다.
# 3) 주문 후 : 주문 후 순회 기법에서는 왼쪽 하위 트리, 오른쪽 하위 트리, 마지막으로 루트 노드를 순회합니다. postorder 기법의 순회 순서는 left-> right-> root입니다.
n이 루트 노드이고‘l’및’r’이 각각 트리의 왼쪽 및 오른쪽 노드 인 경우 트리 순회 알고리즘은 다음과 같습니다.
In order (lnr) 알고리즘 :
- inOrder (left- Subtree)를 사용하여 왼쪽 하위 트리를 탐색합니다.
- 루트 노드 (n)를 방문하십시오.
- inOrder (right- subtree)를 사용하여 오른쪽 하위 트리를 탐색합니다.
선주문 (nlr) 알고리즘 :
- 루트 노드 (n)를 방문하십시오.
- preorder (left-subtree)를 사용하여 왼쪽 하위 트리를 탐색합니다.
- preorder (right-subtree)를 사용하여 오른쪽 하위 트리를 탐색합니다.
LRN (Postorder) 알고리즘 :
- postOrder (left-subtree)를 사용하여 왼쪽 하위 트리를 탐색합니다.
- postOrder (right-subtree)를 사용하여 오른쪽 하위 트리를 탐색합니다.
- 루트 노드 (n)를 방문하십시오.
위의 순회 기법 알고리즘을 통해 원하는 결과를 얻기 위해 해당 기법을 반복적으로 주어진 트리에 적용 할 수 있음을 알 수 있습니다.
다음 트리를 고려하십시오.
위의 순회 기술을 사용하여 위의 트리에 대한 순회 순서는 다음과 같습니다.
- 주문 순회 : 2 3 5 6 10
- 선주문 순회 : 6 3 2 5 10
- 주문 후 순회 : 2 5 3 10 6
결론
트리는 소프트웨어 분야의 많은 응용 프로그램에서 사용되는 비선형 계층 데이터 구조입니다.
목록을 순회하는 한 가지 방법 만있는 선형 데이터 구조와 달리, 다양한 방식으로 트리를 순회 할 수 있습니다. 이 튜토리얼에서는 순회 기법과 다양한 유형의 트리에 대해 자세히 연구했습니다.
추천 도서
