두 갈래 나무 뒷차례 역법 (귀속과 비귀속)
#include
#include
#include<string.h>
#define MaxSize 30;
typedef int ElementType;
struct TreeNode {
ElementType Data;
struct TreeNode *Left;
struct TreeNode *Right;
struct TreeNode *Next;
};
typedef struct TreeNode *BinTree;
typedef struct TreeNode *Stack;
Stack pop(Stack S);
Stack CreateStack();
void push(Stack s, BinTree T);
BinTree CreateTreeNode();
BinTree CreateBinTree(int op[], int in[], int par_s);
void PostOrderTraversal(BinTree BT, ElementType root);
int main()
{
BinTree BT;
int N, i, e;
int index_j = 0, index_i = 0;
char action[5];
scanf("%d", &N);
int *in = (int*)malloc(sizeof(int)*N);
int *op = (int*)malloc(sizeof(int) * 2 * N);
getchar();
for (i = 0; i < N * 2; i++)
{
scanf("%s", action);
getchar();
if (strcmp(action, "Push") == 0)
{
scanf("%d", &e);
in[index_i++] = e;
op[i] = 1;
}
else
{
op[i] = 0;
}
}
BT=CreateBinTree(op, in, N);
PostOrderTraversal(BT, BT->Data);
}
Stack CreateStack()
{
Stack s;
s = (Stack)malloc(sizeof(struct TreeNode));
s->Next = NULL;
return s;
}
void push(Stack s, BinTree T)
{
if (s == NULL)
s = CreateStack();
T->Next = s->Next;
s->Next = T;
}
Stack pop(Stack S)
{
Stack temp = NULL,n;
if (!S || S->Next == NULL)
return NULL;
temp = S->Next;
S->Next = temp->Next;
n = temp;
temp = NULL;
return n;
}
BinTree CreateTreeNode()
{
BinTree Node = (BinTree)malloc(sizeof(struct TreeNode));
Node->Left = NULL;
Node->Right = NULL;
return Node;
}
BinTree CreateBinTree(int op[], int in[], int par_s)
{
BinTree root = NULL;
BinTree temp = NULL, Node = NULL;
Stack S;
int i = 0, n = 0;
if (par_s == 1)
{
root = CreateTreeNode();
root->Data = in[i];
return root;
}
else if (par_s == 0)
return NULL;
else
{
S = CreateStack();
root = CreateTreeNode();
root->Data = in[i];
Node = root;
temp = root;
push(S, temp);
n++;
for (i = 1; i < 2 * par_s; i++)
{
if (op[i])
{
Node = CreateTreeNode();
Node->Data = in[n];
push(S, Node);
if (temp->Left == NULL && op[i - 1])
temp->Left = Node;
else
temp->Right = Node;
temp = Node;
n++;
}
else
{
temp=pop(S);
}
}
}
free(S);
return root;
}
void PostOrderTraversal(BinTree BT,ElementType root)
{
if (BT->Left)
PostOrderTraversal(BT->Left, root);
if (BT->Right)
PostOrderTraversal(BT->Right, root);
if (BT->Data == root)
printf("%d", BT->Data);
else
printf("%d ", BT->Data);
}
비반복:
#include
#include
#include<string.h>
#define MaxSize 30;
typedef int ElementType;
struct TreeNode {
ElementType Data;
struct TreeNode *Left;
struct TreeNode *Right;
struct TreeNode *Next;
};
typedef struct TreeNode *BinTree;
typedef struct TreeNode *Stack;
Stack pop(Stack S);
Stack CreateStack();
void push(Stack s, BinTree T);
BinTree CreateTreeNode();
BinTree CreateBinTree(int op[], int in[], int par_s);
void PostOrderTraversal(BinTree T, ElementType root);
int main()
{
BinTree BT;
int N, i, e;
int index_j = 0, index_i = 0;
char action[5];
scanf_s("%d", &N);
int *in = (int*)malloc(sizeof(int)*N);
int *op = (int*)malloc(sizeof(int) * 2 * N);
getchar();
for (i = 0; i < N * 2; i++)
{
scanf_s("%s", action, 5);
getchar();
if (strcmp(action, "Push") == 0)
{
scanf_s("%d", &e);
in[index_i++] = e;
op[i] = 1;
}
else
op[i] = 0;
}
BT=CreateBinTree(op, in, N);
PostOrderTraversal(BT, BT->Data);
}
Stack CreateStack()
{
Stack s;
s = (Stack)malloc(sizeof(struct TreeNode));
s->Next = NULL;
return s;
}
void push(Stack s, BinTree T)
{
if (s == NULL)
s = CreateStack();
T->Next = s->Next;
s->Next = T;
}
Stack pop(Stack S)
{
Stack temp = NULL,n;
if (!S || S->Next == NULL)
return NULL;
temp = S->Next;
S->Next = temp->Next;
n = temp;
temp = NULL;
return n;
}
BinTree CreateTreeNode()
{
BinTree Node = (BinTree)malloc(sizeof(struct TreeNode));
Node->Left = NULL;
Node->Right = NULL;
return Node;
}
BinTree CreateBinTree(int op[], int in[], int par_s)
{
BinTree root = NULL;
BinTree temp = NULL, Node = NULL;
Stack S;
int i = 0, n = 0;
if (par_s == 1)
{
root = CreateTreeNode();
root->Data = in[i];
return root;
}
else if (par_s == 0)
return NULL;
else
{
S = CreateStack();
root = CreateTreeNode();
root->Data = in[i];
Node = root;
temp = root;
push(S, temp);
n++;
for (i = 1; i < 2 * par_s; i++)
{
if (op[i])
{
Node = CreateTreeNode();
Node->Data = in[n];
push(S, Node);
if (temp->Left == NULL && op[i - 1])
temp->Left = Node;
else
temp->Right = Node;
temp = Node;
n++;
}
else
temp=pop(S);
}
}
free(S);
return root;
}
void PostOrderTraversal(BinTree T,ElementType root)
{
BinTree temp = NULL;
Stack S = CreateStack();
while (T || S->Next) {
while (T) {
push(S, T);
T = T->Left;
}
if (S->Next)
{
T = pop(S);
push(S, T);
T = T->Right;
if (!T||T==temp)
{
temp = pop(S);
printf("%d", temp->Data);
if (temp->Data != root)
printf(" ");
T = NULL;
}
}
}
}
이곳은 창고로 나무를 구성하는 데 쓰인다.
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.