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();
}
};
