I'm in the middle of writing a C++ program which will eventually sort data, using a tree. I would like to swap a child with its parent if the child's value (could be anything, using a template) is less than the parent's. however, I have become stuck when trying to swap the two. I would like to swap all of the private variables except for 'tree *parent', as that must remain at the same node when everything else changes.
My class is as follows:

template <class data_t> class tree {
    data_t val;
    tree *lchild, *rchild; //point to children
    tree *right, *left; //point to nodes in the same row, right/left
    tree *parent; //points to parent
    int iam; //defines state (LCHILD (0), RCHILD (1) or ROOT (2)
    tree(data_t v) { val=v; lchild=rchild=left=right=0; iam=ROOT; parent=this;}
    void add(tree *node);
    tree *getnextl() { return lchild; }
    tree *getnextr() { return rchild; }
    tree *getnextn() { tree *t_parent=parent;
                       if(!t_parent->rchild) return t_parent;
                       else if(t_parent->right) return t_parent->right;
                       else {
                             return t_parent->lchild;}}
    tree *getleft() { return left; }
    tree *getright() { return right; }
    data_t getval() { return val; }
    data_t readtop();           
    void move_up();

And the start of the desired move_up() function:

template <class data_t> void tree<data_t>::move_up()
    if(parent->getval()>val) {

The move_up() function is be called at the end of the new tree function, which is called to create each node.

I'd be very grateful for any advice.

9 Years
Discussion Span
Last Post by fatnickc

Sorry for the double post, but the edit button is no longer available, and I have just noticed that my explanation wasn't perfectly clear (as well as seeing a good few mistakes grammatically...). The 'new tree' function I referred to is called add() in the code, and is used to assign a pointed-to node to be a child of a previous one, and to update the required 'right's and 'left's etc. It does not create the new node itself, as this is done in main.
The move_up() function is intended only to move the recently added node up, and put the parent it replaces each time below it. The function is called again on the repositioned node, and this continues until the parent's value is less than the value of the node in question.

The part I am facing trouble with is doing the actual swap, as 'parent' is only a pointer to the node's parent.


So...basically you're writing a heap, right?

>The part I am facing trouble with is doing the actual swap, as 'parent' is only a pointer to the node's parent.
Are you swapping data or doing a physical swap? If you're swapping data, I don't see what the problem is. If you're doing a physical swap, you should be using rotations.


Yes, it is a heap. The problem I was facing was thinking through how to swap the system of pointers. However, having left it for a few hours it does seem a lot simpler than I remember!
I'll have a go at it in a minute, when I'm on the right computer.


Indeed, it was much simpler than I was imagining. Thanks for the helpful push!

This question has already been answered. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.