구현 - 이진 트리

이진트리의 노드는 똑같이 이진트리라는 점을 이용해서 노드가 곧 트리인 클래스를 만들어보았다.

좌, 우 삽입

전위, 중위, 후위, 레벨 순회, 

원소개수, 높이, 터미널 개수를 구하는 연산을 작성했다.
 

class BSubTree

{

string _key{};

int _value{};

BSubTree* _left{};

BSubTree* _right{};

public:

BSubTree() {};

BSubTree(string key, int data) : _key(key), _value(data) {};

const string& key() { return _key; }

void print()

{

cout << _value << " " << _key << endl;

}

void push_left(BSubTree* node)

{

_left = node;

}

void push_right(BSubTree* node)

{

_right = node;

}

void print_preorder() //VLR

{

print();

if (_left) _left->print_preorder();

if (_right) _right->print_preorder();

}

void print_inorder() //LVR

{

if (_left) _left->print_inorder();

print();

if (_right) _right->print_inorder();

}

void print_postorder() //LRV

{

if (_left) _left->print_postorder();

if (_right) _right->print_postorder();

print();

}

void print_levelorder()

{

queue<BSubTree*> que;

que.push(this);

while (!que.empty())

{

BSubTree* front = que.front();

front->print();

if (front->_left) que.push(front->_left);

if (front->_right) que.push(front->_right);

que.pop();

}

}

size_t number_of_elem()

{

return number_of_elem(this);

}

size_t get_height()

{

return get_height(this);

}

size_t number_of_leaf()

{

return number_of_leaf(this);

}

private:

size_t number_of_elem(BSubTree* curr)

{

if (!curr) return 0;

return 1 + number_of_elem(curr->_left) + number_of_elem(curr->_right);

}

size_t get_height(BSubTree* curr)

{

if (!curr) return 0;

size_t leftH = get_height(curr->_left);

size_t rightH = get_height(curr->_right);

size_t currH = leftH < rightH ? rightH + 1 : leftH + 1;

return currH;

}

size_t number_of_leaf(BSubTree* curr)

{

if (!curr) return 0;

if (!curr->_left && !curr->_right)

{

cout << curr->_key << ", ";

return 1;

}

return number_of_leaf(curr->_left) + number_of_leaf(curr->_right);

}

};

테스트 코드:

void main()

{

BSubTree grandfa("할아버지", 1);

BSubTree uncle("큰 아버지", 2);

BSubTree father("아버지", 3);

BSubTree bigbro("친척 형", 4);

BSubTree brother("형", 5);

BSubTree me("나", 6);

grandfa.push_left(&uncle);

grandfa.push_right(&father);

uncle.push_left(&bigbro);

father.push_left(&brother);

father.push_right(&me);

cout << "전위 순회 : \n";

grandfa.print_preorder();

cout << endl;

cout << "중위 순회 : \n"; 

grandfa.print_inorder();

cout << endl;

cout << "후위 순회 : \n";

grandfa.print_postorder();

cout << endl;

cout << "레벨 순회 : \n";

grandfa.print_levelorder();

cout << endl;

cout << "구성원 수: " << grandfa.number_of_elem() << endl;

cout << "세대 수 " << grandfa.get_height() << endl;

cout << "자식이 없는 구성원 수 : ";

cout << "(" << grandfa.number_of_leaf() << ")" << endl;

cout << endl;

}