12347 - Binary Search Tree

All about problems in Volume 123. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Post Reply
sabrina07
New poster
Posts: 2
Joined: Sat Jul 05, 2014 2:42 pm

12347 - Binary Search Tree

Post by sabrina07 » Tue Jul 22, 2014 8:53 pm

I am getting wrong ans, please help me :( , here is my code

Code: Select all

#include <iostream>
#include <cctype>
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:
        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);
};

// 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);
        }
    }
}
//postorder
void Tree::postOrder(Node* n) {
    if ( n ) {
        postOrder(n->Left());
        postOrder(n->Right());
        cout << n->Key() << endl;
    }
}


// Test main program
int main() {
    Tree* tree = new Tree();
    int node_value;
    
    while (scanf("%d",&node_value)!=EOF) {
        
        tree->addNode(node_value);
        }
    
    
   
    tree->postOrder(tree->Root());
    cout << endl;
    
    return 0;
}

lighted
Guru
Posts: 585
Joined: Wed Jun 11, 2014 9:56 pm
Location: Kyrgyzstan, Bishkek

Re: 12347- Binary Search Tree

Post by lighted » Tue Jul 22, 2014 11:35 pm

Given the pre-order traversal of a binary search tree, you task is to find the post-order traversal of this tree
Given tree is pre-order traversal , so must build it as follows:

Pre-order traversal (Root-Left-Right)

1. First we visit root
2. Left subtree
3. Right subtree

Therefore first number is always root value. You must make it root.
After root value comes left subtree. How can we now the bounds of left and right subtree?
All numbers standing right from root value and that are less root value are left subtree. Make them left subtree for current root.
After left subtree comes right subtree until last number and all of them are greater than root value. Make them right subtree for current root.

You must build tree in order mentioned above.
I didn't build tree at all. I used only array of numbers.
I just traversed it in preorder traversal by recursive function and printed root value after traversing left and right subtree
(because in post-order traversal (Left –Right-Root) first visited left and right subtrees and then visited root)

Hope it is not confusing.
A person who sees the good in things has good thoughts. And he who has good thoughts receives pleasure from life... Bediuzzaman

Post Reply

Return to “Volume 123 (12300-12399)”