데이터 간 관계를 자식, 부모 관계로 표현하는 2차원적인 자료 구조. 자료의 삽입, 삭제가 빠르고 검색에 유리하다. 용량이 커져도 속도의 감소가 작아 대용량의 자료를 처리할 때 유용하다.

tree_traverse.cpp

#include <stdio.h>
#include <stdlib.h>
 
struct Node
{
	int data;
	Node *left;
	Node *right;
};
Node *Root;
 
void InitTree(int data)
{
	Root=(Node *)malloc(sizeof(Node));
	Root->data=data;
}
 
Node *AddChild(Node *Parent,int data,bool bLeft)
{
	Node *New;
 
	New=(Node *)malloc(sizeof(Node));
	New->data=data;
	New->left=NULL;
	New->right=NULL;
	if (bLeft) {
		Parent->left=New;
	} else {
		Parent->right=New;
	}
	return New;
}
 
void PreOrder(Node *R)
{
	printf("%d ",R->data);
	if (R->left) PreOrder(R->left);
	if (R->right) PreOrder(R->right);
}
 
void InOrder(Node *R)
{
	if (R->left) InOrder(R->left);
	printf("%d ",R->data);
	if (R->right) InOrder(R->right);
}
 
void PostOrder(Node *R)
{
	if (R->left) PostOrder(R->left);
	if (R->right) PostOrder(R->right);
	printf("%d ",R->data);
}
 
void FreeTree(Node *R)
{
	if (R->left) FreeTree(R->left);
	if (R->right) FreeTree(R->right);
	free(R);
}
 
void main()
{
	Node *Left,*Right;
 
	InitTree(1);
	Left=AddChild(Root,2,true);
	Right=AddChild(Root,3,false);
	AddChild(Left,4,true);
	AddChild(Left,5,false);
	AddChild(Right,6,true);
 
	PreOrder(Root);puts("");
	InOrder(Root);puts("");
	PostOrder(Root);puts("");
 
	FreeTree(Root);
}

• 위키피디아
  
• 김상형 씨 홈페이지