Cây nhị phân là một loại cây đặc biệt trong đó mỗi nút của cây có thể có nhiều nhất hai nút con. Các nút con này được gọi là nút con phải và nút con trái.
Một cây nhị phân đơn giản là -
Để đại diện cho cây, có hai cách,
- biểu diễn nút động sử dụng danh sách được liên kết
- Biểu diễn tuần tự sử dụng mảng.
Ở đây, chúng ta sẽ thảo luận về biểu diễn mảng của cây nhị phân. Đối với điều này, chúng ta cần đánh số các nút của BT. Việc đánh số này có thể bắt đầu từ 0 đến (n-1) hoặc từ 1 đến n.
Cho phép lấy vị trí của các nút và các nút cha và con của chúng trong mảng.
Khi chúng tôi sử dụng 0 trình tự dựa trên chỉ mục,
Giả sử nút cha là một chỉ mục p.
Sau đó, nút left_child ở chỉ mục (2 * p) + 1.
Nút right_child ở chỉ mục (2 * p) + 2.
Nút gốc ở chỉ số 0.
left_child ở chỉ mục 1.
Right_child ở chỉ mục 2.
Khi chúng tôi sử dụng 1 trình tự dựa trên chỉ mục,
Giả sử nút cha ở chỉ mục p,
Right_node ở index (2 * p).
Left_node ở chỉ mục (2 * p) +1 .
Nút gốc ở chỉ mục 1.
left_child ở chỉ mục 2.
Right_child ở chỉ mục 3.
Ví dụ
#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;
} Đầu ra
Can't set child at6 , no parent found Can't set child at6 , no parent found AD--E-----