数据结构分类总结

文章目录

• 树
• • 树的构建
  • 树的遍历

树

树的构建

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 );
	}
}