二叉木の先序,中序,後序の非再帰遍歴(C言語実装)

12649 ワード

c struct tree テスト null

1、順序スタックの宣言

#ifndef _seq_stack_h
#define _seq_stack_h

#include "binary_tree.h"

#define STACK_INIT_SIZE 5
#define STACK_INCR_SIZE 2

typedef bitree_node * stack_elem_type;
//typedef int stack_elem_type;

typedef struct seq_stack
{
	stack_elem_type * base;
	stack_elem_type * top;
	int size;
}seq_stack;

void init_stack_sq( seq_stack * stack );
void free_stack_sq( seq_stack * stack );

stack_elem_type get_top_sq( seq_stack stack );
void pop_elem_sq( seq_stack * stack );
void push_elem_sq( seq_stack * stack, stack_elem_type e );

int stack_empty_sq( seq_stack stack );
int stack_length_sq( seq_stack stack );

void trav_stack_sq( seq_stack stack );

#endif

2、順序スタックの実現

#include <stdlib.h>
#include <stdio.h>
#include <assert.h>

#include "seq_stack.h"

void init_stack_sq( seq_stack * stack )
{
	stack->size = STACK_INIT_SIZE;
	stack->base = stack->top = ( stack_elem_type * )malloc( STACK_INIT_SIZE * sizeof( stack_elem_type ) );
	assert( stack->base != NULL );
}

void free_stack_sq( seq_stack * stack )
{
	stack->size = 0;
	free( stack->base );
	stack->base=  stack->top = NULL;
}

void push_elem_sq( seq_stack * stack, stack_elem_type e )
{
	stack_elem_type * base = NULL, * p = NULL, * q = NULL;
	if( stack->top - stack->base >= stack->size )
	{
		stack->size += STACK_INCR_SIZE;
		base = ( stack_elem_type * )malloc( sizeof( stack_elem_type ) * stack->size );
		assert( base != NULL );
		p = base; q = stack->base;
		while( q < stack->top )
			*p++ = *q++;
		free( stack->base );
		stack->base = base;
		stack->top = stack->base + ( stack->size - STACK_INCR_SIZE );
	}
	*stack->top++ = e;
}

stack_elem_type get_top_sq( seq_stack stack )
{
	return stack_empty_sq( stack ) ? NULL : *( stack.top - 1 );
}

void pop_elem_sq( seq_stack * stack )
{
	assert( stack->top > stack->base );
	--stack->top;
}

int stack_length_sq( seq_stack stack )
{
	return stack.top - stack.base;
}

int stack_empty_sq( seq_stack stack )
{
	return stack.base == stack.top;
}

void trav_stack_sq( seq_stack stack )
{
	stack_elem_type * p = stack.base;
	while( p < stack.top )
		printf( "%c ", (*p++)->data );
	printf( "
" );
}

3、循環キューの宣言

#ifndef _circ_queue_h
#define _circ_queue_h

#include "binary_tree.h"

typedef bitree_node * queue_elem_type;

typedef struct circ_queue 
{
	queue_elem_type * buffer;
	int front, rear;
	int size;
}circ_queue;

void init_circ_queue( circ_queue * cq );
void clear_circ_queue( circ_queue * cq );
void free_circ_queue( circ_queue * cq );

void trav_circ_queue( circ_queue cq );

int push_elem_cq( circ_queue * cq, queue_elem_type e );
queue_elem_type get_front_elem_cq( circ_queue cq );
void pop_elem_cq( circ_queue * cq );

int circ_queue_length( circ_queue cq );
int circ_queue_empty( circ_queue cq );


#endif

4、循環行列の実現

#include <stdlib.h>
#include <stdio.h>
#include <assert.h>
#include "circ_queue.h"

void init_circ_queue( circ_queue * cq )
{
	cq->size = 10;
	cq->buffer = ( queue_elem_type * )malloc( sizeof( queue_elem_type ) * cq->size );
	assert( cq->buffer );
	cq->front = cq->rear = 0;
}

void clear_circ_queue( circ_queue * cq )
{
	cq->front = cq->rear = 0;
}

void free_circ_queue( circ_queue * cq )
{
	cq->size = 0;
	free( cq->buffer );
	cq->front = cq->rear = 0;
}

int circ_queue_empty( circ_queue cq )
{
	return cq.front == cq.rear;
}

int circ_queue_full( circ_queue cq )
{
	return ( cq.rear + 1 ) % cq.size == cq.front;
}

void trav_circ_queue( circ_queue cq )
{
	int i;
	if( ! circ_queue_empty( cq ) )
	{
		i = cq.front;
		while( i % cq.size != cq.rear )
		{
			printf( "%c ", cq.buffer[i++]->data );
		}
	}
}

int push_elem_cq( circ_queue * cq, queue_elem_type e )
{
	int res = -1;
	if( ! circ_queue_full( *cq ) )
	{
		cq->buffer[cq->rear++] = e;
		cq->rear %= cq->size;
		res = 0;
	}
	return res;
}

queue_elem_type get_front_elem_cq( circ_queue cq )
{
	return circ_queue_empty( cq ) ? NULL : cq.buffer[cq.front];
}

void pop_elem_cq( circ_queue * cq )
{
	assert( ! circ_queue_empty( *cq ) );
	cq->front = ( cq->front + 1 ) % cq->size;
}

int circ_queue_length( circ_queue cq )
{
	return ( cq.rear - cq.front + cq.size ) % cq.size;
}

5.後段遍歴のための順序スタックタイプ宣言

#ifndef _post_order_seq_stack_h
#define _post_order_seq_stack_h

#include "binary_tree.h"

#define STACK_INIT_SIZE 5
#define STACK_INCR_SIZE 2

typedef enum visit_flag 
{ 
	LR, RR 
}visit_tag;

typedef struct po_stack_elem_type
{
	bitree_node * ptr;
	visit_tag tag;
}po_stack_elem_type;


typedef struct po_seq_stack
{
	po_stack_elem_type * base;
	po_stack_elem_type * top;
	int size;
}po_seq_stack;

void init_stack_posq( po_seq_stack * stack );
void free_stack_posq( po_seq_stack * stack );

po_stack_elem_type get_top_posq( po_seq_stack stack );
void pop_elem_posq( po_seq_stack * stack );
void push_elem_posq( po_seq_stack * stack, po_stack_elem_type e );

int stack_empty_posq( po_seq_stack stack );
int stack_length_posq( po_seq_stack stack );


#endif

6、ツリータイプ宣言

#ifndef _binary_tree_h
#define _binary_tree_h

typedef char elem_type;

typedef struct bitree_node
{
	elem_type data;
	struct bitree_node * lchild, * rchild;
}bitree_node;

typedef bitree_node * binary_tree;

void create_bitree( binary_tree * root );
void free_bitree( binary_tree * root );

void trav_preorder( binary_tree root );
void trav_preorder_recur( binary_tree root );

void trav_inorder( binary_tree root );
void trav_inorder_recur( binary_tree root );

void trav_postorder( binary_tree root );
void trav_postorder_recur( binary_tree root );

void trav_level_order( binary_tree root );

#endif

7、二叉木実現

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include "binary_tree.h"
#include "seq_stack.h"
#include "circ_queue.h"
#include "po_seq_stack.h"

void create_bitree( binary_tree * root )
{
	char ch;
	if( ( ch = getchar() ) == '#' )
	{
		*root = NULL;
	}
	else
	{
		*root = ( bitree_node * )malloc( sizeof( bitree_node ) );
		( *root )->data = ch;
		create_bitree( &( *root )->lchild );
		create_bitree( &( *root )->rchild );
	}
}

void free_bitree( binary_tree * root )
{
	if( *root != NULL )
	{
		free_bitree( &( *root )->lchild );
		free_bitree( &( *root )->rchild );
		free( *root );
		*root = NULL;
	}
}

void trav_preorder_recur( binary_tree root )
{
	if( root != NULL )
	{
		printf( "%c", root->data );
		trav_preorder_recur( root->lchild );
		trav_preorder_recur( root->rchild );
	}
}

void trav_inorder_recur( binary_tree root )
{
	if( root != NULL )
	{
		trav_inorder_recur( root->lchild );
		printf( "%c ", root->data );
		trav_inorder_recur( root->rchild );
	}
}

void trav_postorder_recur( binary_tree root )
{
	if( root != NULL )
	{
		trav_postorder_recur( root->lchild );
		trav_postorder_recur( root->rchild );
		printf( "%c ", root->data );
	}
}

void trav_preorder( binary_tree root )
{
	seq_stack node_seq; /* node sequence */
	stack_elem_type p = root;

	init_stack_sq( &node_seq );
	push_elem_sq( &node_seq, NULL );

	while( p != NULL )
	{
		printf( "%c ", p->data );
		if( p->rchild != NULL )
			push_elem_sq( &node_seq, p->rchild );
		if( p->lchild != NULL )
			p = p->lchild;
		else
		{
			p = get_top_sq( node_seq );
			pop_elem_sq( &node_seq );
		}
	}
	free_stack_sq( &node_seq );
}


void trav_inorder( binary_tree root )
{
	seq_stack stack;
	bitree_node * p = root;

	init_stack_sq( &stack );
	while( p != NULL || ! stack_empty_sq( stack ) )
	{
		if( p != NULL )
		{
			push_elem_sq( &stack, p );
			p = p->lchild;
		}
		else
		{
			p = get_top_sq( stack );
			pop_elem_sq( &stack );
			printf( "%c ", p->data );
			p = p->rchild;
		}
	}

	free_stack_sq( &stack );
}

void trav_postorder( binary_tree root )
{
	po_seq_stack stack; // po: post-order
	po_stack_elem_type elem;
	bitree_node * p = root;
	init_stack_posq( &stack );
	while( p != NULL || ! stack_empty_posq( stack ) )
	{
		while( p != NULL )
		{
			elem.ptr = p;
			elem.tag = LR;
			push_elem_posq( &stack, elem );
			p = p->lchild;
		}

		elem = get_top_posq( stack );
		pop_elem_posq( &stack );
		p = elem.ptr;

		if( elem.tag == LR )
		{
			elem.tag = RR;
			push_elem_posq( &stack, elem );
			p = p->rchild;
		}
		else
		{
			printf( "%c ", p->data );
			p = NULL;
		}
	}
	
	free_stack_posq( &stack );
}

void trav_level_order( binary_tree root )
{
	circ_queue cq;
	queue_elem_type p = NULL;
	init_circ_queue( &cq );
	if( root != NULL )
	{
		push_elem_cq( &cq, root );
		while( ! circ_queue_empty( cq ) )
		{
			p = get_front_elem_cq( cq );
			pop_elem_cq( &cq );
			printf( "%c ", p->data );
			if( p->lchild != NULL )
				push_elem_cq( &cq, p->lchild );
			if( p->rchild != NULL )
				push_elem_cq( &cq, p->rchild );
		}
	}

	free_circ_queue( &cq );
}

8、試験手順

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

#include "binary_tree.h"
#include "seq_stack.h"

int main( int argc, char * argv[] )
{
	binary_tree root = NULL;
	create_bitree( &root );
	printf( "PreOrder recursive: " );
	trav_preorder_recur( root );
	printf( "
" );

	trav_preorder( root );
	printf( "

" );

	printf( "InOrder recursive: " );
	trav_inorder_recur( root );
	printf( "
" );

	trav_inorder( root );
	printf( "

" );

	printf( "PostOrder recursive:" );
	trav_postorder_recur( root );
	printf( "
" );

	trav_postorder( root );
	printf( "

" );

	printf( "Level Order: " );
	trav_level_order( root );
	printf( "
" );

	free_bitree( &root );

	return 0;
}

c#udp受信単純テスト

GameCenter authenticate:GKErrorDomain Code=2 "The requested operation has been cancelled."