이 진 트 리 의 옮 겨 다 니 기 (재 귀 법, 스 택 법)
9257 단어 데이터 구조
/*
*/
#include
#include
#define Ele char
typedef struct BinTree
{
Ele data;
struct BinTree * leftChild;
struct BinTree * rightChild;
}BinTree;
#include "Stack.c"
#include "LinkQueue.c"
BinTree * NewTree(int level, int nowLevel);
void TraversalByRecursion(BinTree * T, LinkQueue *LQ, int order) ; // ( )
void TraversalByStack(BinTree * T, int order) ;
int main ()
{
BinTree * T = NewTree(10, 1);
LinkQueue *LQ = NewQueue();
printf("
( ) ");
TraversalByRecursion(T,LQ , 0);
printf("
( ) ");
TraversalByRecursion(T,LQ , 1);
printf("
( ) ");
TraversalByRecursion(T,LQ , 2);
printf("
( ) ");
TraversalByRecursion(T,LQ , 3);
printf("
( ) ");
TraversalByStack(T, 0);
printf("
( ) ");
TraversalByStack(T, 1);
printf("
( ) ");
TraversalByStack(T, 3);
return 0;
}
//
BinTree * NewTree(int level, int nowLevel)
{
if(nowLevel > level)
{
return NULL;
}
BinTree * T = (BinTree*)malloc(sizeof(BinTree));
T->data = nowLevel + 'A';
T->leftChild = NewTree(10, nowLevel * 2);
T->rightChild = NewTree(10, nowLevel * 2 + 1);
return T;
}
// ( ) order = 0 ; order = 1 ; order = 2 ; oeder = 3
void TraversalByRecursion(BinTree * T, LinkQueue *LQ,int order)
{
if(order == 0)
{
printf("%c ", T->data);
if(T->leftChild != NULL)
TraversalByRecursion(T->leftChild, LQ, order);
if(T->rightChild != NULL)
TraversalByRecursion(T->rightChild, LQ, order);
}
if(order == 1)
{
if(T->leftChild != NULL)
TraversalByRecursion(T->leftChild, LQ, order);
printf("%c ", T->data);
if(T->rightChild != NULL)
TraversalByRecursion(T->rightChild, LQ, order);
}
if(order == 2)
{
if(T->leftChild != NULL)
TraversalByRecursion(T->leftChild, LQ, order);
if(T->rightChild != NULL)
TraversalByRecursion(T->rightChild, LQ, order);
printf("%c ", T->data);
}
if(order == 3)
{
// :1 ;2 ;3
printf("%c ", T->data);//1 ;
if(T->leftChild != NULL)
PushQueue(LQ, T->leftChild);// 2 ;
if(T->rightChild != NULL)
PushQueue(LQ, T->rightChild);// 2 ;
if(!IsEmptyQueue(LQ))
TraversalByRecursion(PopQueue(LQ), LQ, order);//3
}
}
// ( ) order = 0 ; order = 1 ; order = 2 ; oeder = 3
void TraversalByStack(BinTree * T, int order)
{
BinTree *temp;
int rightChild = 0;
Stack* S = NewStack();
/*
1 ;
2 ,
3
*/
if(order == 1)
{
while(T != NULL)
{
//1 ;
while(T != NULL)
{
Push(S,T);
T = T->leftChild;
}
//2 ,
do
{
T = Pop(S);
printf("%c ", T->data);/
T = T->rightChild;
}
while(T == NULL && !IsEmpty(S));
}
}
/*
1
2 ;
3
*/
if(order == 0)
{
while(T != NULL)
{
//1 ;
while(T != NULL)
{
if(T->leftChild == NULL && T->rightChild == NULL)
{
printf("%c ", T->data);/
}
Push(S,T);
T = T->leftChild;
}
//2 ,
do
{
T = Pop(S);
T = T->rightChild;
}
while(T == NULL && !IsEmpty(S));
}
}
/*
:
while( )
;
;
;
*/
LinkQueue *LQ = NewQueue();
if(order == 3)
{
PushQueue(LQ, T);//
while(!IsEmptyQueue(LQ))
{
T = PopQueue(LQ);//1
printf("%c ", T->data);//2
if(T->leftChild != NULL)
PushQueue(LQ, T->leftChild);//3
if(T->rightChild != NULL)
PushQueue(LQ, T->rightChild);//3
}
}
}
Stack.c
/*
- (C )
: 、 、 、 、
*/
#include
#include
#define Element BinTree*
typedef struct _Stack
{
Element data;
struct _Stack* next;
} Stack;
Stack * NewStack();//
int Push(Stack * S, Element value) ;//
Element Pop(Stack * S);//
void Traserval(Stack *S);//
int IsEmpty(Stack * S);//
//int main()
//{
// int i = 0;
// Stack* S = NewStack();
// for(i = 0; i < 20; i++)
// {
// Push(S, i * 3);//
// }
// Traserval(S);
// for(i = 0; i < 25;i++)
// {
// printf(" :%d ", IsEmpty(S));
// printf(" : %d
", Pop(S));
// }
//
// return 0;
//}
//
Stack * NewStack()
{
Stack* S = (Stack*)malloc(sizeof(Stack));
S->next = NULL;
S->data = 0;
return S;
}
//
int Push(Stack * S, Element value)
{
Stack* temp = NewStack();
if(temp == NULL)
{
return -1;
}
temp->data = value;
temp->next = S->next;
S->next = temp;
return 1;
}
//
Element Pop(Stack * S)
{
Stack * temp;
Element data;
if(S->next == NULL)
{
return data;
}
temp = S->next;
data = temp->data;
S->next = temp->next;
free(temp);
return data;
}
//
int IsEmpty(Stack * S)
{
if(S->next == NULL)
{
return 1;
}
return 0;
}
//
void Traserval(Stack *S)
{
printf("
");
while(S->next != NULL)
{
printf("%d
", S->next->data);
S = S->next;
}
}
LinkQueue.c
/*
( )
: 、 、 、 、
*/
#include
#include
#define Ele_3 BinTree*
typedef struct LinkQueue
{
Ele_3 data;
struct LinkQueue* next;
}LinkQueue;
LinkQueue* NewQueue();
void PushQueue(LinkQueue* LQ, Ele_3 data);
Ele_3 PopQueue(LinkQueue * LQ);
void TraservalQueue(LinkQueue* LQ);
int IsEmptyQueue(LinkQueue * LQ);
//
//int main()
//{
// int i;
// LinkQueue *LQ = NewQueue();
// for(i = 0; i < 20; i ++)
// {
// Push(LQ, i * 4);
// }
// for(i = 0; i < 25; i ++)
// {
// printf(" %d
",IsEmpty(LQ));
// Pop(LQ);
// Traserval(LQ);
// }
// return 0;
//}
//
LinkQueue* NewQueue()
{
LinkQueue* LQ = (LinkQueue*)malloc(sizeof(LinkQueue));
LQ->data = 0;
LQ->next = NULL;
}
//
void PushQueue(LinkQueue* LQ, Ele_3 data)
{
int i;
LinkQueue* temp = NewQueue();
temp->data = data;
while(LQ->next != NULL)
{
LQ = LQ->next;
}
LQ->next = temp;
}
//
Ele_3 PopQueue(LinkQueue * LQ)
{
LinkQueue * temp;
Ele_3 data;
if(LQ->next == NULL)
{
return data;
}
temp = LQ->next;
data = temp->data;
LQ->next = temp->next;
free(temp);
return data;
}
//
int IsEmptyQueue(LinkQueue * LQ)
{
if(LQ->next == NULL)
{
return 1;
}
else
{
return 0;
}
}
//
void TraservalQueue(LinkQueue* LQ)
{
printf("
");
while(LQ->next != NULL)
{
printf("%d
", LQ->next->data);
LQ = LQ->next;
}
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
정수 반전Udemy 에서 공부 한 것을 중얼거린다 Chapter3【Integer Reversal】 (예) 문자열로 숫자를 반전 (toString, split, reverse, join) 인수의 수치 (n)가 0보다 위 또는 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.