[Exercises 1]
/*
Write a C++ function to count the leaf nodes in a binary tree.
이진트리에서 단말노드를 세는 함수를 작성한다
*/
#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 << "->";
}
}
int LeafCount()
{
return LeafCount(root);
}
int LeafCount(TreeNode *currentNode)
{
if (!currentNode)
return 0;
if (!(currentNode->leftChild) && !(currentNode->rightChild))
return 1;
return (LeafCount(currentNode->leftChild) + LeafCount(currentNode->rightChild));
}
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;
cout << "단말노드: " << t1.LeafCount() << endl;
if (t1 == t2)
cout << "두 트리는 동일합니다" << endl;
else
cout << "두 트리는 동일하지 않습니다" << endl;
return 0;
}
[Exercises 2]
/*
Write a C++ function, SwapTree(), that swaps the left and right children of every node of a binary tree
이진트리에서 모든 노드의 오른쪽 자식과 왼쪽 자식을 뒤바꾸는 SwapTree() 함수를 작성한다.
*/
#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 << "->";
}
}
int LeafCount()
{
return LeafCount(root);
}
int LeafCount(TreeNode *currentNode)
{
if (!currentNode)
return 0;
if (!(currentNode->leftChild) && !(currentNode->rightChild))
return 1;
return (LeafCount(currentNode->leftChild) + LeafCount(currentNode->rightChild));
}
void SwapTree()
{
SwapTree(root);
}
void SwapTree(TreeNode *currentNode)
{
TreeNode *temp;
if (currentNode->leftChild == NULL && currentNode->rightChild == NULL) //자식들이 둘다 없을 경우
return;
if (currentNode->leftChild == NULL && currentNode->rightChild) //오른쪽 자식만 있는 경우
{
currentNode->leftChild = currentNode->rightChild;
currentNode->rightChild = NULL;
}
else if (currentNode->leftChild && currentNode->rightChild == NULL) //왼쪽 자식만 있는 경우
{
currentNode->rightChild = currentNode->leftChild;
currentNode->leftChild = NULL;
}
else //둘다 있는 경우
{
temp = currentNode->leftChild;
currentNode->leftChild = currentNode->rightChild;
currentNode->rightChild = temp;
}
if (currentNode->leftChild)
SwapTree(currentNode->leftChild);
if (currentNode->rightChild)
SwapTree(currentNode->rightChild);
}
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;
t1.Initialize();
t1.SwapTree();
cout << "기존 트리에서 왼쪽자식과 오른쪽 자식을 뒤바꾼다" << endl;
cout << endl;
cout << "전위순회: ";
t1.Preorder();
cout << endl;
cout << "중위순회: ";
t1.Inorder();
cout << endl;
cout << "후위순회: ";
t1.Postorder();
cout << endl << endl;
return 0;
}
[Swap된 Figure 5.11]
[Exercises 4]
/*
Write a recursive function to delete all nodes in a binary tree
이진트리 내에 있는 노드를 모드 지우는 재귀함수를 작성한다
*/
#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 << "->";
}
}
int LeafCount()
{
return LeafCount(root);
}
int LeafCount(TreeNode *currentNode)
{
if (!currentNode)
return 0;
if (!(currentNode->leftChild) && !(currentNode->rightChild))
return 1;
return (LeafCount(currentNode->leftChild) + LeafCount(currentNode->rightChild));
}
void SwapTree()
{
SwapTree(root);
}
void SwapTree(TreeNode *currentNode)
{
TreeNode *temp;
if (currentNode->leftChild == NULL && currentNode->rightChild == NULL) //자식들이 둘다 없을 경우
return;
if (currentNode->leftChild == NULL && currentNode->rightChild) //오른쪽 자식만 있는 경우
{
currentNode->leftChild = currentNode->rightChild;
currentNode->rightChild = NULL;
}
else if (currentNode->leftChild && currentNode->rightChild == NULL) //왼쪽 자식만 있는 경우
{
currentNode->rightChild = currentNode->leftChild;
currentNode->leftChild = NULL;
}
else //둘다 있는 경우
{
temp = currentNode->leftChild;
currentNode->leftChild = currentNode->rightChild;
currentNode->rightChild = temp;
}
if (currentNode->leftChild)
SwapTree(currentNode->leftChild);
if (currentNode->rightChild)
SwapTree(currentNode->rightChild);
}
void deleteTree()
{
deleteTree(root);
}
void deleteTree(TreeNode *currentNode)
{
if (currentNode == NULL)
return;
deleteTree(currentNode->leftChild);
deleteTree(currentNode->rightChild);
cout << currentNode->data << " 삭제 " << endl;
delete(currentNode);
return;
}
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;
t1.Initialize();
t1.SwapTree();
cout << "기존 트리에서 왼쪽자식과 오른쪽 자식을 뒤바꾼다" << endl;
cout << endl;
cout << "전위순회: ";
t1.Preorder();
cout << endl;
cout << "중위순회: ";
t1.Inorder();
cout << endl;
cout << "후위순회: ";
t1.Postorder();
cout << endl << endl;
cout << "이진트리 삭제" << endl;
t1.deleteTree();
return 0;
}
[참고] Fundamentals of Data Structures in C++(Horowitz, Sahni, Mehta) 원서
*영어로 적혀있는 문제를 제가 의역한 것이기 때문에 오역이 있을 수 있습니다. 양해 부탁드립니다.
*Exercises 3번 문제는 명제계산을 트리로 변환하는 문제였습니다. 나중에 풀 기회가 되면 코드를 올리겠습니다
*Exercises 5번 문제는 Copy 함수와 동일한 기능을 하는 함수이기 때문에 생략했습니다