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

Trädvy Permalänk
Medlem
Registrerad
Okt 2016

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.

Stax 353xbk | Stax L300Le + L700 Arc + Custom Pads
SMSL AD18 | Kef Q300

Trädvy Permalänk
Medlem
Plats
Göteborg
Registrerad
Nov 2011

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

GNU/Linux

Blog
YouTube

Trädvy Permalänk
Medlem
Registrerad
Okt 2016

deleted

Stax 353xbk | Stax L300Le + L700 Arc + Custom Pads
SMSL AD18 | Kef Q300

Trädvy Permalänk
Medlem
Plats
Göteborg
Registrerad
Nov 2011

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

GNU/Linux

Blog
YouTube

Trädvy Permalänk
Medlem
Registrerad
Okt 2016
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

Stax 353xbk | Stax L300Le + L700 Arc + Custom Pads
SMSL AD18 | Kef Q300

Trädvy Permalänk
Medlem
Plats
Linköping
Registrerad
Jun 2007

@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.

Trädvy Permalänk
Medlem
Registrerad
Okt 2016
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.

Stax 353xbk | Stax L300Le + L700 Arc + Custom Pads
SMSL AD18 | Kef Q300

Trädvy Permalänk
Medlem
Plats
Linköping
Registrerad
Jun 2007
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.

Trädvy Permalänk
Medlem
Registrerad
Nov 2018

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.

Trädvy Permalänk
Datavetare
Plats
Stockholm
Registrerad
Jun 2011

Ä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]

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

Trädvy Permalänk
Medlem
Registrerad
Okt 2016
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.

Stax 353xbk | Stax L300Le + L700 Arc + Custom Pads
SMSL AD18 | Kef Q300

Trädvy Permalänk
Medlem
Registrerad
Okt 2016
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.

Stax 353xbk | Stax L300Le + L700 Arc + Custom Pads
SMSL AD18 | Kef Q300

Trädvy Permalänk
Medlem
Registrerad
Okt 2016
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++

Stax 353xbk | Stax L300Le + L700 Arc + Custom Pads
SMSL AD18 | Kef Q300

Trädvy Permalänk
Medlem
Registrerad
Nov 2018
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.

Trädvy Permalänk
Medlem
Plats
Uppsala
Registrerad
Mar 2012
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.

Trädvy Permalänk
Medlem
Registrerad
Nov 2018
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.

Trädvy Permalänk
Forumledare
Plats
Här
Registrerad
Jul 2009

*tråd rensad*

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

Trädvy Permalänk
Medlem
Plats
Småland, långt ute i mörka skogen.
Registrerad
Maj 2018
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.

Linux och Android

Trädvy Permalänk
Medlem
Registrerad
Dec 2015
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.

Trädvy Permalänk
Datavetare
Plats
Stockholm
Registrerad
Jun 2011

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

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