“ tt va kt ” fakulteti ii-bosqich ki sirtqi 13-20 guruh talabasi aslanov shohjahon uzoqovichning

 
Berilgan Prufer kodidan qanday qilib daraxt qurish mumkin?
Kirish: (4, 1, 3, 4) 
Chiqish: quyidagi daraxtning qirralari 
2 ---- 4 ---- 3 ---- 1 ---- 5 
| 
6 
Kirish: (1, 3, 5) 
Chiqish: quyidagi daraxtning qirralari 
2 ---- 1 ---- 3 ---- 5 ---- 4 
Berilgan Prufer kodining uzunligi m bo'lsin. G'oya m + 2 tepaliklarning bo'sh 
grafikasini yaratishdir. Birinchi elementni ketma-ketlikdan olib tashlaymiz. Joriy 
ketma-ketlikning birinchi elementi x bo'lsin. Keyin berilgan ketma-ketlikda 
bo'lmagan va hali daraxtga qo'shilmagan eng kichik qiymatni topamiz. Ushbu qiymat 
y bo'lsin. Biz $ x $ dan $ y $ ga chekka qo'shamiz va ushbu bosqichni takrorlaymiz. 
Yuqoridagi birinchi misol bilan daraxtni qurish algoritmini tushunaylik: 
1-qadam: Avval biz 6 ta vertikalning bo'sh grafikasini tuzamiz
va ketma-ketlikdan 4 ni oling.
2-qadam: 1 dan 6 gacha, eng kichik vertex emas
Prufer ketma-ketligi 2 ga teng.
3-qadam: Biz 2 va 4 orasida chekka hosil qilamiz.
2 ---- 4 1 3 5 6 

---

4-qadam: ketma-ketlikda 1 va mos keladi
eng past darajaga ega bo'lgan vertex 5 ga teng (2 ta bo'lgani kabi)
ko'rib chiqildi).
2 ---- 4 1 ---- 5 3 6 
5-qadam: Keyingi ketma-ketlik 3 va mos keladi
eng kichik darajaga ega vertex 1 ga teng
(chunki endi 1 Pruferning qolgan qatorining bir qismi emas)
2 ---- 4 3 ---- 1 ---- 5 6 
6-qadam: Keyingi ketma-ketlikda 4 va unga tegishli vertex 
eng kam daraja 3 ga teng (chunki 3 ko'rib chiqilmagan
kabi ketma-ketlikda mavjud emas) 
2 ---- 4 ---- 3 ---- 1 ---- 5 6 
7-qadam: Nihoyat, 1 dan 6 gacha ikkita tepalik qoldirildi (4 
va 6) shuning uchun biz ularga qo'shilamiz. 
2 ---- 4 ---- 3 ---- 1 ---- 5 
| 
6 
Bu 6 ta tepada kerakli daraxt. 
Quyidagi dastur. 
C ++ 
filter_none 
tahrirlash 
play_arrow 

---

yorqinlik_4 
// C++ program to construct tree from given Prufer Code
#include
using namespace std;
// Prints edges of tree represented by give Prufer code
void printTreeEdges(int prufer[], int m)
{
int vertices = m + 2;
int vertex_set[vertices];
// Initialize the array of vertices
for (int i = 0; i < vertices; i++)
vertex_set[i] = 0;
// Number of occurrences of vertex in code
for (int i = 0; i < vertices - 2; i++)
vertex_set[prufer[i] - 1] += 1;
cout << "\nThe edge set E(G) is :\n";
// Find the smallest label not present in
// prufer[].
int j = 0;
for (int i = 0; i < vertices - 2; i++) {
for (j = 0; j < vertices; j++) {
// If j+1 is not present in prufer set
if (vertex_set[j] == 0) {
// Remove from Prufer set and print

---

// pair.
vertex_set[j] = -1;
cout << "(" << (j + 1) << ", " 
<< prufer[i] << ") ";
vertex_set[prufer[i] - 1]--;
break;
}
}
}
j = 0;
// For the last element
for (int i = 0; i < vertices; i++) {
if (vertex_set[i] == 0 && j == 0) {
cout << "(" << (i + 1) << ", ";
j++;
}
else if (vertex_set[i] == 0 && j == 1)
cout << (i + 1) << ")\n";
}
}
// Driver code
int main()
{
int prufer[] = { 4, 1, 3, 4 };
int n = sizeof(prufer) / sizeof(prufer[0]);
printTreeEdges(prufer, n);

---

return 0;
}
Java 
filter_none 
tahrirlash 
play_arrow 
yorqinlik_4 
// Java program to construct tree from given Prufer Code
class GFG {
// Prints edges of tree represented by give Prufer code
static void printTreeEdges(int prufer[], int m)
{
int vertices = m + 2;
int vertex_set[] = new int[vertices];
// Initialize the array of vertices
for (int i = 0; i < vertices; i++)
vertex_set[i] = 0;
// Number of occurrences of vertex in code
for (int i = 0; i < vertices - 2; i++)
vertex_set[prufer[i] - 1] += 1;
System.out.print("\nThe edge set E(G) is :\n");
// Find the smallest label not present in
// prufer[].

---

int j = 0;
for (int i = 0; i < vertices - 2; i++) {
for (j = 0; j < vertices; j++) {
// If j+1 is not present in prufer set
if (vertex_set[j] == 0) {
// Remove from Prufer set and print
// pair.
vertex_set[j] = -1;
System.out.print("(" + (j + 1) + ", " 
+ prufer[i] + ") ");
vertex_set[prufer[i] - 1]--;
break;
}
}
}
j = 0;
// For the last element
for (int i = 0; i < vertices; i++) {
if (vertex_set[i] == 0 && j == 0) {
System.out.print("(" + (i + 1) + ", ");
j++;
}
else if (vertex_set[i] == 0 && j == 1)
System.out.print((i + 1) + ")\n");
}
}

---

// Driver code
public static void main(String args[])
{
int prufer[] = { 4, 1, 3, 4 };
int n = prufer.length;
printTreeEdges(prufer, n);
}
}
// This code is contributed by Arnab Kundu