Muszę wydrukować węzły drzewa binarnego za pomocą przejścia poziomu, ale w postaci spiralnej, tj. Węzły na różnym poziomie powinny być drukowane w postaci spiralnej.kolejność drukowania w kolejności drzewa binarnego w sposób Zygzak
dla np: Jeśli drzewo wyglądać następująco:
Wyjście powinno być 5 20 25 10 15 6 4.
Algorytm użyłem jest proste i jest tylko niewielka zmienność przejścia poziomu. Po prostu wziąłem zmienną p.if zmienna jest równa 1, niż wydrukowanie kolejności na danym poziomie od lewej do prawej, jeśli jest to -1, wydrukuj od prawej do lewej.
void getlevel(struct node *root,int n,int p)
{
if(root==NULL)
return;
if(n==0)
{
printf("%d ",root->info);
return;
}
if(n>0)
{
if(p==1)
{
getlevel(root->left,n-1,p);
getlevel(root->right,n-1,p);
}
if(p==-1)
{
getlevel(root->right,n-1,p);
getlevel(root->left,n-1,p);
}
}
}
Dostaję odpowiedź, ale najgorszym przypadku złożoność jest prawdopodobnie O (n^2) w przypadku skrzywienia drzewa.
Czy może być lepszy algorytm dla tego zadania? ..
Mój cały program jest here
Cóż możemy zrobić lepiej, to sprawdzić tutaj http://techieme.in/spiral-traversal/. Istnieje wiele sposobów rozwiązania tego problemu. – dharam