Breadth-first Traversing?

I'm new to binary trees. How would I output the nodes in the trees by levels then from left to right?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
#include <cstdlib>
#include <deque>
#include <iostream>
using namespace std;

class Binary_Tree
{
private:
    struct tree_node
    {
        int data;
        tree_node* leftChild;
        tree_node* rightChild;
    };
    tree_node* root;
    
public:
    Binary_Tree()
    {
        root = NULL;
    }
    
    bool is_empty() const {return root == NULL; }
    void insert(int);
};

void Binary_Tree::insert(int a)
{
    tree_node* t = new tree_node;
    tree_node* parent;
    t->data = a;
    t->leftChild = NULL;
    t->rightChild = NULL;
    parent = NULL;
    
    if(is_empty()) root = t;
    else
    {
        tree_node* current;
        current = root;
        while(current)
        {
            parent = current;
            if(t->data > current->data)
            {
                current = current->rightChild;
            }else{
                current = current->leftChild;
            }
        }
        if(t->data < parent->data) 
        {
            parent->leftChild = t;
        }else{
            parent->rightChild = t;
        }
    }
}

void Breadth_First()
{
    
    
}

int main()
{
    Binary_Tree trees;
    int choice;
    int temp;
    deque<int> num(15);
    while(1)
    {
        cout << "1. insert" << endl;
        cout << "2. output" << endl;
        cout << "3. exit" << endl;
        cin >> choice;
        switch(choice)
        {
            case 1:
                for(int i=0; i<15;i++)
                {
                    cout << "Enter a number" << endl;
                    cin >> temp;
                    num.push_back(temp);
                    trees.insert(temp);
                }
                break;
            case 2:
                Breadth_First();
                break;
            case 3:
                return 0;
        }
    }
}
Last edited on
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
#include <queue>
#include <iostream>

class Binary_Tree
{
    private:
        struct node
        {
            int data;
            node* leftChild = nullptr ;
            node* rightChild = nullptr ;
        };

        node* root = nullptr ;

        static void recursive_delete( node* n )
        {
            if( n != nullptr )
            {
                recursive_delete( n->leftChild ) ;
                recursive_delete( n->rightChild ) ;
                delete(n) ;
            }
        }

        static void insert( node* tree, int value ) // invariant: pointer is not null
        {
            // get a reference to the appropriate child substree
            // note: a reference is required because it should be modified if it is null
            node*& where = value < tree->data ? tree->leftChild : tree->rightChild ;
            if( where == nullptr ) where = new node { value } ;
            else insert( where, value ) ;
        }

        static void push_children( std::queue< const node* >& q, const node* n )
        {
            // our breadth first is from left to right; so push the left child first
            if( n->leftChild ) q.push( n->leftChild ) ;
            if( n->rightChild ) q.push( n->rightChild ) ;
        }

        // non-copyable, non-moveable (move elided for brevity)
        Binary_Tree( const Binary_Tree& ) = delete ;
        void operator= ( const Binary_Tree& ) = delete ;

    public:

        Binary_Tree() = default ;
        ~Binary_Tree() { recursive_delete(root) ; }

        bool is_empty() const { return root == nullptr; }

        void insert( int value )
        {
            if( is_empty() ) root = new node { value } ;
            else insert( root, value ) ;
        }

        std::ostream& print_breadth_first( std::ostream& stm = std::cout ) const
        {
            if( is_empty() ) return stm ;

            // we need to print the items level by level, top to bottom
            // so use a queue to hold the items at the next lower level (they go to the back of the queue)
            // these would be printed only after we are done printing the current level
            std::queue< const node* > queue ;
            queue.push(root) ; // start with the root

            while( !queue.empty() ) // as long as there are no more items to be printed
            {
                stm << queue.front()->data << ' ' ; // print the item at the current level
                push_children( queue, queue.front() ) ; // hold the children for later processing
                queue.pop() ; // and remove the item that was printed
            }

            return stm << '\n' ;
        }
};

int main()
{
    Binary_Tree my_tree ;
    for( int value : { 12, 78, 23, 32, 44, 11, 92, 64, 81, 10, 19, 17 } )
    {
        my_tree.insert(value) ;
        my_tree.print_breadth_first() ;
    }
}

http://coliru.stacked-crooked.com/a/8a2ea1b7b9bf2e01
How would I change this so that it accepts user input instead of using numbers that are already input into the program?
1
2
3
4
5
for( int value : { 12, 78, 23, 32, 44, 11, 92, 64, 81, 10, 19, 17 } )
    {
        my_tree.insert(value) ;
        my_tree.print_breadth_first() ;
    }
Topic archived. No new replies allowed.