《대화데이터구조》 독서노트(二)

6장 트리(Tree)
트리(Tree)는 n(n>=0)개의 결점의 유한 집합이다.n=0일 때 빈 나무라고 부른다.비어 있지 않은 모든 트리에서 다음을 수행합니다.
1) 뿌리(Root)라는 특정한 결점이 있고 하나만 있음.
2) n>1일 경우 나머지 결점은 m(m>0)개의 서로 교차하지 않는 유한 집합 T1, T2,......,Tm로 나눌 수 있는데 그 중에서 각 집합 자체는 하나의 나무이고 뿌리의 자수(SubTree)라고 부른다.
두 갈래 나무(Binary Tree)는 n(n>=0)개의 결점의 유한한 집합으로 이 집합은 공집합(공두 갈래 나무라고 부른다)이거나 한 뿌리 결점과 두 그루가 서로 교차하지 않는 것을 각각 뿌리 결점이라고 부른다
왼쪽 나무와 오른쪽 나무의 두 갈래 나무로 이루어져 있다.

/*                */
typedef struct BiTNode  /*      */
{
	TElemType data;   /*      */
	struct BiTNode *lchild, *rchild;   /*        */
} BiTNode, *BiTree;

두 갈래 나무의 스트리밍(traversing binary tree)은 뿌리 결점에서 출발하여 어떤 순서에 따라 두 갈래 나무의 모든 결점을 순서대로 방문하여 매 결점이 한 번 방문하고 한 번만 방문하는 것을 말한다.
두 갈래 나무를 옮겨다니는 방법은 다음과 같다.
1. 앞 순서 두루

/*              */
void PreOrderTraverse(BiTree T)
{
	if ( T==NULL )
		return;

	printf("%c",T->data);        /*       ，             */

	PreOrderTraverse(T->lchild); /*          */
	
	PreOrderTraverse(T->rchild); /*           */

}

2. 중간 순서 반복

/*              */
void InOrderTraverse(BiTree T)
{
	if ( T==NULL )
		return;

	InOrderTraverse(T->lchild);  /*         */

	printf("%c",T->data);        /*       ，             */
	
	InOrderTraverse(T->rchild); /*           */

}

3. 후순 두루

/*              */
void PostOrderTraverse(BiTree T)
{
	if ( T==NULL )
		return;

	PostOrderTraverse(T->lchild); /*          */
	
	PostOrderTraverse(T->rchild); /*          */

	printf("%c",T->data);        /*       ，             */


}

4. 차례차례
층차순력서에 알고리즘이 첨부되어 있지 않으며 정리 결과는 다음과 같다.
층차 스트리밍 알고리즘에서 대기열(FIFO) 방식으로 이루어졌는데 대기열의 실현에 대해서는 자세히 말하지 않겠습니다.

/*              */
void LayerOrderTraverse(BiTree T)
{
	if ( T==NULL )
		return;

	BiTree *x;

	Queue Q;         /*     Q */

	InitQueue(&Q);   /*      Q */

	EnQueue(&Q,T);   /*        */

	while(! QueueEmpty(Q))   /*       */
	{
		DeQueue(&Q, x);   /*         ，    x */

		printf("%c",(*x)->data);  /*       ，             */

		if ((*x)->lchild)
			EnQueue(&Q,(*x)->lchild);  /*      ，        */

		if ((*x)->rchild)
			EnQueue(&Q,(*x)->rchild);  /*      ，        */

	}
}