c++ - Print out all words in a Trie implemented with a map -


i have trienode class defined follows:

class trienode { public:     map<char, trienode*> children;     bool isleaf = false; // if node represents end of word     int wordcount = 0; // how many times word appears     trienode(); };

i'm trying print out of words in trie (preferably in alphabetical order, although i'd settle @ point). i've been trying implement recursive solution, haven't been able make decent start.

edit: should mention other questions i've looked @ how print words in trie store children array, rather map.

here's depth-first recursive traversal. best not use raw pointers, did here because asked , you. did not delete child nodes allocated addtrie, because wanted demonstrate traversal, rather write entire implementation. so, need add code delete these if use this.

#include <iostream> #include <map> #include <string>  class trienode { public:     std::map<char, trienode*> children;     bool isleaf = false; // if node represents end of word     int wordcount = 0; // how many times word appears     trienode() {} };  void addtrie(trienode& trie, const char* word) {     auto c = *(word++);     auto next = trie.children[c];     if(!next) { trie.children[c] = next = new trienode; }     if(*word) { addtrie(*next, word); }     else      { next->isleaf = true; } }  void dumptrie(const trienode& trie, std::string word={}) {     for(const auto& child : trie.children) {         const auto next_word = word + child.first;         if(child.second->isleaf) { std::cout << next_word << '\n'; }         dumptrie(*child.second, next_word); }   }  int main() {     trienode trie;     addtrie(trie, "goodbye");     addtrie(trie, "hello");     addtrie(trie, "good");     addtrie(trie, "goodyear");     dumptrie(trie); }

output

good goodbye goodyear hello

Comments

Post a Comment

Popular posts from this blog

c# - Update a combobox from a presenter (MVP) -

i using mvp in project, new in mvp. have 2 comboboxes. when select option in combobox, combobox should filled new data. this action in presenter. view 'view1' in presenter, , introduced combobox1 , combobox2 properties in 'view1', because need 'datasource', 'displaymember', 'valuemember' , 'refresh()' in method below. but, when using pattern, enough send property like public string combobox2 { { return combobox1.selectedvalue.tosstring(); } } into presenter not whole combobox. how can solve problem? public void onselectedindexchangedcombobox1() { if (view1.combobox1.selectedindex == -1) { return; } datatable dt = tools.getdatatable("a path"); var query = (from o in dt.asenumerable() o.field<string>("afield") == farmerview.combobox1.selectedvalue.tostring() orderby o.field<string>("anotherfield") select...
Read more

How to understand 2 main() functions after using uftrace to profile the C++ program? -

i trying uftrace profile following simple c++ program: #include <iostream> class { public: a() {std::cout << "a created" << std::endl;} ~a() {std::cout << "a destroyed" << std::endl;} }; int main() { a; return 0; } the profile result this: # uftrace a.out created destroyed # duration tid function 2.026 [ 4828] | __cxa_atexit(); [ 4828] | main() { [ 4828] | __static_initialization_and_destruction_0() { 89.397 [ 4828] | std::ios_base::init::init(); 0.768 [ 4828] | __cxa_atexit(); 93.029 [ 4828] | } /* __static_initialization_and_destruction_0 */ 94.425 [ 4828] | } /* main */ [ 4828] | main() { [ 4828] | a::a() { 11.104 [ 4828] | std::operator <<(); 10.825 [ 4828] | std::basic_ostream::operator <<(); 24.514 [ 4828] | } /* a::a */ [ 4828] | a::~a() { 0.978 [ 4828] | ...
Read more

How to put a lock and transaction on table using spring 4 or above using jdbcTemplate and annotations like @Transactional? -

i trying put lock on table while writing on table , if happened in between roll-back . trying convert below code lock table test_g1 read; lock table test_g write; -- begin; start transaction; insert test_g1 values(143); insert test_g values(145); select * test_g1; select * test_g; rollback; select * test_g; unlock tables; how convert above code @transactional spring jdbctemplate code? @transactional(rollbackfor={dataaccessexception.class}) public void test(){ jdbctemplate.execute("insert test1 (id, nam) values (4, 'a')"); throw new dataaccessexception("error") { }; } here trying throw error, insert statement should rollback it's not happening . thanks edit-1 attaching code , doing in jdbcdaoimpl.java , mentioned problem comment above test() . app.java package com.cgiri.javabrains.spring4; import org.springframework.beans.factory.annotation.autowired; import org.springframework.context.applic...
Read more