C++ få fram sekvens för binärt sökträd

Permalänk
Medlem

C++ få fram sekvens för binärt sökträd

Hej,

Jag försöker skapa en funktion som skriver ut sekvensen för ett binärt sökträd:
in: 6
cout: 3 1 5 0 2 6
Likt sökträdet

3 1 5 0 2 4 6

Eller
in: 14
cout: 7 3 11 1 5 9 13 0 2 4 6 8 10 12 14
Likt sökträdet

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

Nuvarande implementation skriver ut: 7 3 11 1 9 5 13 0 8 4 12 2 10 6 14

#include <iostream> #include <string> #include <vector> #include <queue> using namespace std; int getMid(const int begin, const int end) { return (begin + end) / 2; } void getBinaryIndex(const int begin = 0, const int end = 14) { queue<int> que; int mid = getMid(begin, end); que.push(mid); int counter = 0; while (!que.empty()) { if (counter > end) return; int left = getMid(begin, que.front() - 1); int right = getMid(que.front() + 1, end); que.push(left); que.push(right); cout << que.front() << " "; que.pop(); counter++; } } int main() { getBinaryIndex(); getchar(); return 0; }

Funktionen behöver endast funka med end = n^2 - 2 för heltal n.

Permalänk
Medlem

@Sinery: Låter som att du vill göra en Breadth First Search (BFS). Har du sökt på det?

Visa signatur

:(){ :|:& };:

🏊🏻‍♂️   🚴🏻‍♂️   🏃🏻‍♂️   ☕

Permalänk
Medlem

deleted

Permalänk
Medlem

@Sinery: Nu förstår jag inte. Hur ser klassen/representationen av ditt binärträd ut?

Visa signatur

:(){ :|:& };:

🏊🏻‍♂️   🚴🏻‍♂️   🏃🏻‍♂️   ☕

Permalänk
Medlem
Skrivet av GLaDER:

@Sinery: Nu förstår jag inte. Hur ser klassen/representationen av ditt binärträd ut?

Borde inte posted den, jag ville endast visa att jag förtog logiken för BFS.

Jag har inget binärt träd, jag vill endast få en sekvens av ett sådant träd.
Tex om jag har en sorterad vektor med maxIndex 14 så kan jag behandla den som ett sorterat träd om jag har sekvensen

7 3 11 1 5 9 13 0 2 4 6 8 10 12 14 = 7 3 11 1 5 9 13 0 2 4 6 8 10 12 14

Permalänk
Medlem

@Sinery: Du kan t.ex. börja med att dela upp sekvensen i nivåer, första nivån kommer ju ha ett element och sen dubbleras antalet element för varje nivå. Så i ditt fall får du t.ex.:

{7} {3 11} {1 5 9 13} {0 2 4 6 8 10 12 14}

Sen får du bestämma hur många tecken varje löv ska ta upp, och raderna (om vi antar att varje rad är lika lång med whitespace inräknat) kommer då bli tecken per löv * antalet löv långa. Varje rad får sen lika många "fack" som antalet noder på raden, och det som återstår då är bara att att centrera noderna inom sina "fack" i strängarna. D.v.s.:

| 7 | | 3 | 11 | | 1 | 5 | 9 | 13 | | 0 | 2 | 4 | 6 | 8 | 10 | 12 | 14 |

Det går förstås inte att få det helt perfekt när noderna är olika stora.

Permalänk
Medlem
Skrivet av perost:

@Sinery: Du kan t.ex. börja med att dela upp sekvensen i nivåer, första nivån kommer ju ha ett element och sen dubbleras antalet element för varje nivå. Så i ditt fall får du t.ex.:

{7} {3 11} {1 5 9 13} {0 2 4 6 8 10 12 14}

Sen får du bestämma hur många tecken varje löv ska ta upp, och raderna (om vi antar att varje rad är lika lång med whitespace inräknat) kommer då bli tecken per löv * antalet löv långa. Varje rad får sen lika många "fack" som antalet noder på raden, och det som återstår då är bara att att centrera noderna inom sina "fack" i strängarna. D.v.s.:

| 7 | | 3 | 11 | | 1 | 5 | 9 | 13 | | 0 | 2 | 4 | 6 | 8 | 10 | 12 | 14 |

Det går förstås inte att få det helt perfekt när noderna är olika stora.

Problemet är fortfarande att få ut nivåerna från 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
Dvs jag måste välja 7, sedan 3 till väster och 11 till höger och så vidare i rätt ordning.

Permalänk
Medlem
Skrivet av Sinery:

Problemet är fortfarande att få ut nivåerna från 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
Dvs jag måste välja 7, sedan 3 till väster och 11 till höger och så vidare i rätt ordning.

Roten på trädet kommer vara elementet i mitten av sekvensen, och elementen på sidorna utgör noderna i vardera gren. Så {0 1 2 3 4 5 6}, {7}, {8 9 10 11 12 13 14}. Sen är det bara att göra samma sak rekursivt, d.v.s. {0 1 2 3 4 5 6} => {0 1 2}, {3}, {4, 5, 6}, o.s.v.

Permalänk

Ni måste verkligen förklara uppgifterna/frågorna ni ställer upp här på forumet tydligare, för det är väldigt svårt att förstå intentionen med dem. I detta fall exempelvis ser jag inte varför du inte bara skulle kunna lagra rotelementet som första element i exempelvis en std::vector och sedan lagras dem från vänster-till-höger. Dvs:

{5, 7, 6, ...} blir

5 / \ 7 6

Det är så enkelt, fast det låter konstigt om det är så man ska göra. Därför drar jag slutsatsen att beskrivningen av uppgiften är lite svagt förklarad.

Permalänk
Datavetare

Är målet att i princip ange höjden på ett fullständigt binärträd och sedan vill du ha en std::vector<int>?

Kanske finns något supersmart sätt, men behöver du inte hålla reda på gränserna för delträden när bredden-först travisering sker genom det "virtuella" trädet?

Något åt detta håll (annan språk om det skulle råka vara en skoluppgift, Go i detta fall)

package main import ( "flag" "fmt" ) type subtree struct { left uint right uint } func subtreeTop(st subtree) uint { return (st.left + st.right) / 2 } func fullTreeCreate(height uint) []uint { var q []subtree var tree []uint // Add top of tree node q = append(q, subtree{0, (1 << height) - 2}) // Breadth-first walk through the virtual tree for len(q) > 0 { // Pop subtree st := q[0] q = q[1:] // Calculate value of top element in subtree top := subtreeTop(st) tree = append(tree, top) // If not at leaf-node, push subtrees if st.left < st.right { q = append(q, subtree{st.left, top - 1}) q = append(q, subtree{top + 1, st.right}) } } return tree } func main() { var height = flag.Uint("height", 4, "Tree height, number of elements are ((1 << height) - 1)") flag.Parse() fmt.Println(fullTreeCreate(*height)) }

Exempelkörning

$ go run fulltree.go -height 3 [3 1 5 0 2 4 6] $ go run fulltree.go -height 4 [7 3 11 1 5 9 13 0 2 4 6 8 10 12 14]

Visa signatur

Care About Your Craft: Why spend your life developing software unless you care about doing it well? - The Pragmatic Programmer

Permalänk
Medlem
Skrivet av Ståupptuppen:

Ni måste verkligen förklara uppgifterna/frågorna ni ställer upp här på forumet tydligare, för det är väldigt svårt att förstå intentionen med dem. I detta fall exempelvis ser jag inte varför du inte bara skulle kunna lagra rotelementet som första element i exempelvis en std::vector och sedan lagras dem från vänster-till-höger. Dvs:

{5, 7, 6, ...} blir

5 / \ 7 6

Det är så enkelt, fast det låter konstigt om det är så man ska göra. Därför drar jag slutsatsen att beskrivningen av uppgiften är lite svagt förklarad.

Då är den inte lägre ett binärt sökträd.
Uppgiften är att omvandla en sorterad vector med (vector.size() == n^2 - 1) till en vector med uppsättningen för ett binärt sökträd.
Vilket är lätt och göra om man har den efterfrågande sekvensen.

Permalänk
Medlem
Skrivet av perost:

Roten på trädet kommer vara elementet i mitten av sekvensen, och elementen på sidorna utgör noderna i vardera gren. Så {0 1 2 3 4 5 6}, {7}, {8 9 10 11 12 13 14}. Sen är det bara att göra samma sak rekursivt, d.v.s. {0 1 2 3 4 5 6} => {0 1 2}, {3}, {4, 5, 6}, o.s.v.

Problemet är givetvis att få det till programkod.

Permalänk
Medlem
Skrivet av Yoshman:

Är målet att i princip ange höjden på ett fullständigt binärträd och sedan vill du ha en std::vector<int>?

Kanske finns något supersmart sätt, men behöver du inte hålla reda på gränserna för delträden när bredden-först travisering sker genom det "virtuella" trädet?

Något åt detta håll (annan språk om det skulle råka vara en skoluppgift, Go i detta fall)

package main import ( "flag" "fmt" ) type subtree struct { left uint right uint } func subtreeTop(st subtree) uint { return (st.left + st.right) / 2 } func fullTreeCreate(height uint) []uint { var q []subtree var tree []uint // Add top of tree node q = append(q, subtree{0, (1 << height) - 2}) // Breadth-first walk through the virtual tree for len(q) > 0 { // Pop subtree st := q[0] q = q[1:] // Calculate value of top element in subtree top := subtreeTop(st) tree = append(tree, top) // If not at leaf-node, push subtrees if st.left < st.right { q = append(q, subtree{st.left, top - 1}) q = append(q, subtree{top + 1, st.right}) } } return tree } func main() { var height = flag.Uint("height", 4, "Tree height, number of elements are ((1 << height) - 1)") flag.Parse() fmt.Println(fullTreeCreate(*height)) }

Exempelkörning

$ go run fulltree.go -height 3 [3 1 5 0 2 4 6] $ go run fulltree.go -height 4 [7 3 11 1 5 9 13 0 2 4 6 8 10 12 14]

Mer eller mindre, som sagt jag behöver sekvensen för att omvandla en sorterad vector till en vector som är ett binärt sökträd.
Jag får försöka att översätta din implementation till C++

Permalänk
Skrivet av Sinery:

Då är den inte lägre ett binärt sökträd.
Uppgiften är att omvandla en sorterad vector med (vector.size() == n^2 - 1) till en vector med uppsättningen för ett binärt sökträd.
Vilket är lätt och göra om man har den efterfrågande sekvensen.

Inte längre ett binärt sökträd? Datastrukturen och dess lagring är ju bara en abstraktion, du kan ju lagra det hur du vill. Därför påstår jag att uppgiften är otydlig.

Permalänk
Medlem
Skrivet av Ståupptuppen:

Inte längre ett binärt sökträd? Datastrukturen och dess lagring är ju bara en abstraktion, du kan ju lagra det hur du vill. Därför påstår jag att uppgiften är otydlig.

Nej, det är inte ett binärt sökträd om det ser ut på sättet du gör. Allt till vänster av en given nod skall vara mindre än den och allt till höger ska vara större. En rotnot med värdet 5 och vänster barn 7 och höger barn 6 bryter mot ett binärt sökträds invariant på alla sätt.

Permalänk
Skrivet av Snigeln Bert:

Nej, det är inte ett binärt sökträd om det ser ut på sättet du gör. Allt till vänster av en given nod skall vara mindre än den och allt till höger ska vara större. En rotnot med värdet 5 och vänster barn 7 och höger barn 6 bryter mot ett binärt sökträds invariant på alla sätt.

Jag tog bara några slumpade siffror för att visa ordningen i hur det representerades i exemplet jag gjorde. Varför blir jag fortsatt missförstådd över något jag förklarat?

V = {root, child1, child2, child11, child12, child21, child22, ...}

Du kan lagra den hur du vill, ingen tvingar en till något så länge man utgår från den premissen när man implementerar.

Permalänk
Moderator
Forumledare

*tråd rensad*

Har raderat ett litet sidospår som hade passat bättre i pm

Visa signatur

Forumets regler | Har du synpunkter på hur vi modererar? Kontakta SweClockers/moderatorerna

Jag stavar som en kratta

Gillar lök på discord

Permalänk
Medlem
Skrivet av Ståupptuppen:

Du kan lagra den hur du vill, ingen tvingar en till något så länge man utgår från den premissen när man implementerar.

Visst. Men det du visade i ditt exempel var INTE ett binärt sökträd. Finessen med ett binärt sökträd är att man kan använda det för att söka binärt. Det går inte med den typ av träd du visade. Ett binärt sökträd är en klassisk datastruktur som är mycket exakt definierad.

https://en.wikipedia.org/wiki/Binary_search_tree

Jag misstänker att det som avses inte bara är ett binärt sökträd utan ett *balanserat* sökträd. Om du inte vet vad ett binärt sökträd är så förstår jag varför du tyckte uppgiften var otydlig.

Jag tror att det enklaste (kanske enda?) sättet att få ut en korrekt lista för valfria heltal n är att skapa ett balanserat sökträd och sedan traversera det på lämpligt sätt.

Visa signatur

Linux och Android

Permalänk
Medlem
Skrivet av Sinery:

Funktionen behöver endast funka med end = n^2 - 2 för heltal n.

Fy på dig, nu blev jag tvungen att natthacka. Kul uppgift.

Yoshmans lösning är ju den vettiga, men om du kör fast på den varianten kan du testa att fylla arrayen baklänges. De matematiska sambanden är ju ganska uppenbara.

Skrivet av Sinery:

Uppgiften är att omvandla en sorterad vector med (vector.size() == n^2 - 1) till en vector med uppsättningen för ett binärt sökträd.

Låter ju i och för sig att uppgiften faktiskt kan vara att implementera trädet, skicka in värdena i vektorn ett och ett i trädet och sedan traversera genom trädet och få ut värdena. Ditt sätt lär ju i och för sig också funka.

Permalänk
Datavetare

Kom på ett annat sätt att se på detta problem som kan vara lättare att förstå.

Man kan väldigt effektivt se en array som en binary-heap. Går däremot inte att bara slänga in element i en ordning och köra std::make_heap() då det inte är en binary-heap som ska skapas utan ett fullständigt binärt träd.

Vad man däremot kan utnyttja från binary-heap är hur man enkelt och väldigt effektivt kan traversera det tänkta binärträdet när det lagras som man nästan alltid lagrar en binary-heap: som en array. Att gå upp/ned i ett sådant träd görs dubblering/halvering av indexvärdet i arrayen.

Exempel, kör C++ denna gång

#include <iostream> #include <string> #include <vector> unsigned leftChild(unsigned idx) { return 1 + (idx << 1); } unsigned rightChild(unsigned idx) { return 1 + leftChild(idx); } template<typename Func> void inOrderWalk(unsigned idx, unsigned numElem, Func &visitor) { if (idx < numElem) { inOrderWalk(leftChild(idx), numElem, visitor); visitor(idx); inOrderWalk(rightChild(idx), numElem, visitor); } } auto fullTreeMake(unsigned height) { unsigned numElem = (1 << height) - 1; std::vector<unsigned> tree(numElem); auto visitor = [&, cnt=0](unsigned idx) mutable { tree[idx] = cnt++; }; inOrderWalk(0, numElem, visitor); return tree; } int main(int argc, char *argv[]) { std::vector<std::string> args(argv + 1, argv + argc); unsigned height = 3; if (args.size() > 0) { height = std::stoi(args.front()); } auto tree = fullTreeMake(height); for (auto node: tree) { std::cout << node << ' '; } std::cout << '\n'; }

Exempelkörning

$ ./inorderwalk 4 7 3 11 1 5 9 13 0 2 4 6 8 10 12 14

Visa signatur

Care About Your Craft: Why spend your life developing software unless you care about doing it well? - The Pragmatic Programmer