#define cinGetValue(value,status) \
{ \
string inputLine; /* raw user input text*/ \
istringstream convert; /* string converstion variable.*/ \
\
getline(cin,inputLine); /* get a string of data from user input (could be empty) */ \
convert.str(inputLine); /* load 'convert' with user input */ \
convert >> value; /* load 'convert' with user input */ \
status = inputLine.empty(); /* boolean indicator of empty or !empty */ \
}
// homemade pause
// --------------
#define pause(message) {char x[10];cout<<endl<<message;gets_s(x,10);}
// node definition
// ---------------
typedef struct _node
{
int payload; //value of node
struct _node *left ; //nodes < value (at start of program)
struct _node *right ; //nodes > value (at start of program)
} node;
// branch direction
// ----------------
typedef enum _dirBranch {ROOT,LEFT,RIGHT} dirBranch;
// default dataset
// ---------------
//int nodeData[] = {10,8,15,6,9,13,19,4,12,14,18,20,2,5,11,1,3};
int nodeData[] = {10, //root
1, 2, 3, 4, 5, 6, 7, 8, 9, //sorted left branch
15,13,19,12,13,18,20,11 }; //AVT ordered
#define nodeDataCount sizeof(nodeData)/sizeof(int)
// forward declarations
// --------------------
node *treeAdd (node *root,int payload);
void treeDisplay (node *root,int depth ,dirBranch dir);
void swapSubtrees(node *root);
// This main program provides a user interface to manipulate a
// binary tree implemented as a linked list.
// ===========================================================
int main()
{
int idx; //index for data load from array
// empty binary tree
// -----------------
node *root = NULL;
// load binary tree from initial data
// ----------------------------------
root = treeAdd(root,nodeData[0]); //first call sets root
for (idx=1;idx<nodeDataCount;idx++)
treeAdd(root,nodeData[idx]);
// display binary tree
// -------------------
cout << "Original Binary Tree" <<endl;
cout << "--------------------" <<endl;
treeDisplay(root,0,ROOT);
pause("<Enter to swapSubtrees>");
cout << endl;
// swap the subtrees & display
// ---------------------------
cout << "Binary Tree with Swapped Subtrees" << endl;
cout << "---------------------------------" << endl;
swapSubtrees(root);
treeDisplay(root,0,ROOT);
// pause
// -----
pause("<Enter to Terminate>");
}
// Add a new value to the binary tree
// ==================================
node *treeAdd(node *root , //current root (maybe NULL)
int payload) //payload to be stored in tree
{
// create & load a new node
// ------------------------
node *newNode = new node;
newNode->payload = payload;
newNode->left = NULL;
newNode->right = NULL;
// link it into the binary tree
// ----------------------------
if (root != NULL)
{
node *tempNode = root; //used for tree traversal
while (1)
{
if (tempNode->payload > payload)
{
// try left branch
// ---------------
if (tempNode->left == NULL)
{
// there is no left branch: insert node
// ------------------------------------
tempNode->left = newNode;
break;
}
else
{
// follow left branch
// ------------------
tempNode = tempNode->left;
}
}
else
{
// try right branch
// ----------------
if (tempNode->right == NULL)
{
// there is no right branch: insert node
// ------------------------------------
tempNode->right = newNode;
break;
}
else
{
// follow right branch
// -------------------
tempNode = tempNode->right;
}
}
}
}
// always return the node we just added
// ------------------------------------
return newNode;
}
// Display the entire tree: sideways
// ---------------------------------
void treeDisplay(node *currNode, //current node to display
int depth , //number of spaces to indent (/3)
dirBranch dir ) //type of prefix '/' or '\' to output
{
int spaces; //number of spaces to indent
// take care of all the right branches
// -----------------------------------
if (currNode->right != NULL)
treeDisplay(currNode->right,depth+1,RIGHT);
// display this node
// -----------------
if (dir != ROOT)
{
for (spaces=depth;spaces>0;spaces--) cout << " ";
cout << ((dir==RIGHT) ? '/' : '\\'); //right/left indicator
}
cout << setw(2) << currNode->payload << endl;
// take care of all the left branches
// ----------------------------------
if (currNode->left != NULL)
treeDisplay(currNode->left,depth+1,LEFT);
}
// Swap all the right/left subtrees
// --------------------------------
void swapSubtrees(node *currNode)
{
node *tempNode; //for swapping
// swap left & right at this node
tempNode = currNode->left;
currNode->left = currNode->right;
currNode->right == tempNode;
// Check that link isn't NULL
// and Recurse down each side.
}
I can only seem to get 1 of the trees to show up the swap and it's still not swapped properly.