二叉树的顺序贮存结构
总结：树的结构中主要要把握递归的思想。
头文件
#ifndef STREEHEAD_H_INCLUDED
#define STREEHEAD_H_INCLUDED#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#define MAX_TREE_SIZE 100
typedef int SqBiTree[MAX_TREE_SIZE] ;
int InitBiTree( SqBiTree T ) ;
int DestroyBiTree( SqBiTree T ) ;
int CreateBiTree( SqBiTree T ) ;
int ClearBiTree( SqBiTree T ) ;
int EmptyBiTree( SqBiTree T ) ;
int BiTreeDepth( SqBiTree T ) ;
int Root( SqBiTree T ) ;
int Value( SqBiTree T , int e ) ;
int Assign( SqBiTree T , int e , int value ) ;
int Parent( SqBiTree T , int e ) ;
int LeftChild( SqBiTree T , int e ) ;
int RightChild( SqBiTree T , int e ) ;
int LeftSibling( SqBiTree T , int e ) ;
int RightSibling( SqBiTree T , int e ) ;
int InsertChild( SqBiTree T , int e , int lor , SqBiTree C ) ;
int Move( SqBiTree S , int i , SqBiTree T , int j ) ;
int DeleteChild( SqBiTree T , int e ) ;
int PrintBiTree( SqBiTree T ) ;
int PreOrderTraverse( SqBiTree T , int e ) ;
int InTraverse( SqBiTree T , int e ) ;
int InOrderTraverse( SqBiTree T , int e ) ;
int PostOrderTraverse( SqBiTree T , int e ) ;
#endif // STREEHEAD_H_INCLUDED
函数实现
#include "Streehead.h"
int InitBiTree( SqBiTree T )
{
int i ;
for( i = 0 ; i < MAX_TREE_SIZE ; i++ )
{
T[i] = 0 ;
}
return 0 ;
}
int DestroyBiTree( SqBiTree T )
{
return 0 ;
}
int CreateBiTree( SqBiTree T )
{
printf( "请输入节点的值，输入0表示空结点，输999结束。\n" ) ;
int i = 0 ;
while( 1 )
{
scanf( "%d" , &T[i] ) ;
if( T[i] == 999 )
{
break ;
}
if( i != 0 && T[(i + 1)/2 - 1] == 0 && T[i] != 0 )
{
printf( "ERROR!\n" ) ;
exit( 1 ) ;
}
i++ ;
}
while( i < MAX_TREE_SIZE )
{
T[i++] = 0 ;
}
return 0 ;
}
int ClearBiTree( SqBiTree T )
{
int i ;
for( i = 0 ; i < MAX_TREE_SIZE ; i++ )
{
T[i] = 0 ;
}
return 0 ;
}
int EmptyBiTree( SqBiTree T )
{
if( T[0] == 0 )
{
return 1 ;
}
return 0 ;
}
int BiTreeDepth( SqBiTree T )
{
int i = MAX_TREE_SIZE ;
while( T[ i - 1 ] == 0 )
{
i-- ;
if( i == 0 )
{
break ;
}
}
if( i == 0 )
{
return 0 ;
}
return ( log( i ) / log( 2 ) + 1 );
}
int Root( SqBiTree T )
{
if( T[0] == 0 )
{
printf( "ERROR!\n" ) ;
exit( 1 ) ;
}
return T[0] ;
}
int Value( SqBiTree T , int e )
{
if( e <= 0 || e > MAX_TREE_SIZE )
{
printf( "ERROR!\n" ) ;
exit( 1 ) ;
}
if( T[0] == 0 )
{
printf( "ERROR!\n" ) ;
exit( 1 ) ;
}
if( T[ e - 1] == 0 )
{
printf( "ERROR!\n" ) ;
exit( 1 ) ;
}
return T[ e - 1 ] ;
}
int Assign( SqBiTree T , int e , int value )
{
if( e <= 0 || e > MAX_TREE_SIZE )
{
printf( "ERROR!\n" ) ;
exit( 1 ) ;
}
if( value == 0 )
{
if( e == 1 )
{
printf( "ERROR!\n" ) ;
exit( 1 ) ;
}
else if( e != 1 && 2 * e < MAX_TREE_SIZE && ( T[ 2 * e - 1 ] != 0 || T[ 2 * e ] != 0 ) )
{
printf( "ERROR!\n" ) ;
exit( 1 ) ;
}
T[ e - 1 ] = value ;
}
else
{
if( e != 1 && T[ e / 2 - 1 ] == 0 )
{
printf( "ERROR!\n" ) ;
exit( 1 ) ;
}
T[ e - 1 ] = value ;
}
return 0 ;
}
int Parent( SqBiTree T , int e )
{
if( e <= 0 || e > MAX_TREE_SIZE )
{
printf( "ERROR!\n" ) ;
exit( 1 ) ;
}
if( e == 1 )
{
printf( "The root does not have parent!\n" ) ;
exit( 1 ) ;
}
else if( e != 1 && T[ e - 1 ] != 0 )
{
return T[ e / 2 - 1 ] ;
}
return -1 ;
}
int LeftChild( SqBiTree T , int e )
{
if( e <= 0 || e > MAX_TREE_SIZE )
{
printf( "ERROR!\n" ) ;
exit( 1 ) ;
}
if( 2 * e <= MAX_TREE_SIZE && T[ 2 * e - 1] != 0 )
{
return T[ 2 * e - 1] ;
}
return -1 ;
}
int RightChild( SqBiTree T , int e )
{
if( 2 * e < MAX_TREE_SIZE && T[ 2 * e ] != 0 )
{
return T[ 2 * e ] ;
}
return -1 ;
}
int LeftSibling( SqBiTree T , int e )
{
if( e <= 0 || e > MAX_TREE_SIZE )
{
printf( "ERROR!\n" ) ;
exit( 1 ) ;
}
if( e == 1 )
{
printf( "The root does not have leftsibling!\n" ) ;
exit( 1 ) ;
}
if( e / 2 == ( e + 1 ) / 2 || ( ( e / 2 != ( e + 1 ) / 2 ) && T[ e - 1 ] == 0 ) )
{
printf( "ERROR!\n" ) ;
exit( 1 ) ;
}
return T[ e - 2 ] ;
}
int RightSibling( SqBiTree T , int e )
{
if( e <= 0 || e > MAX_TREE_SIZE )
{
printf( "ERROR!\n" ) ;
exit( 1 ) ;
}
if( e == 1 )
{
printf( "The root does not have leftsibling!\n" ) ;
exit( 1 ) ;
}
if( ( e / 2 != ( e + 1 ) / 2 ) || ( ( e / 2 == ( e + 1 ) / 2 ) && ( T[ e ] == 0 ) ) )
{
printf( "ERROR!\n" ) ;
exit( 1 ) ;
}
return T[ e ] ;
}
int Move( SqBiTree S , int i , SqBiTree T , int j )
{
if( S[ 2 * i + 1 ] != 0 )
{
Move( S , 2 * i + 1 , T , 2 * j + 1 ) ;
}
if( S[ 2 * i + 2 ] != 0 )
{
Move( S , 2 * i + 1 , T , 2 * j + 2 ) ;
}
T[j] = S[i] ;
S[i] = 0 ;
return 0 ;
}
int InsertChild( SqBiTree T , int e , int lor , SqBiTree C )
{
int k ;
if( e <= 0 || e > MAX_TREE_SIZE )
{
printf( "ERROR1!\n" ) ;
exit( 1 ) ;
}
if( lor != 0 && lor != 1 )
{
printf( "ERROR!\n" ) ;
exit( 1 ) ;
}
k = 2 * e - 1 + lor ;
if( T[ k ] != 0 )
{
Move( T , k , T , 2 * k + 2 ) ;
}
Move( C , 0 , T , k ) ;
return 0 ;
}
int DeleteChild( SqBiTree T , int e )
{
int i = MAX_TREE_SIZE - 1 ;
if( e <= 0 || e > MAX_TREE_SIZE )
{
printf( "ERROR!\n" ) ;
exit( 1 ) ;
}
while( T[i] == 0 )
{
i-- ;
}
int j ;
int k ;
for( j = 0 ; pow( 2, j ) * e <= i ; j++ )
{
for( k = 0 ; k < pow( 2 , j ) ; k++ )
{
T[ ( ( int ) pow(2 , j ) ) * e - 1 + k ] = 0 ;
}
}
return 0 ;
}
int PreOrderTraverse( SqBiTree T , int e )
{
if( T[ e - 1 ] != 0 )
{
printf( "%d " , T[ e - 1 ] ) ;
}
if( T[ 2 * e - 1 ] != 0 )
{
PreOrderTraverse( T , 2 * e ) ;
}
if( T[ 2 * e ] != 0 )
{
PreOrderTraverse( T , 2 * e + 1 ) ;
}
return 0 ;
}
int InOrderTraverse( SqBiTree T , int e )
{
if( T[ 2 * e - 1 ] != 0 )
{
InOrderTraverse( T , 2 * e ) ;
}
if( T[ e - 1 ] != 0 )
{
printf( "%d " , T[ e - 1 ] ) ;
}
if( T[ 2 * e ] != 0 )
{
InOrderTraverse( T , 2 * e + 1 ) ;
}
return 0 ;
}
int PostOrderTraverse( SqBiTree T , int e )
{
if( T[ 2 * e - 1 ] != 0 )
{
PostOrderTraverse( T , 2 * e ) ;
}
if( T[ 2 * e ] != 0 )
{
PostOrderTraverse( T , 2 * e + 1 ) ;
}
if( T[ e - 1 ] != 0 )
{
printf( "%d " , T[ e - 1 ] ) ;
}
return 0 ;
}
int PrintBiTree( SqBiTree T )
{
int i ;
for( i = 0 ; i < MAX_TREE_SIZE ; i++ )
{
if( T[i] != 0 )
{
printf( "%d " , T[i] ) ;
}
}
printf( "\n" ) ;
return 0 ;
}
主函数测试
#include "Streehead.h"
int main()
{
SqBiTree T ;
SqBiTree C = { 20 } ;
InitBiTree( T ) ;
CreateBiTree( T ) ;
PrintBiTree( T ) ;
/*int dea = BiTreeDepth( T ) ;
printf( "the death of the tree is %d\n" , dea ) ;
printf( "the root of the tree is %d\n" , Root( T ) ) ;
Assign( T , 9 , 20 ) ;
printf( "the value of e is %d\n" , Value( T , 9 ) ) ;
printf( "the parent of e is %d\n" , Parent( T , 10 ) ) ;
printf( "the leftchild of e is %d\n" , LeftChild( T , 5 ) ) ;
printf( "the rightchild of e is %d\n" , RightChild( T , 5 ) ) ;
printf( "the leftsibling of e is %d\n" , LeftSibling( T , 11 ) ) ;
printf( "the rightsibling of e is %d\n" , RightSibling( T , 10 ) ) ;*/
InsertChild( T , 2 , 0 , C ) ;
PrintBiTree( T ) ;
DeleteChild( T , 3 ) ;
PrintBiTree( T ) ;
printf( "前序\n") ;
PreOrderTraverse( T , 1 ) ;
printf( "\n中序\n" ) ;
InOrderTraverse( T , 1 ) ;
printf( "\n后序\n" ) ;
PostOrderTraverse( T , 1 ) ;
printf( "\n" ) ;
return 0;
}