[자료구조] Binary Tree

Linked representation을 통해 구현한 Tree

 

TreeNode 클래스.

Tree 클래스가 TreeNode 클래스의 private data 멤버를 접근해야하기 때문에 friend로 지정해준다.

template<class T> class Tree;
template<class T>
class TreeNode {
    friend class Tree<T>;
private:
    T data;
    TreeNode<T> *leftChild;
    TreeNode<T> *rightChild;
public:
    TreeNode(const T& e){
        data = e;
        leftChild = 0;
        rightChild = 0;
    }
};

 

Tree 클래스

LevelOrder() 함수, Inorder() 함수를 통해 level order, inorder traversal을 구현했다.

template<class T>
class Tree {
public:
    Tree(const T& e){
        root = new TreeNode<T>(e);
    }
    TreeNode<T>* AddNode(TreeNode<T> *x,bool isLeft, const T& e){
        if(x && isLeft) {
            x->leftChild = new TreeNode<T>(e);
            return x->leftChild;
        } else if(x && !isLeft) {
            x->rightChild = new TreeNode<T>(e);
            return x->rightChild;
        } else {
            return 0;
        }
    }
    void AddNode(TreeNode<T> *x,bool isLeft, TreeNode<T> *newNode){
        if(x && isLeft) {
            x->leftChild = newNode;
        } else if(x && !isLeft) {
            x->rightChild = newNode;
        }
    }
    vector<T> LevelOrder() {
        vector<T> v;
        queue<TreeNode<T>*> q;
        TreeNode<T> *currentNode = root;
        while(currentNode) {
            v.push_back(currentNode->data);
            if(currentNode->leftChild) q.push(currentNode->leftChild);
            if(currentNode->rightChild) q.push(currentNode->rightChild);
            if(q.empty()) return v;
            currentNode = q.front();
            q.pop();
        }
        return v;
    }
    void inorderTraverse(TreeNode<T>* self) {
        if(self==0) return;
        inorderTraverse(self->leftChild);
        v.push_back(self->data);
        inorderTraverse(self->rightChild);
    }
    vector<T> Inorder() {
        v.clear();
        inorderTraverse(root);
        return v;
    }
    
    TreeNode<T>* getRoot(){
        return root;
    }
private:
    TreeNode<T> *root;
    vector<T> v;
};

 

밑의 main 함수를 실행한 결과

int main(void) {
    Tree<string> tree("+");
    tree.AddNode(tree.getRoot(), false, "E");
    TreeNode<string> *x2 = new TreeNode<string>("*");
    TreeNode<string> *x4 = new TreeNode<string>("*");
    tree.AddNode(tree.getRoot(), true, x2);
    tree.AddNode(x2, true, x4);
    tree.AddNode(x2, false, "D");
    TreeNode<string> *x6 = new TreeNode<string>("/");
    tree.AddNode(x4, true, x6);
    tree.AddNode(x4, false, "C");
    tree.AddNode(x6, true, "A");
    tree.AddNode(x6, false, "B");
    
    vector<string> v = tree.LevelOrder();
    
    for(int i=0;i<v.size();i++)
        cout << v[i];
    cout << endl;
    
    vector<string> v2 = tree.Inorder();
    
    for(int i=0;i<v2.size();i++)
        cout << v2[i];
    
    cout << endl;
}