資料結構分類總結

文章目錄

• 樹
• • 樹的建構
  • 樹的周遊

樹

樹的建構

typedef struct node
{
	int value;
	struct node * lchild;
	struct node * rchild;
}BSTNode
           

bool InsertBST( BSTNode *& tree, int value )
{
	if ( tree == NULL ){
		tree = new BSTNode();
		tree->value = value;
		tree->lchild = NULL;
		tree->rchild = NULL;
		return true;
	}
	if (value == tree->value){
		return false;
	}else if(value < tree->value){
		InsertBST( tree->lchild );
	}
	else{
		InsertBST( tree->rchild );
	}
}
BSTNode *CreateBST( int arr[], int n)
{
	int i = 0;
	BSTNode *tree = NULL;
	for( ; i < n; i++ ){
		Insert( tree, arr[i] )
	} 
	return tree;
}
           

樹的周遊

①、先序周遊

void PreOrder( BSTNode *b )
{
	if ( b ！= NULL ){
		printf( "%d\n", b->value );
		PreOrder( b->rchild );
		PreOrder( b->lchild );
	}
}
           

②、中序周遊

void InOrder( BSTNode *b )
{
	if ( b ！= NULL ){
		InOrder( b->rchild );
		printf( "%d\n", b->value );
		InOrder( b->lchild );
	}
}
           

③、後序周遊

void PostOrder( BSTNode *b )
{
	if ( b ！= NULL ){
		PostOrder( b->rchild );
		PostOrder( b->lchild );
		printf( "%d\n", b->value );
	}
}