c++로 작성한 트리 순회

자료구조 프로그래밍 과목을 배우면서 c++로 작성한 트리 순회입니다.(2가지 버전)

bt.h

#ifndef TREE_H

#define TREE_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

{

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;

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

};

 

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 << endl << "Duplicate 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

hw8.cpp

#include "bt.h"

 

int main(void)

{

        Tree<double> tree;

        double dval;

 

        cout << "Enter doubles:\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;

        return 0;

}

bt+.h

#ifndef BST_H

#define BST_H

#include <iostream>

#include <queue>

using namespace std;

 

template <class K, class E>

struct Node

{

        Node(K ky, E el, Node<K, E> *left = 0, Node<K, E> *right = 0) :key(ky), element(el), leftChild(left), rightChild(right)

        {

        }

        Node<K, E> *leftChild;

        K key;

        E element;

        Node<K, E> *rightChild;

};

 

template <class K, class E>

class BST

{

private:

        void Visit(Node<K, E> *);

        void Insert(Node<K, E>*&, K &, E &);

        void Preorder(Node<K, E> *);

        void Inorder(Node<K, E> *);

        void Postorder(Node<K, E> *);

        Node<K, E> *root;

public:

        BST()

        {

               root = 0;

        }

        void Insert(K &newkey, E &el)

        {

               Insert(root, newkey, el);

        }

        void Preorder()

        {

               Preorder(root);

        }

        void Inorder()

        {

               Inorder(root);

        }

        void Postorder()

        {

               Postorder(root);

        }

        void Levelorder();

};

 

template <class K, class E>

void BST<K, E>::Visit(Node<K, E> *ptr)

{

        cout << ptr->key << ":" << ptr->element << " ";

}

 

template <class K, class E>

void BST<K, E>::Insert(Node<K, E> *&ptr, K &newkey, E &el)

{

        if (ptr == 0)

               ptr = new Node<K, E>(newkey, el);

        else if (newkey < ptr->key)

               Insert(ptr->leftChild, newkey, el);

        else if (newkey>ptr->key)

               Insert(ptr->rightChild, newkey, el);

        else

               ptr->element = el;

}

 

template <class K, class E>

void BST<K, E>::Preorder(Node<K, E> *currentNode)

{

        if (currentNode)

        {

               Visit(currentNode);

               Preorder(currentNode->leftChild);

               Preorder(currentNode->rightChild);

        }

}

 

template <class K, class E>

void BST<K, E>::Inorder(Node<K, E> *currentNode)

{

        if (currentNode)

        {

               Inorder(currentNode->leftChild);

               Visit(currentNode);

               Inorder(currentNode->rightChild);

        }

}

 

template <class K, class E>

void BST<K, E>::Postorder(Node<K, E> *currentNode)

{

        if (currentNode)

        {

               Postorder(currentNode->leftChild);

               Postorder(currentNode->rightChild);

               Visit(currentNode);

        }

}

 

template <class K, class E>

void BST<K, E>::Levelorder()

{

        queue<Node<K, E>*> q;

        Node<K, E> *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

hw8+.cpp

#include "bt+.h"

#include <string>

 

int main(void)

{

        BST<string, double> bst;

        string str;

        double dval;

 

        cout << "Enter string & double pairs:\n";

 

        while (cin >> str >> dval)

               bst.Insert(str, dval);

        cout << endl << "Preorder traversal: ";

        bst.Preorder();

        cout << endl << "Inorder traversal: ";

        bst.Inorder();

        cout << endl << "Postorder traversal: ";

        bst.Postorder();

        cout << endl << "Levelorder traversal: ";

        bst.Levelorder();

        cout << endl;

        return 0;

}

 

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~