首页 > 代码库 > binary tree breadth first traversal in c++
binary tree breadth first traversal in c++
BFS is faster to find shortest path from root to leaf node of a tree. But the tradeoff is to use more memory.
the basic trategy is to maintain a list to hold nodes of each level.
1 void BFS(TreeNode<T>* node){ 2 if(node == NULL) // if node is NULL, return 3 return; 4 else{ 5 std::list<TreeNode<T>* > current; 6 current.push_back(node); 7 while( current.size != 0){ 8 std::list<TreeNode<T>* > next_level; 9 for(std::list<TreeNode<T>* >::iterator itr = current.beign();10 itr != current.end(); ++itr){11 if(node->left) next_level.push_back(node->left);12 if(node->right) next_level.push_back(node->right);13 }14 current = next_level;15 } 16 } 17 }
you could use iterator to traverse the current list to print out the values as well.
binary tree breadth first traversal in c++
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。