For this program, create ordered binary trees in C++ from this input: ABCDEFGHIJ

Question

For this program, create ordered binary trees in C++ from this input: ABCDEFGHIJKLMNOPQRSTU VWXYZ 9876543210 MFCJABDEHGIKLTPNORSQWUVYXZ SPHINCTERSAYSWHAT 524137968 MATLSO FTERFO EYBLEIF LYBWIOL SYGTHO FPNOEDESO LLTDREOI

Each line contains the input for a single tree. The input for a tree is read from left-to-right and is inserted into the tree one character at a time. After you have created the tree for an input, print out its preorde, inorder, postorder, and reverse inorder traversals. A reverse inorder traversal is simply going to the right, visiting the node and then going to the left (i.e., RVL). Make sure to read the input from stdin so that I can execute your program as follows: ./treefun < input


For this program, create ordered binary trees in C++ from this input: ABCDEFGHIJKLMNOPQRSTU VWXYZ 9876543210 MFCJABDEHGIKLTPNORSQWUVYXZ SPHINCTERSAYSWHAT 524137968 MATLSO FTERFO EYBLEIF LYBWIOL SYGTHO FPNOEDESO LLTDREOI

Each line contains the input for a single tree. The input for a tree is read from left-to-right and is inserted into the tree one character at a time. After you have created the tree for an input, print out its preorde, inorder, postorder, and reverse inorder traversals. A reverse inorder traversal is simply going to the right, visiting the node and then going to the left (i.e., RVL). Make sure to read the input from stdin so that I can execute your program as follows: ./treefun < input


ABCDEFGHIJKLMNOPQRSTU VWXYZ 9876543210 MFCJABDEHGIKLTPNORSQWUVYXZ SPHINCTERSAYSWHAT 524137968 MATLSO FTERFO EYBLEIF LYBWIOL SYGTHO FPNOEDESO LLTDREOI

Each line contains the input for a single tree. The input for a tree is read from left-to-right and is inserted into the tree one character at a time. After you have created the tree for an input, print out its preorde, inorder, postorder, and reverse inorder traversals. A reverse inorder traversal is simply going to the right, visiting the node and then going to the left (i.e., RVL). Make sure to read the input from stdin so that I can execute your program as follows: ./treefun < input

Explanation / Answer

#include <iostream>

using namespace std;

// Node class

class Node {

int key;

Node* left;

Node* right;

public:

Node() { key=-1; left=NULL; right=NULL; };

void setKey(int aKey) { key = aKey; };

void setLeft(Node* aLeft) { left = aLeft; };

void setRight(Node* aRight) { right = aRight; };

int Key() { return key; };

Node* Left() { return left; };

Node* Right() { return right; };

};

// Tree class

class Tree {

Node* root;

public:

Tree();

~Tree();

Node* Root() { return root; };

void addNode(int key);

void inOrder(Node* n);

void preOrder(Node* n);

void postOrder(Node* n);

private:

void addNode(int key, Node* leaf);

void freeNode(Node* leaf);

};

// Constructor

Tree::Tree() {

root = NULL;

}

// Destructor

Tree::~Tree() {

freeNode(root);

}

// Add a node

void Tree::addNode(int key) {

// No elements. Add the root

if ( root == NULL ) {

cout << "add root node ... " << key << endl;

Node* n = new Node();

n->setKey(key);

root = n;

}

else {

cout << "add other node ... " << key << endl;

addNode(key, root);

}

}

// Add a node (private)

void Tree::addNode(int key, Node* leaf) {

if ( key <= leaf->Key() ) {

if ( leaf->Left() != NULL )

addNode(key, leaf->Left());

else {

Node* n = new Node();

n->setKey(key);

leaf->setLeft(n);

}

}

else {

if ( leaf->Right() != NULL )

addNode(key, leaf->Right());

else {

Node* n = new Node();

n->setKey(key);

leaf->setRight(n);

}

}

}

// Print the tree in-order

// Traverse the left sub-tree, root, right sub-tree

void Tree::inOrder(Node* n) {

if ( n ) {

inOrder(n->Left());

cout << n->Key() << " ";

inOrder(n->Right());

}

}

//Print reverse inored

// Traverse the right sub-tree, root, left sub-tree

void Tree::reverseInOrder(Node* n) {

if ( n ) {

inOrder(n->Right());

cout << n->Key() << " ";

inOrder(n->Left());

}

}

// Print the tree pre-order

// Traverse the root, left sub-tree, right sub-tree

void Tree::preOrder(Node* n) {

if ( n ) {

cout << n->Key() << " ";

preOrder(n->Left());

preOrder(n->Right());

}

}

// Print the tree post-order

// Traverse left sub-tree, right sub-tree, root

void Tree::postOrder(Node* n) {

if ( n ) {

postOrder(n->Left());

postOrder(n->Right());

cout << n->Key() << " ";

}

}

// Test main program

int main() {

char[] arr=new char[100];

char choice;

Tree* tree = new Tree();

do

{

cout<<"Enter the values:";

cin>>arr;

int size=strlen(arr);

for(int i=0;i<size;i++)

tree->addNode(arr[i]);

cout << "In order traversal" << endl;

tree->inOrder(tree->Root());

cout << endl;

cout << "Pre order traversal" << endl;

tree->preOrder(tree->Root());

cout << endl;

cout << "Post order traversal" << endl;

tree->postOrder(tree->Root());

cout << endl;

cout << "Reversse Inorder traversal" << endl;

tree->reverseInOrder(tree->Root());

cout << endl;

cout<<"Do you want to continue?(Y/N)";

cin>>choice;

}while(choice=='Y');

delete tree;

return 0;

}

Related Questions

Navigate

• Browse (All)
• Browse F
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.