c++initializer-listtree-traversal

Initialize a tree in inorder?


Im using initializer list and helper to create a tree in inorder. for example {1,2,3,4,5,6,7} if I print the tree in inorder traversal it will also give 1,2,3,4,5,6,7.

tree::tree(const initializer_list<int>& I) {
    const int* p1 = I.begin();
    root = nullptr;
    IL_helper(I, p1, root);
}

void tree::IL_helper(const initializer_list<int>& I, const int*& p1, node* & p2) {
    if (p1 == I.end()) {
        return;
    }
    
    p2 = new node(*p1);
    ++p1;
    
    IL_helper(I, p1, p2->Lchild);
    IL_helper(I, p1, p2->Rchild);
}

how to form a tree with inorder traversal with recursion. In my code, I realize it will only have Lchild. tree t{1,2,3,4,5,6,7} ; cout << t.inOrderT(t.root); output: 1,2,3,4,5,6,7


Solution

  • p2 = new node(*p1);

    overwrites the p2, but its type is just node*, so this assignment does not affect anything outside of the function. Just change the parameter to node* &p2.

    Also, I see a second problem - in your example is no bisection of the input list - so the nodes of the tree you will construct will always have just the Lchild set. Because in the recursive chain of IL_helper(I, p1, p2->Lchild); all of the list will be consumed, leaving nothing left for the Rchild call. It's technically not a bug if that's the intended behavior ( for example, the tree might be re-balanced afterwards ), but is it ?