이 진 트 리 의 만 들 기, 옮 겨 다 니 기

이 프로그램 은 인터넷 의 절 차 를 참고 하 였 습 니 다. 감사합니다.
이 프로그램 은 자체 적 으로 데이터 구 조 를 참고 하여 스 택 과 대기 열의 템 플 릿 류 를 다시 참고 하고 인터넷 의 프로그램 을 참고 하여 이 진 트 리 의 구축 과 세 가지 스 트 리밍 방식 (재 귀 와 비 재 귀 실현 포함) 을 썼 다.
대기 열의 실현:

#ifndef __BT_QUEUE__
#define __BT_QUEUE__

/************************************************************************/
/*       ，    、  、                                */
/*     ，              								*/
/************************************************************************/

#include <iostream>

template<typename T>
class BT_Queue
{
public:
	BT_Queue(void);
	~BT_Queue(void){}
	typedef struct qnode{
		T data;
		struct qnode *next;
	}QTYPE;
	QTYPE *front, *rear;
	void initQueue();
	void push(T t);
	void pop();
	int empty();
};

template<typename T>
BT_Queue<T>::BT_Queue(void)
{
	initQueue();
}

template<class T>
void BT_Queue<T>::initQueue()
{
	QTYPE *p;
	p = (QTYPE*)malloc(sizeof(QTYPE));
	p->next = NULL;
	front = rear = p;
}

template<class T>
void BT_Queue<T>::push(T t)
{
	QTYPE *s;
	s = (QTYPE*)malloc(sizeof(QTYPE));
	s->data = t;
	s->next = rear->next;
	rear->next = s;
	rear = s;
}

template<class T>
int BT_Queue<T>::empty()
{
	return front == rear ? 1 : 0;
}

template<class T>
void BT_Queue<T>::pop()
{
	QTYPE *p;
	if(empty())
	{
		printf("queue is free");
		return;
	}
	p = front->next;
	front->next = p->next;
	if(front->next == NULL)
		rear = front;
	free(p);
}

#endif

템 플 릿 류 의 설명 과 구현 을 같은 파일 에 두 어야 합 니 다.
창고 의 실현:

#ifndef __BT_STACK__
#define __BT_STACK__

#include <iostream>

template<class T>
class BT_Stack
{
public:
	BT_Stack();
	~BT_Stack(){}
	typedef struct snode{
		T data;
		struct snode *next;
	}LinkStack;
	LinkStack *top;
	
	void initStack();
	void push(T t);
	void pop();
	int empty();
	T getTop();
};

template<class T>
BT_Stack<T>::BT_Stack()
{
	initStack();
}

template<class T>
void BT_Stack<T>::initStack()
{
	top = (LinkStack*)malloc(sizeof(LinkStack));
	(top)->next = NULL;
}

template<class T>
void BT_Stack<T>::push(T t)
{
	LinkStack* s;
	s = (LinkStack*)malloc(sizeof(LinkStack));
	s->data = t;
	s->next = (top)->next;
	(top)->next = s;
}

template<class T>
int BT_Stack<T>::empty()
{
	return (top)->next == NULL ? 1 : 0;
}

template<class T>
void BT_Stack<T>::pop()
{
	LinkStack *s;
	if(empty())
	{
		printf("stack is free");
		return;
	}
	s = (top)->next;
	(top)->next = s->next;
	free(s);
}

template<class T>
T BT_Stack<T>::getTop()
{
	if(empty())
	{
		printf("stack is free");
		return NULL;
	}
	return (top)->next->data;
}
#endif

 
이 진 트 리 코드 부분:

#include <stdio.h>
#include <malloc.h>
#include <time.h>
// #include <stack>
// #include <queue>
#include <assert.h>
#include "BT_Queue.h"
#include "BT_Stack.h"

using namespace std;

#define MAX_CNT 10
#define BASE  100

typedef int ElemType;

typedef struct treeT
{
	ElemType key;
	struct treeT* left;
	struct treeT* right;
}treeT, *pTreeT;

//      
static void visit(pTreeT root)
{
	if (NULL != root)
	{
		printf(" %d
", root->key);
	}
}


//       
static pTreeT BT_MakeNode(ElemType target)
{
	pTreeT pNode = (pTreeT) malloc(sizeof(treeT));

	assert( NULL != pNode ); 

	pNode->key   = target;
	pNode->left  = NULL;
	pNode->right = NULL;

	return pNode;
}

//     
pTreeT BT_Insert(ElemType target, pTreeT* ppTree)
{
	pTreeT Node;

	assert( NULL != ppTree ); 

	Node = *ppTree;
	if (NULL == Node)
	{
		return *ppTree = BT_MakeNode(target);
	}

	if (Node->key == target)    //          
	{
		return NULL;
	}
	else if (Node->key > target)    //  
	{
		return BT_Insert(target, &Node->left);
	}
	else
	{
		return BT_Insert(target, &Node->right);
	}
}



//        （  ）
void BT_PreOrder(pTreeT root)
{
	if (NULL != root)
	{
		visit(root);
		BT_PreOrder(root->left);
		BT_PreOrder(root->right);
	}    
}
//        （   ）
void BT_PreOrderNoRec(pTreeT root)
{
	BT_Stack<treeT *> s;

	while ((NULL != root) || !s.empty())
	{
		if (NULL != root)
		{
			visit(root);
			s.push(root);
			root = root->left;
		}
		else
		{
			root = s.getTop();
			s.pop();
			root = root->right;
		}
	}
}


//        （  ）
void BT_InOrder(pTreeT root)
{
	if (NULL != root)
	{
		BT_InOrder(root->left);
		visit(root);
		BT_InOrder(root->right);
	}
}
//        （   ）
void BT_InOrderNoRec(pTreeT root)
{
	BT_Stack<treeT *> s;
	while ((NULL != root) || !s.empty())
	{
		if (NULL != root)
		{
			s.push(root);
			root = root->left;
		}
		else
		{
			root = s.getTop();
			visit(root);
			s.pop();
			root = root->right;
		}
	}
}


//        （  ）
void BT_PostOrder(pTreeT root)
{
	if (NULL != root)
	{
		BT_PostOrder(root->left);
		BT_PostOrder(root->right);
		visit(root);    
	}
}
//        （   ）
void BT_PostOrderNoRec(pTreeT root)
{
	BT_Stack<treeT *> s; 
	pTreeT pre = NULL; 

	while ((NULL != root) || !s.empty()) 
	{ 
		if (NULL != root) 
		{ 
			s.push(root); 
			root = root->left; 
		} 
		else 
		{ 
			root = s.getTop(); 
			if (root->right != NULL && pre != root->right)
			{ 
				root = root->right; 
			} 
			else
			{ 
				root = pre = s.getTop(); 
				visit(root); 
				s.pop(); 
				root = NULL; 
			} 
		} 
	} 
}

//      
void BT_LevelOrder(pTreeT root)
{
	BT_Queue<treeT *> q;
	treeT *treePtr;

	assert( NULL != root ); 

	q.push(root);

	while (!q.empty())
	{
		treePtr = q.front->next->data;
		q.pop();
		visit(treePtr);

		if (NULL != treePtr->left)
		{
			q.push(treePtr->left);    
		}
		if (NULL != treePtr->right)
		{
			q.push(treePtr->right);
		}    

	}
}


int main(int argc, char *argv[])
{
	int i;
	pTreeT root = NULL;

	srand( (unsigned)time( NULL ) ); 

	for (i=0; i<MAX_CNT; i++)
	{
		BT_Insert(rand() % BASE, &root);
	}

	//  
	printf("PreOrder:
");
	BT_PreOrder(root);
	printf("
");

	printf("PreOrder no recursion:
");
	BT_PreOrderNoRec(root);
	printf("
");

	//  
	printf("InOrder:
");
	BT_InOrder(root);
	printf("
");

	printf("InOrder no recursion:
");
	BT_InOrderNoRec(root);
	printf("
");

	//  
	printf("PostOrder:
");
	BT_PostOrder(root);
	printf("
");

	printf("PostOrder no recursion:
");
	BT_PostOrderNoRec(root);
	printf("
");

	//  
	printf("LevelOrder:
");
	BT_LevelOrder(root);
	printf("
");
	system("pause");
	return 0;
}