(二)二叉樹の抽象的なデータタイプの定義と遍歴

タイプ名:フォークツリー
データの対象セット:貧しい集合点があります.空でないとルートノードとその左、右のフォークツリーからなります.
操作セット:
Boolean isempty
(
BinTree BT
)0
//BTが空かどうか判別する
void
Traversal
(
BinTree BT
)0
//遍歴して、各結点をある順に訪問します.
BinTree Creat BinTree
()
    
//フォークツリーを作成する
//一般的なエルゴード方法は以下の通りです.
void
PreOrder Traversal
(
BinTree BT
)0
//先序-----根、左子樹、右子樹
void
InOrder Traversal
(
BinTree BT
)0
//中序-----左子樹、根、右子樹
void
LevelOrder Traversal
(
BinTree BT
)0
//後順に遍歴-----左子樹、右子樹、根
(1)まず、巡回
プロセスを巡回:1、ルートノードにアクセスします.2、左サブツリーにアクセスします.3、右サブツリーにアクセスします. 

void PreOrderTraversal(BinTree BT)
{
	if(BT){
		printf("%d",BT->Data);
		PreOrderTraversal(BT->Left); 
		PreOrderTraversal(BT->Right);
	}
}

(2)中順序巡回
プロセスを巡回しました.1、左のツリーにアクセスします.2、ルートノードにアクセスする.3、右サブツリーにアクセスする

void InOrderTraversal(BinTree BT) //    
{
	if(BT){
		InOrderTraversal(BT->Left);
		printf("%d",BT->Data);
		InOrderTraversal(BT->Right);
	}
}

(3)を巡回しました.
プロセスを巡回しました.1、左のツリーにアクセスします.2、右サブツリーにアクセスします.3、ルートノードにアクセスする

void LevelOrderTraversal(BinTree BT)//    
{
	if(BT){
		LevelOrderTraversal(BT->Left);
		LevelOrderTraversal(BT->Right);
		printf("%d",BT->Data);
	}
} 

で巡回された非再帰的アルゴリズム

void InOrderTraversal( BinTree BT )
{ 
	BinTree T = BT;
	Stack S = CreatStack( MaxSize ); /*        S*/
	while( T || !IsEmpty(S) ){
		while(T){ /*              */
		Push(S,T);
		T = T->Left;
		}
		if(!IsEmpty(S)){
			T = Pop(S); /*      */
			printf(“%5d”, T->Data); /*（  ）    */
			T = T->Right; /*     */
		}
	}
}

最初に非再帰的アルゴリズムを巡回します.

void InOrderTraversal( BinTree BT )
{ 
	BinTree T = BT;
	Stack S = CreatStack( MaxSize ); /*        S*/
	while( T || !IsEmpty(S) ){
		while(T){ /*              */
			Push(S,T);
			printf(“%5d”, T->Data); /*（  ）    */
			T = T->Left;
		}
		if(!IsEmpty(S)){
			T = Pop(S); /*      */
			T = T->Right; /*     */
		}
	}
}