이진 트리는 트리의 각 노드가 최대 두 개의 자식 노드를 가질 수 있는 특수한 유형의 트리입니다. 이러한 자식 노드를 오른쪽 자식과 왼쪽 자식이라고 합니다.
간단한 이진 트리는 -
나무를 나타내는 방법에는 두 가지가 있습니다.
- 연결 목록을 사용하는 동적 노드 표현
- 배열을 사용하는 순차 표현.
여기서는 이진 트리의 배열 표현에 대해 설명합니다. 이를 위해 BT의 노드에 번호를 매겨야 합니다. 이 번호는 0에서 (n-1) 또는 1에서 n으로 시작할 수 있습니다.
배열에서 노드와 해당 상위 및 하위 노드의 위치를 파생시킵니다.
0 인덱스 기반 시퀀싱을 사용하면
상위 노드가 인덱스 p라고 가정합니다.
그러면 left_child 노드는 인덱스 (2*p)+ 1에 있습니다.
right_child 노드는 인덱스 (2*p) + 2에 있습니다.
루트 노드는 인덱스 0에 있습니다.
left_child는 인덱스 1에 있습니다.
Right_child는 인덱스 2에 있습니다.
1개의 색인 기반 시퀀싱을 사용하면
상위 노드가 인덱스 p에 있다고 가정합니다.
Right_node는 색인(2*p)에 있습니다.
Left_node는 색인(2*p)+1에 있습니다. .
루트 노드는 인덱스 1에 있습니다.
left_child는 인덱스 2에 있습니다.
Right_child는 인덱스 3에 있습니다.
예
#include<bits/stdc++.h>
using namespace std;
char tree[10];
int rootnode(char key){
if(tree[0] != '\0')
cout<<"Tree already had root";
else
tree[0] = key;
return 0;
}
int leftchild(char key, int parent){
if(tree[parent] == '\0')
cout <<"\nCan't set child at"<<(parent * 2) + 1<<" , no parent found";
else
tree[(parent * 2) + 1] = key;
return 0;
}
int rightchild(char key, int parent){
if(tree[parent] == '\0')
cout<<"\nCan't set child at"<<(parent * 2) + 2<<" , no parent found";
else
tree[(parent * 2) + 2] = key;
return 0;
}
int traversetree(){
cout << "\n";
for(int i = 0; i < 10; i++){
if(tree[i] != '\0')
cout<<tree[i];
else
cout<<"-";
}
return 0;
}
int main(){
rootnode('A');
rightchild('C', 2);
leftchild('D', 0);
rightchild('E', 1);
rightchild('F', 2);
traversetree();
return 0;
} 출력
Can't set child at6 , no parent found Can't set child at6 , no parent found AD--E-----