/*
기존 이진트리에 살을 좀 붙여봤습니다.
*/
#include <iostream>
using namespace std;
class Tree;
class TreeNode
{
private:
TreeNode *leftChild;
int data;
TreeNode *rightChild;
public:
TreeNode():leftChild(NULL), data(0), rightChild(NULL)
{
}
TreeNode(int temp, TreeNode *left, TreeNode *right) :leftChild(left), data(temp), rightChild(right)
{
}
friend class Tree;
friend int Equal(TreeNode *tn1, TreeNode *tn2);
};
class Tree
{
private:
TreeNode *root;
public:
Tree() :root(NULL)
{
}
Tree(const Tree &t)
{
root = Copy(t.root);
}
void Initialize() //트리를 초기화
{
//Figure 5.11을 따라서 그렸습니다
root = new TreeNode(1, 0, 0);
root->leftChild = new TreeNode(2, 0, 0);
root->rightChild = new TreeNode(3, 0, 0);
root->leftChild->leftChild = new TreeNode(4, 0, 0);
root->leftChild->rightChild = new TreeNode(5, 0, 0);
root->rightChild->leftChild = new TreeNode(6, 0, 0);
root->rightChild->rightChild = new TreeNode(7, 0, 0);
root->leftChild->leftChild->leftChild = new TreeNode(8, 0, 0);
root->leftChild->leftChild->rightChild = new TreeNode(9, 0, 0);
root->leftChild->rightChild->leftChild = new TreeNode(10, 0, 0);
root->leftChild->rightChild->rightChild = new TreeNode(11, 0, 0);
root->rightChild->leftChild->leftChild = new TreeNode(12, 0, 0);
root->rightChild->leftChild->rightChild = new TreeNode(13, 0, 0);
root->rightChild->rightChild->leftChild = new TreeNode(14, 0, 0);
root->rightChild->rightChild->rightChild = new TreeNode(15, 0, 0);
}
TreeNode *Copy(TreeNode *origNode)
{
if (origNode)
{
TreeNode *temp = new TreeNode;
temp->data = origNode->data;
temp->leftChild = Copy(origNode->leftChild);
temp->rightChild = Copy(origNode->rightChild);
}
else
return 0;
}
void Preorder() //driver
{
Preorder(root);
}
void Preorder(TreeNode *currentNode) //workhorse
{
if (currentNode)
{
cout << currentNode->data << "->";
Preorder(currentNode->leftChild);
Preorder(currentNode->rightChild);
}
}
void Inorder()
{
Inorder(root);
}
void Inorder(TreeNode *currentNode)
{
if (currentNode)
{
Inorder(currentNode->leftChild);
cout << currentNode->data << "->";
Inorder(currentNode->rightChild);
}
}
void Postorder()
{
Postorder(root);
}
void Postorder(TreeNode *currentNode)
{
if (currentNode)
{
Postorder(currentNode->leftChild);
Postorder(currentNode->rightChild);
cout << currentNode->data << "->";
}
}
friend int operator==(const Tree &t1, const Tree &t2);
};
int operator==(const Tree &t1, const Tree &t2)
{
return Equal(t1.root, t2.root);
}
int Equal(TreeNode *tn1, TreeNode *tn2)
{
if ((!tn1) && (!tn2)) //둘다 NULL
return 1;
if (tn1 && tn2 && (tn1->data == tn2->data) && Equal(tn1->leftChild, tn2->leftChild) && Equal(tn1->rightChild, tn2->rightChild))
//둘 다 존재하고 데이터가 같고, 왼쪽 자식 오른쪽 자식이 같다
return 1;
return 0;
}
int main(void)
{
Tree t1, t2;
t1.Initialize();
t2 = t1;
cout << "5.3 Exercises 2 정답을 확인할 수 있습니다" << endl;
cout << endl;
cout << "전위순회: ";
t1.Preorder();
cout << endl;
cout << "중위순회: ";
t2.Inorder();
cout << endl;
cout << "후위순회: ";
t1.Postorder();
cout << endl << endl;
if (t1 == t2)
cout << "두 트리는 동일합니다" << endl;
else
cout << "두 트리는 동일하지 않습니다" << endl;
return 0;
}
[참고] Fundamentals of Data Structures in C++(Horowitz, Sahni, Mehta) 원서
*영어로 적혀있는 문제를 제가 의역한 것이기 때문에 오역이 있을 수 있습니다. 양해 부탁드립니다.