So I have figured out everything with this program, except one thing which is escaping me. I have created a General Tree(or sometimes called left most tree) where the node points to its left most child, and the child points to its right sibling and also its leftmost child.

Creating the tree, displaying the tree was fine.

Now I need to create the mirror image of the tree, where the first node becomes the last node, last node becomes the first node, and i cant seem to get it. Any help?

Here is what I have so far:

void mirror(){

			mirror(this->root);
		}

		void mirror(TreeNode* node){

			for(TreeNode* kid = node->leftChild; kid != NULL; kid = kid->rightSibling){
			
				TreeNode* next = kid->rightSibling;
				kid->rightSibling = kid->leftChild;
				kid->leftChild = next;
			}
		}

just for reference, here is the rest of my code:

#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#include <string>

using namespace std;

class Tree{

	private:

		//inner node class
		class TreeNode{

		public:

			//name of node
			char name;
			//number of children
			int children;
			//left most child
			TreeNode *leftChild;
			//right sibling
			TreeNode *rightSibling;
			//treenode constructor
			TreeNode(char nodeName, int numChildren){

				this->name = nodeName;
				this->children = numChildren;
				this->leftChild = NULL;
				this->rightSibling = NULL;
			}
		};

		//root of tree
		TreeNode *root;

	public:

		void mirror(){

			mirror(this->root);
		}

		void mirror(TreeNode* node){

			for(TreeNode* kid = node->leftChild; kid != NULL; kid = kid->rightSibling){
			
				TreeNode* next = kid->rightSibling;
				kid->rightSibling = kid->leftChild;
				kid->leftChild = next;
			}
		}

		//counts the number of nodes with only one child
		void oneChild(){

			int count = 0;
			oneChild(this->root, count);
			cout << count;
		}

		//overloaded count of nodes with one chils
		void oneChild(TreeNode* node, int &count){

			if(node){

				if(node->leftChild && node->leftChild->rightSibling == NULL)
					count++;
				oneChild(node->leftChild, count);
				oneChild(node->rightSibling, count);
			}
		}

		//smallest node function
		void smallestNode(){

			char smallest = this->root->name;
			smallestNode(this->root, smallest);
			cout << smallest;
		}

		//overloaded smallest node function
		void smallestNode(TreeNode *node, char &smallest){

			if(node){

				if(node->name < smallest)
					smallest = node->name;

				smallestNode(node->leftChild, smallest);
				smallestNode(node->rightSibling, smallest);
			}
		}

		//print tree function
		void printTree(){

			int count = 0;

			printTree(this->root,"");
		}

		//overloaded print tree function
		void printTree(TreeNode *node, string indent){

			if(node == NULL)
				return;

			cout << indent << node->name << endl;
			indent.append(" ");
			for(TreeNode* temp = node->leftChild; temp != NULL; temp = temp->rightSibling)
				printTree(temp,indent);

		}

		//stack of TreeNode*'s
		std::stack< TreeNode*, std::vector< TreeNode*>> myStack;

			//tree creation
			TreeNode* makeTree(){

				//input file stream
				ifstream fin;
				//opens the file
				fin.open("prog1.txt");
				// Verifies file is opened correctly
				if(!fin){
					cout << "OOPS" << endl;
					exit(1);
				}

				char name;
				int count;

				do{

					fin >> name >> count;

					TreeNode *newNode = new TreeNode(name, count);

					for(int kid = 0; kid < count; kid++){

						TreeNode *child = myStack.top();
						myStack.pop();
						child->rightSibling = newNode->leftChild;
						newNode->leftChild = child;
					}

					myStack.push(newNode);

					TreeNode *myNode = myStack.top();

				}while(!fin.eof());

			this->root = myStack.top();

			return myStack.top();

		fin.close();
	}

};

I'm not sure I understand what you are trying to do in your code (it is mixing siblings and children, which would be some kind of inversion...)

But if what you are trying to do is convert this:

+---+
    | 0 |--X
    +---+
      |
      V
    +---+   +---+   +---+
    | 1 |-->| 2 |-->| 3 |--X
    +---+   +---+   +---+
      |       |       |
      X       V       |
            +---+     |
            | 4 |--X  |
            +---+     |
              |       |
              X       V
                    +---+   +---+
                    | 5 |-->| 6 |--X
                    +---+   +---+
                      |       |
                      X       X

into this:

+---+
    | 0 |--X
    +---+
      |
      V
    +---+   +---+   +---+
    | 3 |-->| 2 |-->| 1 |--X
    +---+   +---+   +---+
      |       |       |
      |       V       V
      |     +---+
      |     | 4 |-X
      |     +---+
      |       |
      |       X
      V
    +---+   +---+
    | 6 |-->| 5 |--X
    +---+   +---+
      |       |
      X       X

Then consider how the general tree is organized. Each set of children is a singly-linked list. So all you have to do is iterate (or recurse) down through each child node and reverse the linked list of siblings.

It will help if you try to do it on paper. If you still get stuck there is a C code snippet for reversing a singly linked list where I responded with an iterative algorithm to do it (the original snippet is flawed).

Hope this helps.

Sorry I was not very clear, I actually did not understand the question fully myself.

Basically, the children of a node just become reversed:

so if node t has a kid named a and e, and a's right sibling is e, t would point to e and then a would be e's right sibling, and so on and so forth.

I have used your idea about reversing the list and still doesn't seem quite right, can you show me what I am doing wrong?

//creates the mirror image of the tree
		void mirror(){

			mirror(this->root);
		}

		//overloaded mirror image function.
		//TreeNode *node is a TreeNode node which is passed in to work with
		void mirror(TreeNode *node){

			node->leftChild = reverseList(node->leftChild);
			for(TreeNode *kid = node->leftChild; kid != NULL; kid = kid->rightSibling)
			
				mirror(kid);
		}

		//reverse list
		TreeNode* reverseList(TreeNode *node){
		
			TreeNode *temp1 = node;
			TreeNode *temp2 = NULL;
			TreeNode *temp3 = NULL;

			while (temp1){

				node = temp1; //set the head to last node		
				temp2= temp1->leftChild; // save the next ptr in temp2
				temp1->leftChild = temp3; // change next to privous
				temp3 = temp1;
				temp1 = temp2;
			}

			return node;
		}

Sorry I was not very clear, I actually did not understand the question fully myself.

Basically, the children of a node just become reversed:

so if node t has a kid named a and e, and a's right sibling is e, t would point to e and then a would be e's right sibling, and so on and so forth.

I have used your idea about reversing the list and still doesn't seem quite right, can you show me what I am doing wrong?

//creates the mirror image of the tree
		void mirror(){

			mirror(this->root);
		}

		//overloaded mirror image function.
		//TreeNode *node is a TreeNode node which is passed in to work with
		void mirror(TreeNode *node){

			node->leftChild = reverseList(node->leftChild);
			for(TreeNode *kid = node->leftChild; kid != NULL; kid = kid->rightSibling)
			
				mirror(kid);
		}

		//reverse list
		TreeNode* reverseList(TreeNode *node){
		
			TreeNode *temp1 = node;
			TreeNode *temp2 = NULL;
			TreeNode *temp3 = NULL;

			while (temp1){

				node = temp1; //set the head to last node		
				temp2= temp1->leftChild; // save the next ptr in temp2
				temp1->leftChild = temp3; // change next to privous
				temp3 = temp1;
				temp1 = temp2;
			}

			return node;
		}

Why not "swap" the addresses that t is pointing to?

#include <algorithm>

swap(a, e); //?

@Aggie
Your mirror() function is right-on.

However, in reverseList() you are still mixing siblings and children. The 'next' node is the sibling, not the child.

It took me a minute to figure it out because you used a whole bunch of nonsense variable names. I've been doing this for over twenty years. If it was hard for me to read then you don't stand a chance. Please use meaningful variable names.

@Alex
Swap is not useful here. Reversing a singly-linked list requires chaining along three pointers, not two.

Hope this helps.

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.