15. 이진트리 -b. 포인터로 구현한 이진트리

이진트리

  # 최소한의 기능만 가진 이진트리 (라지만 꼭 있어야 하는 기능들이 아직 없는듯한...)

  # 아무래도 미완성 느낌이 강하긴 하지만 추후에 내용을 추가하기로 결정.

  # 현재로서는 트리에 노드를 추가하려면 수작업으로 노드를 찾아가서 노드를 추가하는 식으로 작업하도록 되어있다.

  # 순회의 목적에 따라 함수포인터를 전달하도록 되어있기 때문에 이를 사용한 메인 함수도 함께 첨부했다.

  

  # 다음 포스트는 '스레이드 이진트리'와 '수식 트리'까지 다루고, 바로 '우선순위 큐와 힙', '그래프'로 넘어간 뒤,

  # 알고리즘 부분으로 넘어가서 탐색과 정렬에 관련된 자료구조를 다뤄야 할 듯 하다. 

C++로 구현한 포인터 기반 이진트리

  BinaryTree.h

#pragma once

template <typename T>
struct node
{
	T data;
	node* left;
	node* right;
};

//트리 관련 전역 함수
template <typename T>
void ChangeData(node<T>* node, T data)
{
	node->data = data;
}

template <typename T>
T& CheckData(node<T>* node)
{
	return node->data;
}

template <typename T>
node<T>* MakeNode(T data)
{
	node<T>* nn = new node<T>;
	nn->data = data;
	nn->left = nullptr;
	nn->right = nullptr;

	return nn;
}

//작업을 함수포인터로 전달받는 순회 함수
template <typename T>
void preorder(node<T>* node, void(*action)(T) )
{
	if (node != nullptr) {
		action(node->data);
		preorder(node->left, action);
		preorder(node->right, action);
	}
}


template <typename T>
void inorder(node<T>* node, void(*action)(T))
{
	if (node != nullptr) {
		inorder(node->left, action);
		action(node->data);
		inorder(node->left, action);
	}
}


template <typename T>
void postorder(node<T>* node, void(*action)(T))
{
	if (node != nullptr) {
		postorder(node->left, action);
		postorder(node->right, action);
		action(node->data);
	}
}


template <typename T>
class BinaryTree
{
	node<T>* rootNode;
	
private:
	

public:
	//노드 포인터를 리턴하는 함수
	node<T>* getRoot();
	node<T>* getRight(node<T>* node);
	node<T>* getLeft(node<T>* node);

	//src트리를 Dest노드의 자식으로 붙임
	bool  connectLeft(node<T>* DestNode, node<T>* SrcTree);
	bool  connectRight(node<T>* DestNode, node<T>* SrcTree);

public:
	BinaryTree(T data);
	virtual ~BinaryTree();
};

template <typename T>
BinaryTree<T>::BinaryTree(T data)
{
	rootNode = new node<T>;
	rootNode->data = data;
	rootNode->left = nullptr;
	rootNode->right = nullptr;
}


template <typename T>
node<T>* BinaryTree<T>::getRoot()
{
	return rootNode;
}

template <typename T>
node<T>* BinaryTree<T>::getLeft(node<T>* node)
{
	return node->left;
}

template <typename T>
node<T>* BinaryTree<T>::getRight(node<T>* node)
{
	return node->right;
}


template <typename T>
bool  BinaryTree<T>::connectLeft(node<T>* DestNode, node<T>* srcTree)
{
	if (DestNode->left == nullptr) {
		DestNode->left = srcTree;
		return true;
	}

	return false;
}

template <typename T>
bool  BinaryTree<T>::connectRight(node<T>* DestNode, node<T>* srcTree)
{
	if (DestNode->right == nullptr) {
		DestNode->right = srcTree;
		return true;
	}

	return false;
}


template <typename T>
BinaryTree<T>::~BinaryTree()
{

}

  main.cpp

#include "BinaryTree.h"
#include <iostream>

void print(int data) {
	std::cout << data << std::endl;
}

int main()
{
	BinaryTree<int> bt(0);
	std::cout << CheckData(bt.getRoot()) << std::endl;

	BinaryTree<int> bt2(1);

	bt2.connectLeft(bt2.getRoot(), MakeNode(2));
	std::cout << CheckData(bt2.getLeft(bt2.getRoot())) << std::endl;

	preorder(bt2.getRoot(), print);

}