#include <iostream>
#include <list>
using namespace std;
typedef struct bin_tree_node
{
int v;
struct bin_tree_node *left;
struct bin_tree_node *right;
}BTNode;
BTNode *create_bin_tree_node(int v)
{
BTNode *p = new BTNode;
if(p != NULL){
p->v = v;
p->left = NULL;
p->right = NULL;
}
return p;
}
void create_balanced_bin_tree(BTNode **root, int arr[], int start, int end)
{
if(start <= end){
int mid = (start + end + 1) / 2;
*root = create_bin_tree_node(arr[mid]);
create_balanced_bin_tree(&((*root)->left), arr, start, mid - 1);
create_balanced_bin_tree(&((*root)->right), arr, mid + 1, end);
}
}
void print_bin_tree(BTNode *root)
{
if(root != NULL){
cout << " " << root->v;
print_bin_tree(root->left);
print_bin_tree(root->right);
cout << endl;
}
}
void print_d_level_node(BTNode *root)
{
list<BTNode *> l0, l1;
list<BTNode *>::iterator it;
int level = 0;
l0.push_back(root);
while(!l0.empty()){
cout << "level " << level++ << " -- ";
for(it = l0.begin(); it != l0.end(); ++it){
cout << (*it)->v << " ";
}
cout << endl;
for(it = l0.begin(); it != l0.end(); ++it){
if((*it)->left != NULL){
l1.push_back((*it)->left);
}
if((*it)->right != NULL){
l1.push_back((*it)->right);
}
}
if(l1.empty()){
break;
}
l0.clear();
l0.resize(l1.size()); // make sure enough space is reserved
copy(l1.begin(), l1.end(), l0.begin());
l1.clear();
}
}
int main(int argc, char* argv[])
{
int arr[30];
for(int i = 0; i < 30; i ++){
arr[i] = i;
}
BTNode *root = NULL;
create_balanced_bin_tree(&root, arr, 0, 29);
print_bin_tree(root);
print_d_level_node(root);
return 0;
}
Output
15 7 3 1 0
2
5 4
6
11 9 8
10
13 12
14
23 19 17 16
18
21 20
22
27 25 24
26
29 28
level 0 -- 15
level 1 -- 7 23
level 2 -- 3 11 19 27
level 3 -- 1 5 9 13 17 21 25 29
level 4 -- 0 2 4 6 8 10 12 14 16 18 20 22 24 26 28
Solution
Modify of the breath-first traversal of the tree
Problem
Given a binary search tree, design an algorithm which creates a linked list of all the nodes at each depth (i. e. , if you have a tree with depth D, you’ll have D linked lists).