이진트리 표기식 구현하기

#include <iostream>
#include "tree0.h"
using namespace std;
int main() {
    Tree<double> tree;
    double dval;
 
    cout << "Enter values:\n";
    while(cin>>dval)
        tree.Insert(dval);
 
    cout << endl << "Preorder traversal:        "; tree.Preorder();
    cout << endl << "Inorder traversal: ";         tree.Inorder();
    cout << endl << "Postorder traversal:       "; tree.Postorder();
    cout << endl << "Levelorder traversal:      "; tree.Levelorder();
    cout << endl;
}
 
 

#ifndef TREE0_H
#define TREE0_H
#include<iostream>
#include<queue>
using namespace std;
 
template<class T>
struct Node {
    Node(T d, Node<T> *left = 0, Node<T> *right = 0)
        :data(d), leftChild(left), rightChild(right) {}
 
    Node<T> *leftChild;
    T data;
    Node<T> *rightChild;
};
template<class T>
class Tree {
public:
    Tree() { root = 0; }
    void Insert(T &value) { Insert(root, value); }
    void Preorder() { Preorder(root); }
    void Inorder() { Inorder(root); }
    void Postorder() { Postorder(root); }
    void Levelorder();
private:
    void Visit(Node<T> *);
    void Insert(Node<T>* &, T &);
    void Preorder(Node<T> *);
    void Inorder(Node<T> *);
    void Postorder(Node<T> *);
    Node<T> *root;
};
template<class T>
void Tree<T>::Visit(Node<T> *ptr) { cout << ptr->data << " "; }
 
template<class T>
void Tree<T>::Insert(Node<T>* &ptr, T &value) {
    if (ptr == 0) ptr = new Node<T>(value);
    else if (value < ptr->data) Insert(ptr->leftChild, value);
    else if (value > ptr->data) Insert(ptr->rightChild, value);
    else cout << "\nDuplicate value" << value << " ignored\n";
}
template<class T>
void Tree<T>::Preorder(Node<T> *currentNode) {
    if (currentNode) {
        Visit(currentNode);
        Preorder(currentNode->leftChild);
        Preorder(currentNode->rightChild);
    }
}
template<class T>
void Tree<T>::Inorder(Node<T> *currentNode) {
    if (currentNode) {
        Inorder(currentNode->leftChild);
        Visit(currentNode);
        Inorder(currentNode->rightChild);
    }
}
template<class T>
void Tree<T>::Postorder(Node<T> *currentNode) {
    if (currentNode) {
        Postorder(currentNode->leftChild);
        Postorder(currentNode->rightChild);
        Visit(currentNode);
    }
}
template<class T>
void Tree<T>::Levelorder() {
    queue< Node<T>* > q;
    Node<T> *currentNode = root;
    while (currentNode) {
        Visit(currentNode);
        if (currentNode->leftChild) q.push(currentNode->leftChild);
        if (currentNode->rightChild) q.push(currentNode->rightChild);
        if (q.empty()) return;
        currentNode = q.front();
        q.pop();
    }
}
#endif

입력:

Enter values:

35 15.7 81.5 4 66 91 2 5 88 94

ctl-d 

출력:

Preorder traversal:     35 15.7 4 2 5 81.5 66 91 88 94

Inorder traversal:      2 4 5 15.7 35 66 81.5 88 91 94

Postorder traversal:    2 5 4 15.7 66 88 94 91 81.5 35

Levelorder traversal:   35 15.7 81.5 4 66 91 2 5 88 94

환경:linux