subset.c

这是一个关于用递推法解决求某一个集合的所有的子集。非常适合初学数据结构的同胞阅读。

#define MaxQueueSize   10
typedef char DataTypeQ;
#include"SeqQueue.h"

typedef SeqQueue DataTypeT;
#include"Tree.h"



void Subset(BiTreeNode *t, SeqQueue q, int flag)
{
	char c;
	SeqQueue p;

	if( t == NULL )
		return ;

	if( flag == 0 )
	{
		QueueDelete( &q, &c );

		p = t->data;

		QueueAppend(&p, c);

		InsertLeftNode(t, p);

		if( !QueueNotEmpty(q) )
		{
			printf("  (");
			while( QueueNotEmpty(p) )
			{
				QueueDelete(&p, &c);
				printf("%c", c);
			
			}
			printf(")");
			
			return;
		}

		Subset(t->left, q, 0);
		Subset(t->left, q, 1);
	}

	else
	{
		QueueDelete( &q, &c );

		p = t->data;

		InsertRightNode(t, p);

		if( !QueueNotEmpty(q) )
		{
			printf("  (");
			while( QueueNotEmpty(p) )
			{
				QueueDelete(&p, &c);
				printf("%c", c);
			}
			printf(")");

			return;
		}

		Subset(t->right, q, 0);
		Subset(t->right, q, 1);


	}


}


void main()
{
	int i;
	SeqQueue q;
	char a[4] = {'A','B','C'};

	BiTreeNode *root;

	QueueInitiate(&q);
	Initiate(&root);

	InsertLeftNode(root, q);


	printf("\nThe set is:(");
	for( i = 0; i < 3; i ++ )
	{
		QueueAppend(&q,a[i]);
		printf("%c",a[i]);
	}
	printf(")\n");

	printf("\nThe subset is:{");
	Subset(root->left, q, 0);
	Subset(root->left, q, 1);

	printf("  }\n");
	Destroy(&root);


}