#include <stdio.h>
#include <stdlib.h>
#define INIT_SIZE 15
#define Add
5
typedef struct BiTNode
{
int data;
int flag;//标志位 1表示数的最低位
0表示不是数据的最低位
struct BiTNode *lchild, *rchild;
}*BiTree;
typedef struct BNode
{
BiTree *top;
BiTree *base;
int stack_size;
}BiTree_Stack;
typedef struct
{
int *top;
int *base;
int stack_size;
}Sq_Stack;
////////数栈的基本函数////////
void Init_SqStack( Sq_Stack &S )
{
S.base = (int *) malloc (INIT_SIZE*sizeof(int));
if( !S.base )
exit(0);
S.top = S.base;
S.stack_size = INIT_SIZE;
}
void Pop_SqStack( Sq_Stack &S, int &temp )
{
if( S.top == S.base )
return;
temp = *--S.top;
}
void Push_SqStack( Sq_Stack &S, int temp )
{
if( S.top - S.base >= S.stack_size )
{
S.base = (int *) realloc (S.base, (S.stack_size+Add)*sizeof(int));
S.top = S.base + S.stack_size;
S.stack_size += Add;
}
*S.top++ = temp;
}
void Getop_SqStack( Sq_Stack S, int &temp )
{
if( S.top == S.base )
return;
temp = *(S.top - 1);
}
int Empty_SqStack( Sq_Stack S )
{
if( S.top == S.base )
return 1;
return 0;
}
void Destroy_SqStack( Sq_Stack &S )
{
if( S.base )
free( S.base );
S.top = S.base = NULL;
S.stack_size = 0;
}
///////树栈的基本函数/////////
void Init_BStack( BiTree_Stack &S )
{
S.base = (BiTree *) malloc (INIT_SIZE*sizeof(struct BiTNode));
if( !S.base )
exit(0);
S.top = S.base;
S.stack_size = INIT_SIZE;
}
void Pop_BStack( BiTree_Stack &S, BiTree &temp )
{
if( S.top == S.base )
return;
temp = *--S.top;
}
void Push_BStack( BiTree_Stack &S, BiTree temp )
{
if( S.top - S.base >= S.stack_size )
{
S.base = (BiTree *) realloc (S.base, (S.stack_size+Add)*sizeof(struct BiTNode));
S.top = S.base + S.stack_size;
S.stack_size += Add;
}
*S.top++ = temp;
}
int Getop_BStack( BiTree_Stack S, BiTree &temp )
{
if( S.top == S.base )
return 0;
temp = *(S.top - 1);
return 1;
}
int Empty_BStack( BiTree_Stack S )
{
if( S.top == S.base )
return 1;
return 0;
}
void Destroy_BStack( BiTree_Stack &S )
{
if( S.base )
free( S.base );
S.top = S.base = NULL;
S.stack_size = 0;
}
///////////辅助函数////////////
//十进制转换成二进制
void D_TO_B( Sq_Stack &S, int temp )
{
while( temp )
{
Push_SqStack( S, temp%2 );
temp = temp/2;
}
}
//二进制转换成十进制
void B_TO_D( Sq_Stack S, int &temp )
{
temp = 0;
int e = 0;
while( !Empty_SqStack(S) )
{
Pop_SqStack( S, e );
temp = temp*2 + e;
}
}
void Create_BiTree( BiTree &T, Sq_Stack &S )
{
if( !Empty_SqStack(S) )
{
int temp;
Pop_SqStack( S, temp );
if( !T )
{
T = (BiTree) malloc (sizeof(struct BiTNode));
T->data = temp;
T->flag = 0;
T->lchild = T->rchild = NULL;
if( !Empty_SqStack(S) )
{
Getop_SqStack( S, temp );
if( temp == 0 )
Create_BiTree( T->lchild, S );
else
Create_BiTree( T->rchild, S );
}
else
T->flag = 1;
}
else if( T->data == temp && Empty_SqStack(S) )
T->flag = 1;
else if( T->data == temp && !Empty_SqStack(S) )
{
Getop_SqStack( S, temp );
if( temp == 0 )
Create_BiTree( T->lchild, S );
else
Create_BiTree( T->rchild, S );
}
}
}
void printf_sqstack( Sq_Stack S )
{
int temp;
while( S.base != S.top )
{
Pop_SqStack( S, temp );
printf("%d ", temp);
}
printf("\n");
}
//
int Counter( BiTree_Stack Sa, BiTree_Stack Sb )
{
Sq_Stack S_temp;
BiTree Sa_temp, Sb_temp;
int total = 0;
Init_SqStack( S_temp );
while( !Empty_BStack( Sa ) || !Empty_BStack( Sb ) )
{
if( !Empty_BStack( Sa ) && !Empty_BStack( Sb ) )
{
Pop_BStack( Sa, Sa_temp );
Pop_BStack( Sb, Sb_temp );
if( Sa_temp->data == Sb_temp->data )
Push_SqStack( S_temp, 0 );
else
Push_SqStack( S_temp, 1 );
}
else if( !Empty_BStack( Sa ) && Empty_BStack( Sb ) )
{
Pop_BStack( Sa, Sa_temp );
Push_SqStack( S_temp, Sa_temp->data );
}
else if( Empty_BStack( Sa ) && !Empty_BStack( Sb ) )
{
Pop_BStack( Sb, Sb_temp );
Push_SqStack( S_temp, Sb_temp->data );
}
}
printf_sqstack( S_temp );
B_TO_D( S_temp, total );
return total;
}
void printf_stack( BiTree_Stack S )
{
BiTree temp;
while( S.base != S.top )
{
Pop_BStack( S, temp );
printf("%d ", temp->data);
}
printf("\n");
}
//计算最大值
int Total( BiTree T )
{//采用后序遍历
int sum, max=0;
BiTree_Stack Sa, Sb;
BiTree Sa_temp_parent, Sa_temp = NULL, Sb_temp_parent, Sb_temp = NULL;
Init_BStack( Sa );
Push_BStack( Sa, T );
while( !Empty_BStack( Sa ) )
{
while( Getop_BStack( Sa, Sa_temp ) && Sa_temp )
Push_BStack( Sa, Sa_temp->lchild );
Pop_BStack( Sa, Sa_temp );
if( !Empty_BStack( Sa ) )
{
Getop_BStack( Sa, Sa_temp );
Push_BStack( Sa, Sa_temp->rchild );
Getop_BStack( Sa, Sa_temp );
if( !Sa_temp )
{
Pop_BStack( Sa, Sa_temp );
Getop_BStack( Sa, Sa_temp_parent );
while( Sa_temp_parent->rchild == Sa_temp )
{
Getop_BStack( Sa, Sa_temp );
if( Sa_temp->flag == 1 )
{
Init_BStack( Sb );
Push_BStack( Sb, T );
while( !Empty_BStack( Sb ) )
{
while( Getop_BStack( Sb, Sb_temp ) && Sb_temp )
Push_BStack( Sb, Sb_temp->lchild );
Pop_BStack( Sb, Sb_temp );
if( !Empty_BStack( Sb ) )
{
Getop_BStack( Sb, Sb_temp );
Push_BStack( Sb, Sb_temp->rchild );
Getop_BStack( Sb, Sb_temp );
if( !Sb_temp )
{
Pop_BStack( Sb, Sb_temp );
Getop_BStack( Sb, Sb_temp_parent );
while( Sb_temp_parent->rchild == Sb_temp )
{
Getop_BStack( Sb, Sb_temp );
if( Sb_temp->flag == 1 )
{
printf_stack( Sa );
printf_stack( Sb );
sum = Counter( Sa, Sb );
printf("%d\n", sum);
putchar('\n');
if( sum > max )
max = sum;
}
Pop_BStack( Sb, Sb_temp );
Getop_BStack( Sb, Sb_temp_parent );
}
Push_BStack( Sb, NULL );
}
}
}
Destroy_BStack( Sb );
}
Pop_BStack( Sa, Sa_temp );
Getop_BStack( Sa, Sa_temp_parent );
}
Push_BStack( Sa, NULL );
}
}
}
return max;
}
void print( BiTree T )
{
if(T)
{
print(T->lchild);
print(T->rchild);
printf("%d ", T->data);
}
}
int main()
{
int n, value;
Sq_Stack S;
BiTree T = NULL;
Init_SqStack( S );
printf("输入数的个数:");
scanf("%d", &n );
while( n-- )
{
printf("输入数的值:");
scanf("%d", &value);
Init_SqStack( S );
D_TO_B( S, value );
Create_BiTree( T, S );
Destroy_SqStack( S );
}
print( T );
printf("\n");
printf("\n");
printf("异或的最大值为:%d\n", Total(T) );
return 0;
}
