[Exercises 1]
/*
Write out the inorder, preorder, postorder, and level-order traversals for the binary trees of Figure 5.10
5.10의 이진트리를 중위, 전위, 후위, 그리고 레벨-표기법으로 작성해본다
*/
inorder(중위): H->D->I->B->E->A->F->C->G
preorder(전위): A->B->D->H->I->E->C->F->G
postorder(후위): H->I->D->E->B->F->G->C->A
level: A->B->C->D->E->F->G->H->I
[Exercises 2]
/*
Do Exercise 1 for the binary tree of Figure 5.11
5.11의 이진트리에 대해서도 전 문제와 똑같이 풀어본다
*/
inorder(중위) : 8->4->9->2->10->5->11->1->12->6->13->3->14->7->15
preorder(전위) : 1->2->4->8->9->5->10->11->3->6->12->13->7->14->15
postorder(후위) : 8->9->4->10->11->5->2->12->13->6->14->15->7->3->1
level : 1->2->3->4->5->6->7->8->9->10->11->12->13->14->15
[Exercises 3]
/*
Do Exercise 1 for the binary tree of Figure 5.15
5.15의 이진트리에 대해서도 전 문제와 똑같이 풀어본다
*/
inorder(중위) : E->C->B->D->A
preorder(전위) : A->B->C->E->D
postorder(후위) : E->C->D->B->A
level : A->B->C->D->E
[Exercises 4]
/*
Implement a forward iterator for Tree.
Tree 클래스에 대한 전방 반복자를 구현한다.
Your iterator should traverse the tree in inorder.
반복자는 중위 순회를 해야한다
*/
template <typename T>
class inorderIterator
{
private:
stack<TreeNode<T>*> s;
TreeNode<T> *currentNode;
public:
inorderIterator(Tree<T> tree)
{
currentNode = root;
}
T *Next()
{
while (currentNode)
{
s.push(currentNode);
currentNode = currentNode->leftChild;
}
if (s.IsEmpty())
return 0;
currentNode = s.Top();
s.Pop();
T &temp = currentNode->data;
currentNode = currentNode->rightChild;
return &temp;
}
};
[Exercises 5]
/*
Implement a forward iterator for Tree.
Tree 클래스에 대한 전방 반복자를 구현한다.
Your iterator should traverse the tree in level.
반복자는 레벨 순회를 해야한다
*/
template <class T>
class levelIterator
{
private:
queue<TreeNode<T>*> q;
TreeNode<T> *currentNode;
public:
levelIterator()
{
currentNode = root;
}
T *Next()
{
TreeNode<T> *temp;
if (currentNode)
{
temp = currentNode;
if (currentNode->leftChild)
q.Enqueue(currentNode->leftChild);
if (currentNode->rightChild)
q.Enqueue(currentNode->rightChild);
if (q.IsEmpty())
return 0;
currentNode = q.front;
q.Dequeue();
return &temp->data;
}
}
};
[Exercises 6]
/*
Write a nonrecursive version of function Preoder
전위 순회 함수를 구현하되 비재귀 함수로 구현한다
*/
void Tree<T>::nonrecPreorder()
{
Stack<TreeNode<T>*> s;
TreeNode *currentNode = root;
while (1)
{
while (currentNode)
{
Visit(currentNode); //전위 순회이므로 먼저 노드를 방문
s.Push(currentNode);
currentNode = currentNode->leftChild;
}
if (s.IsEmpty())
return;
currentNode = s.Top();
s.Pop();
currentNode = currentNode->rightChild;
}
}
[Exercises 7]
/*
Use the results of the previous exercise to implement a forward iterator, PreorderIterator, that traverse the tree in preorder
앞서 구현한 전방 반복자를 이용하여 전위 순회를 하는 반복자를 구현한다
*/
template <typename T>
class preorderIterator
{
private:
stack<TreeNode<T>*> s;
TreeNode<T> *currentNode;
public:
preorderIterator()
{
currentNode = root;
}
T *Next()
{
TreeNode<T> *temp;
while (currentNode)
{
s.Push(currentNode);
temp = currentNode;
currentNode = currentNode->leftChild;
return &temp->data;
}
if (s.IsEmpty())
return 0;
currentNode = s.Top();
s.Pop();
currentNode = currentNode->rightChild;
}
};
[Exercises 8]
/*
Write a nonrecursive version of function Postoder
후위 순회 함수를 구현하되 비재귀 함수로 구현한다
*/
void Tree<T>::nonrecPostorder()
{
Stack<TreeNode<T>*> s;
TreeNode *currentNode = root;
while (1)
{
while (currentNode)
{
s.Push(currentNode)
currentNode = currentNode->leftChild;
}
if (s.IsEmpty())
return;
currentNode = s.Top();
s.Pop();
currentNode = currentNode->rightChild;
Visit(currentNode); //후위 순회이므로 마지막으로 노드를 방문
}
}
[Exercises 9]
/*
Use the results of the previous exercise to implement a forward iterator, PostorderIterator, that traverse the tree in preorder
앞서 구현한 전방 반복자를 이용하여 후위 순회를 하는 반복자를 구현한다
*/
template <typename T>
class stackItem
{
public:
bool visit; //방문했는가
TreeNode<T> *t; //노드
};
template <typename T>
class postorderIterator
{
private:
TreeNode<T> *currentNode;
stack<stackItem<T>*> s;
public:
postorderIterator()
{
currentNode = root;
}
T *Next()
{
stackItem<T> *item;
while (1)
{
while (currentNode)
{
item->t = currentNode;
item->visit = 0;
s.Push(item);
currentNode = currentNode->leftChild; //왼쪽 끝까지 간다
}
if (!s.IsEmpty())
{
item = s.Top();
s.Pop();
currentNode = item->t;
if (item->visit == 0) //방문한적 없다면
{
item->visit = 1;
s.Push(item);
currentNode = currentNode->rightChild;
}
else //이미 방문한적이 있다면
{
currentNode = 0;
return &(item->t->data);
}
}
}
}
};
[참고] Fundamentals of Data Structures in C++(Horowitz, Sahni, Mehta) 원서, http://m.blog.csdn.net/ysfseu/article/details/7080872
*영어로 적혀있는 문제를 제가 의역한 것이기 때문에 오역이 있을 수 있습니다. 양해 부탁드립니다.
*9번 후위순회반복자는 링크를 참고했습니다!