17장 연계된 자료 구조(3)

17.3 반복자

반복자(iterator)는

데이터 구조에 저장된 데이터 항목을 순환시켜

데이터 구조의 각 데이터 항목에 대해 원하는 작업을 수행할 수 있도록 하는 구성

(일반적으로 일부 반복기 클래스의 개체)이다.

반복자로서의 포인터

반복자에 대한 기본적인 아이디어, 그리고 사실상 원형 모델은 연결된 목록의 맥락에서 쉽게 볼 수 있다.

연결 리스트는 원형 데이터 구조의 하나이고, 포인터는 반복자의 원형 예시이다.

연결 리스트을 한 번에 한 노드씩 이동하여 목록의 모든 노드를 순환하면 포인터를 반복자로 사용할 수 있다.

전체적인 개요는 다음과 같다:
Node_Type *iterator;
for (iterator = Head; iterator != NULL;
    iterator = iterator-> Link)
반복자가 가리키는 노드로 원하는 것을 수행한다;
Head - 연결 리스트의 헤드 노드를 가리키는 포인터

Link -리스트의 다음 노드를 가리키는 노드의 멤버 변수 이름
예시)

섹션 17.1에서 설명한 종류의 연결 리스트에 있는 모든 노드의 데이터를 출력하려면 다음을 사용할 수 있다:
IntNode *iterator;
for(iterator = head; iterator != NULL; iterator = iterator->getLink( ))
    cout << (iterator->getData( ));
IntNode의 정의는 디스플레이 17.4에 나와 있다.
두 개의 포인터가 같은 연산자 ==와 비교하여 같은 노드를 가리키는지 검사한다.

포인터는 메모리 주소이다.

만약 두 개의 포인터 변수가 같은 메모리 주소를 포함하고 있다면,

그것들은 같은 것으로 비교하여 같은 노드를 가리키게 된다.

마찬가지로 !=를 사용하여 두 개의 포인터가 같은 노드를 가리키지 않는지 비교할 수 있다.

 

반복자 클래스

반복자 클래스(iterator class)는 포인터보다 더 다재다능하고 일반적인 개념이다.

다음 프로그래밍 예제처럼

포인터 멤버 변수를 데이터의 핵심으로 사용하는 경우가 매우 많지만 그것이 필요한 것은 아니다.

예를 들어 반복자의 핵심은 배열 인덱스일 수 있다.

반복자 클래스에는 함수와 오버로딩 연산자가 있으므로

기본 데이터 구조, 노드 유형 또는 기본 위치 마커(포인터 또는 배열 인덱스 등)에 무엇을 사용하든

반복자 클래스의 객체와 포인터 구문을 사용할 수 있다.

또한 광범위한 데이터 구조에서 사용할 수 있는 일반적인 프레임워크를 제공한다.

 

반복자 클래스에는 일반적으로 다음과 같은 오버로딩 연산자가 있다:
++: 오버로딩된 증가 연산자로, 반복자를 다음 항목으로 발전시킨다.
-- :반복자를 이전 항목으로 이동하는 오버로딩된 감소 연산자이다.
==: 두 반복자를 비교하고 둘 다 동일한 항목을 가리킬 경우 true를 반환하는 오버로딩된 균등 연산자이다.
!=: 동일하지 않은 연산자를 오버로드하여 두 반복자를 비교하고 동일한 항목을 가리키지 않으면 true로 반환한다.
*: 한 항목에 대한 접근 권한을 부여하는 오버로딩된 역참조 연산자이다.

(흔히 읽기와 쓰기 접근을 모두 허용하는 참조를 반환한다.)

이 연산자의 목록들을 생각할 때 구체적인 예로 연결 리스트를 사용할 수 있다.

그럴 경우 리스트의 항목은 리스트의 데이터이지 노드 전체의 포인터 멤버가 아님을 기억하자.

데이터 항목을 제외한 모든 것은 반복자 및 데이터 구조 클래스를 사용하는 프로그래머에게 숨겨야 할 구현 세부 사항이다.

반복자는 일부 유형의 데이터 항목을 저장하는 일부 특정 구조 클래스와 함께 사용된다.

데이터 구조 클래스는 일반적으로 해당 클래스의 개체에 대한 반복자를 제공하는 다음과 같은 멤버 함수를 갖는다:
begin( ) : 인수를 사용하지 않고 데이터 구조의 첫 번째 항목("point to")에 있는 반복기를 반환하는 멤버 함수이다.
end( ) : 인수를 사용하지 않고 데이터 구조의 모든 항목을 순환시켰는지 테스트하는 데 사용할 수 있는 반복기를 반환하는 멤버 함수이다.

만약 i가 반복기이고 데이터 구조의 마지막 항목을 초과하여 진행되었다면 end( )와 같아야 한다.

 

반복기를 사용하여 데이터 구조의 항목을 다음과 같이 순환할 수 있다:
for (i = ds.begin( ); i != ds.end( ); i++)
    process *i //*i is the current data item .

여기서 i는 반복자이다. 

 

19장에서는 이들보다 몇 가지 항목과 개선 사항을 더 포함하여 반복자에 대해 논의하지만, 

이것들은 소개를 위해 충분하다.
이 추상적인 논의는 우리가 예를 들기 전까지는 살아나지 않을 것이다.

자, 그럼 하나를 통해 살펴보자.

예: 반복자 클래스

디스플레이 17.31에는

연결 리스트를 기반으로 하는 자료 구조(예: 스택 또는 큐)에 사용할 수 있는

반복자 클래스의 정의가 포함되어 있다. 

노드 클래스와 반복자 클래스를 자신의 네임스페이스에 배치했다. 

반복기는 노드 클래스와 밀접하게 관련되어 있고 

이 노드 클래스를 사용하는 모든 클래스도 반복자 클래스를 사용할 수 있으므로 이는 의미가 있다. 

감소 연산자의 정의는 연결 리스트의 세부 정보에 따라 다르며 

Node 유형에만 의존하지 않으므로 이 반복자 클래스에는 감소 연산자가 없다. 

(반복자의 정의가 기본 연결 리스트에 의존하는 것은 문제가 없다.

방금 이 문제를 피하기로 결정했다.)

 

보다시피 템플릿 클래스 ListIterator는 기본적으로 필요한 멤버 연산자를 가질 수 있도록 클래스로 둘러싸인 포인터이다. 

오버로딩 연산자의 정의는 간단하고 실제로 너무 짧아서 우리는 그들을 모두 인라인 함수로 정의했다. 

역참조 연산자 *는 가리키는 노드의 데이터 멤버 변수를 생성한다. 

오직 데이터 멤버 변수만이 데이터이다. 

노드의 포인터 멤버 변수는 사용자 프로그래머가 신경 쓸 필요가 없는 구현 세부사항의 일부이다.

템플릿 클래스 Node를 사용하는 연결 리스트를 기반으로

ListIterator 클래스를 모든 클래스의 반복자로 사용할 수 있다. 

예시)

템플릿 클래스 Queue를 다시 작성하여 반복자 기능을 갖추고 있다. 

템플릿 클래스 Queue에 대한 인터페이스는 디스플레이 17.32에 나와 있다. 

Queue 템플릿의 이 정의는 이전 버전(디스플레이 17.20)과 동일하지만

다음 두 가지 멤버 함수뿐만 아니라 형식 정의를 추가했다:

Iterator begin( ) const { return Iterator(front); }
Iterator end( ) const { return Iterator( ); }
//The end iterator has end( ).current == NULL.

 

멤버 함수에 대해 먼저 논의해 보겠다.
멤버 함수 begin( )은 큐의 front 노드("to")에 위치한 반복자를 반환하며, 

이는 기본 연결 리스트의 헤드 노드이다.

증가 연산자 ++의 각 응용 프로그램은 반복자를 다음 노드로 이동시킨다.

따라서 노드를 통해 데이터를 다음과 같이 q라는 이름의 큐에서 이동할 수 있다:

for (i = q.begin( ); Stopping_Condition; i++)
    process *i //*i is the current data item .

여기서 i는 반복자 형식의 변수이다.

 

디스플레이 17.31 연결 리스트에 대한 반복자 클래스

//This is the header file iterator.h. This is the interface for the
//class ListIterator, which is a template class for an iterator to use
//with linked lists of items of type T. This file also contains the
//node type for a linked list
#ifndef ITERATOR_H
#define ITERATOR_H

namespace ListNodeSavitch
{
	template<class T>
	class Node
	{
	public:
		Node(T theData, Node<T>* theLink) : data(theData), link(theLink){}
		Node<T>* getLink( ) const { return link; }
		const T& getData( ) const { return data; }
		void setData( const T& theData) { data = theData; }
		void setLink(Node<T>* pointer) { link = pointer; }
	private:
		T data;
		Node<T> *link;
	};
    
	template<class T>
	class ListIterator
	{
	public:
		ListIterator( ) : current(NULL) {}
        
		ListIterator(Node<T>* initial) : current(initial) {}        
		const T& operator *( ) const { return current->getData( ); }
		//Precondition: Not equal to the default constructor object ;
		//that is, current != NULL .        
		ListIterator& operator ++( ) //Prefix form
		{
			current = current->getLink( );
			return *this;
		}        
		ListIterator operator ++( int) //Postfix form
		{
			ListIterator startVersion(current);
			current = current->getLink( );
			return startVersion;
		}        
		bool operator ==( const ListIterator& rightSide) const
		{ return (current == rightSide.current); }
        
		bool operator !=( const ListIterator& rightSide) const
		{ return (current != rightSide.current); }
        
		//The default assignment operator and copy constructor
		//should work correctly for ListIterator .
	private:
		Node<T> *current;
	};
    
} //ListNodeSavitch

#endif //ITERATOR_H

const T& operator *( ) const { return current->getData( ); }

역참조 연산자 *는 노드 전체가 아닌 노드의 데이터 멤버를 생성한다.

이 버전에서는 노드의 데이터를 변경할 수 없다.

 

멤버 함수 end( )는 현재 멤버 변수가 NULL인 반복기를 반환한다.

따라서 반복기 i가 마지막 노드를 통과하면 부울식을 사용한다
i!= q.end( )
true에서 false로 변경된다.

이것이 원하는 Stopping_Condition이다.

이 큐 클래스와 반복자 클래스를 사용하면

반복자를 위해 개요를 설명한 방식으로 큐의 데이터를 순환할 수 있다:
for (i = q.begin( ); i != q.end( ); i++)
     process *i //*i is the current data item .
마지막 노드에 있을 때 i는 q.end( )와 같지 않다.

마지막 노드를 지나 한 위치까지 i가 진행될 때까지 반복기 i는 q.end( )와 같지 않다.

자세한 내용을 기억하려면 q.end( )를 NULL과 같은 엔드 마커라고 생각하라.

이 경우 기본적으로 NULL의 버전이다.

이러한 for문을 사용하는 샘플 프로그램은 디스플레이 17.33에 나와 있다.

 

디스플레이 17.32 반복자 템플릿 클래스가 있는 큐의 인터페이스 파일

//This is the header file queue.h. This is the interface for the class
//Queue, which is a template class for a queue of items of typeT,
//including iterators .
#ifndef QUEUE_H
#define QUEUE_H
#include "iterator.h"
using namespace ListNodeSavitch;

namespace QueueSavitch
{
	template<class T>
	class Queue
	{
	public:
		typedef ListIterator<T> Iterator;
        
		Queue( );
		Queue( const Queue<T>& aQueue);
		Queue<T>& operator =( const Queue<T>& rightSide);
		virtual ~Queue( );
		void add(T item);
		T remove( );
		bool isEmpty( ) const;
        
		Iterator begin( ) const { return Iterator(front);}
		Iterator end( ) const { return Iterator( ); }
		//The end iterator has end( ).current == NULL .
		//Note that you cannot dereference the end iterator .
	private:
		Node<T> *front; //Points to the head of a linked list .
		                //Items are removed at the head .
		Node<T> *back; //Points to the node at the other end of
		               //the linked list .
		               //Items are added at this end .
	};
    
} //QueueSavitch

#endif //QUEUE_H

Node<T> 및 ListIterator<T>의 정의는

파일 iterator.h.의 네임스페이스 List NodeSavitch에 있다.

 

17.33 반복자가 있는 큐 템플릿 클래스를 이용한 프로그램

//Program to demonstrate use of the Queue template class with iterators .
#include <iostream>
#include "queue.h" //not needed
#include "queue.cpp"
#include "iterator.h" //not needed
using std::cin;
using std::cout;
using std::endl;
using namespace QueueSavitch;
int main( )
{
	char next, ans;
	do
	{
		Queue< char> q;
		cout << "Enter a line of text:\n";
		cin.get(next);
		while (next != '\n')
		{
			q.add(next);
			cin.get(next);
		}
        
		cout << "You entered:\n";
		Queue< char>::Iterator i;
        
		for (i = q.begin( ); i != q.end( ); i++)
			cout << *i;
		cout << endl;
        
		cout << "Again?(y/n): ";
		cin >> ans;
		cin.ignore(10000, '\n');
	} while (ans != 'n' && ans != 'N');
    
	return 0;
}

#include "queue.h" //not needed

#include "iterator.h" //not needed

필요하지는 않지만, 많은 프로그래머들은 문서화를 위해 이러한 지시사항을 포함하는 것을 선호한다.

 

Queue< char>::Iterator i;
for (i = q.begin( ); i != q.end( ); i++)
    cout << *i;

만약 컴파일러가 Queue< char>::Iterator i;에 컴플레인이 있는 경우,
using namespace ListNodeSavitch;
ListIterator<char> i;

를 시도하기

 

샘플 대화 상자

Enter a line of text:
Where shall I begin?
You entered:
Where shall I begin?
Again?(y/n): y
Enter a line of text:
Begin at the beginning
You entered:
Begin at the beginning
Again?(y/n): n

 

새큐 템플릿 클래스의 유형 정의에 주목하자:
typedef ListIterator Iterator;

이 typedef가 반드시 필요한 것은 아니다.

Iterator라는 형식 이름 대신 ListIterator<T>를 항상 사용할 수 있다.

그러나 이 typedef를 사용하면 코드를 더 깨끗하게 만들 수 있다.

이 typedef를 사용하면 Queue<char> 클래스의 반복자가 작성된다
Queue<char>::Iterator i;
이를 통해 어떤 클래스의 반복자를 사용해야 하는지 명확히 알 수 있다.

 

새로운 템플릿 클래스 Queue의 구현은 디스플레이 17.34에 제공된다.
이 새로운 Queue 클래스에 추가한 멤버 함수는 인라인으로 정의되어 있기 때문에 

구현 파일에는 실제로 새로울 것이 없지만 

구현 파일을 포함하여 어떻게 배치되는지 보여주고 어떤 방향성을 포함할 것인지 보여준다.

 

디스플레이 17.34 반복자 템플릿 클래스가 있는 큐 구현 파일

//This is the file queue.cpp. This is the implementation of the
//template class Queue. The interface for the template class Queue is
//in the header file queue.h .
#include <iostream>
#include <cstdlib>
#include <cstddef>
#include "queue.h"
using std::cout;

using namespace ListNodeSavitch;
namespace QueueSavitch
{
	template<class T>
	Queue<T>::Queue( ) : front(NULL), back(NULL)
	< The rest of the definition is given in the answer to Self-Test Exercise 16 .>
    
	template<class T>
	Queue<T>::Queue( const Queue<T>& aQueue)
	< The rest of the definition is given in the answer to Self-Test Exercise 19 .>
    
	template<class T>
	Queue<T>& Queue<T>::operator =( const Queue<T>& rightSide)
	< The rest of the definition is given in the answer to Self-Test Exercise 20 .>
    
	template<class T>
	Queue<T>::~Queue( )
	< The rest of the definition is given in the answer to Self-Test Exercise 18 .>
    
	template<class T>
	bool Queue<T>::isEmpty( ) const
	< The rest of the definition is given in the answer to Self-Test Exercise 16 .>
    
	template<class T>
	void Queue<T>::add(T item)
	< The rest of the definition is given in the answer to Self-Test Exercise 17 .>
    
	template<class T>
	T Queue<T>::remove( )
	< The rest of the definition is given in the answer to Self-Test Exercise 17 .>
} //QueueSavitch
#endif //QUEUE_H

멤버 함수 정의는 큐 템플릿의 이전 버전과 동일하며 파일 레이아웃 및 네임스페이스 사용을 보여주기 위해 제공된다.

 

17.4 트리

트리에 대한 자세한 설명은 이 장의 범위를 벗어난다. 

이 장의 목표는 

노드와 포인터를 기반으로 데이터 구조를 구성하고 조작하는 기본적인 기법을 알려주는 것이다. 

연결 리스트는 우리가 토론할 때 좋은 예가 되었다. 

그러나 단일 연결 리스트의 노드들에 대해서는 상당히 제한적인 한 가지 세부 사항이 있는데, 

다른 노드를 가리키는 포인터 멤버 변수가 하나뿐이라는 것이다. 

트리 노드에는 다른 노드에 대한 포인터를 위한 두 개의 멤버 변수가 있다. 

게다가 트리는 매우 중요하고 널리 사용되는 자료 구조이다. 

그래서 트리를 구성하고 조작하는 데 사용되는 일반적인 기법을 간략히 설명하겠다.
이 섹션에서는 13장에서 다루는 재귀를 사용한다.

트리 속성

트리는 디스플레이 17.35와 같은 구조를 가진 자료 구조이다.

트리는 디스플레이 17.35와 같은 구조를 가져야 한다.

특히 트리에서 링크(포인터)를 따르는 경로를 통해 top (루트) 노드에서 임의의 노드에 도달할 수 있다.

트리에는 사이클이 없다는 것에 주목하자.

포인터를 따라가면 결국 끝이 난다.

이런 종류의 int 트리에 대한 노드 클래스의 정의도 디스플레이 17.35에 나와 있다.

각 노드에는 두 개의 링크(두 개의 포인터)가 오는 것에 주목하자.

이진 트리(binary tree): 각 노드에 정확히 두 개의 링크 멤버 변수가 오는 트리

링크 멤버 변수의 개수가 다른 다른 종류의 트리도 있지만 이진 트리가 가장 일반적인 경우이다.

 

디스플레이 17.35 이진 트리

class IntTreeNode
{
public:
	IntTreeNode( int theData, IntTreeNode* left, IntTreeNode* right)
	   : data(theData), leftLink(left), rightLink(right){}
private:
	int data;
	IntTreeNode *leftLink;
	IntTreeNode *rightLink;
};

IntTreeNode *root;

 

루트 노드

root이라는 이름의 포인터는 연결 리스트의 포인터 head와 유사한 목적을 수행한다(디스플레이 17.1).

루트 노드(root node): root 포인터가 가리키는 노드

포인터 root는 그 자체가 루트 노드가 아니라 루트 노드를 가리킨다.

트리의 모든 노드는 링크를 따라 루트 노드에서 연결될 수 있다.
트리(tree)라는 용어가 잘못된 이름처럼 보일 수도 있다.

루트(root)는 나무의 맨 위에 있고

가지치기 구조는 진짜 나무 가지치기 구조라기보다는 뿌리 가지치기 구조처럼 보인다.

그 용어의 비밀은 그림을 거꾸로 뒤집는 것이다(표시 17.35).

그러면 그림은 나무의 가지치기 구조와 닮았고 뿌리 마디는 나무 뿌리가 시작되는 곳이다.

리프 노드(leaf node): 두 링크 멤버 변수가 모두 NULL로 설정된 가지 끝에 있는 노드

이 용어는 이제 어느 정도 의미가 있을지도 모른다.

빈 연결 리스트와 유사하게 포인터 변수 루트를 NULL과 동일하게 설정하여 빈 트리(empty tree)를 표시한다.
트리는 재귀적인 구조를 가지고 있다는 것에 주목하자.

각 트리는 루트 노드가 루트 노드의 leftLink와 rightLink에 의해 가리키는 노드인 두 개의 서브트리를 가지고 있다.

디스플레이 17.35에서는 이 두 부분 트리들을 동그라미로 표시한다.

이런 자연스러운 재귀적 구조는 트리들을 재귀적 알고리즘에 특히 적합하게 만든다.

예를 들어, 각 노드를 방문하여 노드에 있는 데이터를 가지고 무언가를 하는 방식으로 트리를 검색하는 작업을 생각해 보자.

일반적인 공격 계획은 다음과 같다:
전위 순회(preorder) 처리
1. 루트 노드에서 데이터를 처리한다.
2. 왼쪽 하위 트리를 처리한다.
3. 오른쪽 부분 트리를 처리한다.

 

이 세 단계의 순서를 달리하면 이 검색 과정에서 여러 가지 변형을 얻을 수 있다.

다음에는 두 가지 버전이 더 제공된다.
중위 순회(in order) 처리
1. 왼쪽 하위 트리를 처리한다.
2. 루트 노드에서 데이터를 처리한다.
3. 오른쪽 부분 트리를 처리한다.

 

후위 순회(postorder) 처리
1. 왼쪽 하위 트리를 처리한다.
2. 오른쪽 부분 트리를 처리한다.
3. 루트 노드에서 데이터를 처리한다.

 

이진 검색 트리

디스플레이 17.35의 트리는 이진 검색 트리 저장 규칙으로 알려진 특별한 방법으로 트리에 각 숫자를 저장했다.

이진 검색 트리(binary search tree): 이진 검색 트리 저장 규칙을 만족하는 트리

 

이진 검색 트리 저장 규칙(Binary Search Tree Storage Rule)
1. 왼쪽 하위 트리의 모든 값 < 루트 노드의 값
2. 오른쪽 부분 트리의 모든 값 >= 루트 노드의 값
3. 이 규칙은 두 하위 트리 각각에 재귀적으로 적용된다.
(재귀의 기본 경우는 항상 규칙을 만족하는 것으로 간주되는 빈 트리이다.)

 

트리가 이진 검색 트리 저장 규칙을 만족하고
중위 순회 처리 방법을 사용하여 값을 출력하면

숫자가 작은 순서에서 큰 순서로 출력된다.
디스플레이 13.5에 제시된

바이너리 검색 알고리즘과 유사한

바이너리 검색 알고리즘을 사용하면

바이너리 검색 트리 저장 규칙을 따르는 트리의 경우

길이가 길고 얇기보다는 짧고 지방이 많은 트리의 경우

매우 빠르게 값을 검색할 수 있다.

이러한 효율성을 실현하기 위해

이진 저장 트리를 검색하고 유지하는 문제는

여기서 우리가 해결할 수 있는 여지를 넘어서는 큰 주제이다.

예: 트리 템플릿 클래스

디스플레이 17.36에는 이진 탐색 트리에 대한 템플릿 클래스의 정의가 포함되어 있다.

이 예제에서는 SearchTree 클래스를 TreeNode 클래스의 friend 클래스로 만들었다.

이를 통해 트리 클래스 멤버 변수의 정의에서 노드 멤버 변수에 이름을 지정하여 접근할 수 있다.

이 SearchTree 클래스의 구현은 디스플레이 17.37에 제공되며

시연 프로그램은 디스플레이 17.38에 제공된다.

이 템플릿 클래스는 트리 처리의 묘미를 제공하기 위해 고안되었지만 실제로 완전한 예는 아니다.

실제 클래스에는 더 많은 멤버 함수가 있을 것이다.

특히, 실제 트리 클래스에는 복사 생성자와 오버로딩된 할당 연산자가 있을 것이다.

우리는 공간을 절약하기 위해 이것들을 생략했다.

SearchTree 클래스의 함수 정의에 대해 몇 가지 관찰할 사항이 있다.

insert와 inTree 함수는 오버로딩 상태이다.

단일 인수 버전이 우리에게 필요한 것이다.

그러나 가장 명확한 알고리즘은 재귀적 알고리즘이고

재귀적 알고리즘은 부분 트리의 루트에 대해 하나의 매개변수를 추가로 필요로 하다.

따라서 이들 함수 각각에 대해 두 개의 인수로 사설 도움 함수를 정의하고 

2개의 매개변수를 가진 함수에 재귀적 알고리즘을 구현했다.

그런 다음 단일 매개변수 함수는

서브트리 루트 매개변수 집합이 전체 트리의 루트와 동일한 두 개의 매개변수 버전으로 단순히 호출한다.

비슷한 상황이 오버로딩된 멤버 함수 이름을 순서대로 유지한다.

함수 deleteSubtree는 소멸자 함수의 목적과 유사하다.

 

마지막으로 insert 함수는 이진 검색 트리 저장 규칙을 만족하는 트리를 구축한다는 점에 유의해야 한다. 
이 템플릿 클래스의 트리를 만드는 데 insert가 유일한 함수이므로,

이 트리 템플릿 클래스의 객체는 항상 이진 검색 트리 저장 규칙을 만족한다.

함수 inTree는 트리가 이진 검색 트리 저장 규칙을 만족한다는 사실을 알고리즘에 사용한다.

이것은 트리를 검색하는 것을 매우 효율적으로 만든다.

물론 이것은 트리에 저장된 데이터의 T형식에 대해 <연산자가 정의되어야 한다는 것을 의미한다.

일이 올바르게 작동하도록 하기 위해, <연산자는 T형식의 값에 적용될 때 다음 규칙을 만족해야 한다:
■ 민감도(Transitivity): a < b 및 b < c는 a < c를 의미한다.
■ 반대칭(Antisymmetry): a != b이면 a < b 또는 b < a 중 하나지만 둘 다 아니다.
■ 무반전(Irreflexive): 당신은 a < a를 가지고 있지 않다.
대부분의 자연스러운 순서는 이러한 규칙을 충족한다.

 

트리 템플릿 클래스의 인터페이스 파일

//Header file tree.h. The only way to insert data in a tree is with the
//insert function. So, the tree satisfies the Binary Search Tree Storage
//Rule. The function inTree depends on this. < must be defined and
//give a well-behaved ordering to the type T .
#ifndef TREE_H
#define TREE_H
namespace TreeSavitch
{
	template<class T>
	class SearchTree;//forward declaration
    
	template<class T>
	class TreeNode
	{
	public:
		TreeNode( ) : root(NULL){}
		TreeNode(T theData, TreeNode<T>* left, TreeNode<T>* right)
		   : data(theData), leftLink(left), rightLink(right){}
		friend class SearchTree<T>;
	private:
		T data;
		TreeNode<T> *leftLink;
		TreeNode<T> *rightLink;
	};
    
	template<class T>
	class SearchTree
	{
	public:
		SearchTree( ) : root(NULL){}
		virtual ~SearchTree( );
		void insert(T item);//Adds item to the tree.
		bool inTree(T item) const;
		void inorderShow( ) const;
	private:
		void insert(T item, TreeNode<T>*& subTreeRoot);
		bool inTree(T item, TreeNode<T>* subTreeRoot) const;
		void deleteSubtree(TreeNode<T>*& subTreeRoot);
		void inorderShow(TreeNode<T>* subTreeRoot) const;
		TreeNode<T> *root;
	};
    
} //TreeSavitch

#endif

SearchTree 템플릿 클래스에는

복사본 생성자, 할당 연산자의 오버로딩 및 기타 멤버 함수가 있어야 한다.

그러나 이 예제를 짧게 유지하기 위해 이러한 함수를 생략했다.

실제 템플릿 클래스에는 더 많은 멤버 함수와 오버로딩 연산자가 포함된다.

 

디스플레이 17.37 트리 템플릿 클레스의 구현 파일

//This is the implementation file tree.cpp. This is the implementation
//for the template class SearchTree. The interface is in the file tree.h .
namespace TreeSavitch
{
	template<class T>
	void SearchTree<T>::insert(T item, TreeNode<T>*& subTreeRoot)
	{
		if (subTreeRoot == NULL)
			subTreeRoot = new TreeNode<T>(item, NULL, NULL);
		else if (item < subTreeRoot->data)
			insert(item, subTreeRoot->leftLink);
		else//item >= subTreeRoot->data
			insert(item, subTreeRoot->rightLink);
	}
    
	template<class T>
	void SearchTree<T>::insert(T item)
	{
		insert(item, root);
	}
    
	template<class T>
	bool SearchTree<T>::inTree(T item, TreeNode<T>* subTreeRoot) const
	{
		if (subTreeRoot == NULL)
			return false;
		else if (subTreeRoot->data == item)
			return true;
		else if (item < subTreeRoot->data)
			return inTree(item, subTreeRoot->leftLink);
		else//item >= link->data
			return inTree(item, subTreeRoot->rightLink);
	}
    
	template<class T>
	bool SearchTree<T>::inTree(T item) const
	{
		return inTree(item, root);
	}
    
	template<class T> //uses iostream:
	void SearchTree<T>::inorderShow(TreeNode<T>* subTreeRoot) const
	{
		if (subTreeRoot != NULL)
		{
			inorderShow(subTreeRoot->leftLink);
			cout << subTreeRoot->data << " ";
			inorderShow(subTreeRoot->rightLink);
		}
	}
    
	template<class T> //uses iostream:
	void SearchTree<T>::inorderShow( ) const
	{
		inorderShow(root);
	}
    
	template<class T>
	void SearchTree<T>::deleteSubtree(TreeNode<T>*& subTreeRoot)
	{
		if (subTreeRoot != NULL)
		{
			deleteSubtree(subTreeRoot->leftLink);
            
			deleteSubtree(subTreeRoot->rightLink);
            
			//subTreeRoot now points to a one node tree .            
			delete subTreeRoot;
			subTreeRoot = NULL;
		}
	}
    
	template<class T>
	SearchTree<T>::~SearchTree( )
	{
		deleteSubtree(root);
	}
} //TreeSavitch

insert 함수를 사용하여 모든 데이터를 입력하면 트리가 이진 검색 트리 저장 규칙을 충족한다.

inTree 함수는 디스플레이 13.5에 제공된 것의 변형인 이진 탐색 알고리즘을 사용한다.

inorderShow함수: 트리의 중위 순회(in-order traversal)을 사용한다.

deleteSubtree함수: 트리의 후위순회(postorder traversal)을 사용한다.

 

디스플레이 17.38 트리 템플릿 클래스의 시연 프로그램

//Demonstration program for the Tree template class .
#include <iostream>
#include "tree.h"
#include "tree.cpp"
using std::cout;
using std::cin;
using std::endl;
using TreeSavitch::SearchTree;

int main( )
{
	SearchTree< int> t;
    
	cout << "Enter a list of nonnegative integers.\n"
		<< "Place a negative integer at the end.\n";
	int next;
	cin >> next;
	while (next >= 0)
	{
		t.insert(next);
		cin >> next;
	}
    
	cout << "In sorted order: \n";
	t.inorderShow( );
	cout << endl;
    
	return 0;
}

 

샘플 대화 상자

Enter a list of nonnegative integers.
Place a negative integer at the end.
40 30 20 10 11 22 33 44 -1
In sorted order:
10 11 20 22 30 33 40 44