ไบนารีทรีเป็นชนิดพิเศษของทรี ซึ่งแต่ละโหนดของทรีสามารถมีโหนดรองได้ไม่เกินสองโหนด โหนดย่อยเหล่านี้เรียกว่าลูกด้านขวาและลูกด้านซ้าย
ต้นไม้ไบนารีอย่างง่ายคือ −
สำหรับเป็นตัวแทนของต้นไม้ มีสองวิธี
- การแสดงโหนดไดนามิกซึ่งใช้รายการที่เชื่อมโยง
- การแสดงตามลำดับซึ่งใช้อาร์เรย์
ในที่นี้ เราจะพูดถึงการแทนค่าอาร์เรย์ของไบนารีทรี สำหรับสิ่งนี้ เราจำเป็นต้องนับจำนวนโหนดของ 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-----
