N-ary koks ar spoguļattēlu.

[Ezeliitis]

Valoda: C++.

Doma sekojoša. Man ir .txt fails, kurš tiek pierakstīts šādi:

1 2 3 4 5
3 6 7
5 8
8 9 10 11
0 

VAI

5 8

3 6 7
8 9 10 11
1 2 3 4 5
0

,kur pirmais cipars ir vecāks un tālāk sekojošie cipari ir bērni. Man šo visu vajag paņemt un pārmest spoguļattēlā un iegūt:

1 5 4 3 2
5 8
8 11 10 9
3 7 6
0

 

 

Ir kādas idejas?

 

Doma ir strukturēt šādi: (saprotu, ka kaut kas aizlaists pakaļā, jo sēžu 5h jau un vairs nesaprotu kas ir kas...)

const int MAX_CHILD = 100;

struct TreeNode {
  int val;
  TreeNode *children[MAX_CHILD];
  TreeNode(int x) : val(x) {
  for(int i = 0; i < MAX_CHILD; ++i) {
  children[i] = nullptr;
  }
  }
};

Node *newNode(int val){
  TreeNode *temp = new TreeNode;
  temp->val= val;
  return temp;
}

TreeNode* invertTree(TreeNode* root) {
  if(!root) {
  return root;
 }
 
 for(int i = 0; i < MAX_CHILD; ++i) {
 invertTree(children[i]);
 }

 // reverse the children nodes array
 for(int left = 0, right = MAX_CHILD - 1; left < right; left++, right--) {
 swap(children[left], children[right]);
 }

 return root;
 }

 

main()..
newNode(funkcija_atgriez_masivu_ar_values);

 

Varbūt kāds redz kādu foršu un vieglu veidu kā šo visu labot? Varbūt neņemties ar masīviem. Koks ir statisks - bez insertion/deletion.
 

Labots Novembris 16, 2016 - Ezeliitis

[nevertell]

Puis, iemācies apstaigāt koku. Ir divi veidi kā to darīt.

 

Bet nu naīvā implementācija ir katram noudam apgriezt secību pointeriem. Šitas ir LU mājasdarbs?

[binary]

 

 

Bet nu naīvā implementācija ir (..)

Naivajā implementācijā es nemaz neredzu, kur tur vajag kaut kādus nebūt structus, childrenus un sazin vēl ko…

[Ezeliitis]

@nevertell un @binary Kaut kā šādi to ir iespējams izdarīt? (Sākotnējā doma)

 

Kur x ir vecāki un i ir kā bērni un tad attiecīgi, kas uz ko attiecas. Ar šo ideju tālāk kaut kur iemaldījos un metu plinti krūmos. :/

Varbūt varat iemest ideju pseudo kodā?

Labots Novembris 16, 2016 - Ezeliitis

[Raimonds1]

google iedeva šo

https://www.hackerearth.com/practice/notes/trees/

Pats gan es tur pagaidām maz ko saprotu, bet tur ir tāds virsraksts

Tree to its Mirror Tree

The idea is to traverse the tree in postorder and after calling left and right subtree swap the pointers of the node.

Ja der, ieliec pilno kodu, ja vari - ar skaitļu ievadi.

[Eric]

Kāds tur koks!?

Katrai rindai txt failā samaini secību, pirmo elementu rindā atstājot tur kur tas ir..

[Ezeliitis]

@Eric Ko darīt, ja kokam var būt potenciāli simts rindiņas? Tad tas risinājums nebūs efektīvs.

[binary]

Ja mērķis ir nolasīt teksta failu, samainīt "elementu" secību un saglabāt jaunā failā, tad tas kā reiz ir efektīvākais risinājums, neatkarīgi no rindiņu skaita - kaut tur septiņi miljoni to rindiņu.

 

Ja mērķis ir:

1) izveidot koka struktūru

2) izskriet cauri koka struktūrai

3) samainīt vietām katra koka elementa bērnus

4) serializēt koka struktūru

... tad, protams, ar parastu teksta faila lasīšanu un modificēšanu būs par maz.

[Anonīms Alkoholiķis]

Mēķis ir zaļiem gurķiem iemācīt domāt. Savādāk kādam varētu gadīties piedzīvot analoģisku situāciju http://thedailywtf.com/articles/the-logic-barrier, noņempt nost krievu valodu..

 

Ja izmanto c++, varbūt uzreiz vieglak butu izmantot stl vai boost biblipteku, lai nodrosinatu sarakstu funkcionalitati un biezpiena radisanas funkcionalitati.

Labots Novembris 16, 2016 - Anonīms Alkoholiķis