CODEWITHSUNDEEP
c++binary-tree
Filimoni Naisua
Filimoni Naisua

Reputation: 41

Rotate Binary Tree

I am trying to print a non static binary tree. It does print but it rotates towards the left. I cant find a way to correct this and make it rotate upright. 5 is the root node. Code:

template <class dataType>
void displaybinarytree(BinaryTree <dataType> * p, int indent)
{
if(p != NULL) {
    if(p->right()) {
        displaybinarytree(p->right(), indent+4);
    }

    if (indent) {
        cout << setw(indent) << ' ';
    }

    if (p->right()){
        cout<<" /\n" << setw(indent) << ' ';
    }

    cout<< p->getData() << "\n ";

    if(p->left()) {
        cout << setw(indent) << ' ' <<" \\\n";
        displaybinarytree(p->left(), indent+4);
    }
  }
}

Output:

Expected output:

Upvotes: 1

Views: 1281

Answers (2)

grek40
grek40

Reputation: 13438

A recursive approach doesn't play nice with a line-based output, where a line consists of items from multiple sub-trees.

You should switch to a breadth-first-traversal, where you create a working set per tree level. You may need to pre-compute the space requirements of lower tree levels in order to output the desired alignments in higher levels.

A little starting code that doesn't really display the tree as a tree, but at least displays each node in the correct line.

void displaybinarytree(BinaryTree <int> * p, int indent)
{
    deque<BinaryTree<int>*> current;
    deque<BinaryTree<int>*> next;
    next.push_back(p);

    while (!next.empty())
    {
        current.swap(next);
        while  (!current.empty())
        {
            BinaryTree<int>* node = current.front();
            current.pop_front();
            if (node->left)
            {
                next.push_back(node->left);
            }
            if (node->right)
            {
                next.push_back(node->right);
            }
            // instead of a single space, appropriate spacing is needed
            cout << " " << node->data;
        }
        // instead of a single newline, appropriate spacing and connector characters / \ are needed
        cout << endl;
    }
}

See the in-code-comments for things that are missing from this code. I replaced your dataType by int and used primitive fields instead of getter functions, since it doesn't really matter to the concept.

Upvotes: 2

davmac
davmac

Reputation: 20631

If you want the top of the tree to appear at the top of the output, you must output it first - before its branches.

Your code outputs the right branch first, and it therefore appears at the top of the output:

// Outputs right branch:
if(p->right()) {
    displaybinarytree(p->right(), indent+4);
}

if (indent) {
    cout << setw(indent) << ' ';
}

if (p->right()){
    cout<<" /\n" << setw(indent) << ' ';
}

// Outputs "current" node:
cout<< p->getData() << "\n ";

You need to switch the order: output the current node, then the branches.

Also, the slashes are in the wrong direction, and the indent changes need to be corrected. The left branch should be indented less rather than more.

Making just these changes at least gets the tree printed "top down". You will still find the branches are not printed next to each other - that requires a significantly more complex solution.

Upvotes: -1

Related Questions