我想以之字形顺序打印树。这是我的代码,但它没有运行。有人可以指出错误吗? 我创建了两个堆栈来执行相同的操作,当其中两个为空时,我的算法终止,如果其中任何一个包含一些节点,则打印这些节点并将其子节点推送到另一个堆栈中。这个过程一直持续到两个堆栈都变空为止。
#include<stdio.h>
#define MAX_SIZE 100
struct TreeNode{
int value;
struct TreeNode *left;
struct TreeNode *right;
};
struct TreeNode stackA[MAX_SIZE];
struct TreeNode stackB[MAX_SIZE];
int topA = 0;
int topB = 0;
void push(struct TreeNode stack[], struct TreeNode *node, int *top){
if(*top > MAX_SIZE){
printf("stack is full\n");
}
else{
stack[*top] = *node;
*top = *top +1;
}
return;
}
struct TreeNode* pop(struct TreeNode stack[], int *top){
if(*top == 0){
printf("stack is empty\n");
return NULL;
}
else{
struct TreeNode *tmp = stack + *top;
*top = *top - 1;
return tmp;
}
}
int isEmpty(int *top){
if(*top == 0){
return 1;
}
return 0;
}
void printZigZag(struct TreeNode* root){
push(stackA, root,&topA);
printf("%d\n", topA);
while(!isEmpty(&topA) || !isEmpty(&topB)){
while(!isEmpty(&topA)){
struct TreeNode* temp = pop(stackA,&topA);
printf("%d", temp->value);
if(temp->left) push(stackB,temp->left,&topB);
if(temp->right) push(stackB,temp->right,&topB);
printf("%d %d",topA,topB);
return;
}
while(!isEmpty(&topB)){
struct TreeNode *temp = pop(stackB,&topB);
printf("%d", temp->value);
if(temp->right) push(stackA,temp->right,&topA);
if(temp->left) push(stackA,temp->left,&topB);
}
}
}
int main(){
struct TreeNode* root = (struct TreeNode *)malloc(sizeof(struct TreeNode));
root->value = 5;
root->left = NULL;
root->right = NULL;
struct TreeNode* first = (struct TreeNode *)malloc(sizeof(struct TreeNode));
first->value = 15;
first->left = NULL;
first->right = NULL;
root->left = first;
struct TreeNode* second = (struct TreeNode *)malloc(sizeof(struct TreeNode));
second->value = 235;
second->left = NULL;
second->right = NULL;
root->right = second;
struct TreeNode *third = (struct TreeNode *)malloc(sizeof(struct TreeNode));
third->value = 45;
third->left = NULL;
third->right = NULL;
first->left = third;
struct TreeNode *fourth = (struct TreeNode *)malloc(sizeof(struct TreeNode));
fourth->value = 55;
fourth->left = NULL;
fourth->right = NULL;
first->right = fourth;
printZigZag(root);
system("pause");
return 0;
}
最佳答案
我已经检查了你的代码。你犯的最大错误是错误地实现了Pop功能。 *pop 的值应该在您获得堆栈的顶部值之前减少。另一个错误是 if(temp->left) push(stackA,temp->left,&topB) 应该更改为 if(temp->left) push(stackA,temp->left,&topA)。下面是代码工作,我改变了一些小地方以适应 C++。
#include<cstdio>
#define MAX_SIZE 100
struct TreeNode{
int value;
struct TreeNode *left;
struct TreeNode *right;
};
struct TreeNode stackA[MAX_SIZE];
struct TreeNode stackB[MAX_SIZE];
int topA = 0;
int topB = 0;
void push(struct TreeNode stack[], struct TreeNode *node, int *top){
if(*top > MAX_SIZE){
printf("stack is full\n");
}
else{
stack[*top] = *node;
*top = *top +1;
}
return;
}
struct TreeNode* pop(struct TreeNode stack[], int *top){
if(*top == 0){
printf("stack is empty\n");
return NULL;
}
else{
*top = *top - 1;
struct TreeNode *tmp = stack +*top;
return tmp;
}
}
int isEmpty(int *top){
if(*top == 0){
return 1;
}
return 0;
}
void printZigZag(struct TreeNode* root){
push(stackA, root,&topA);
while(!isEmpty(&topA) || !isEmpty(&topB)){
while(!isEmpty(&topA)){
struct TreeNode* temp = pop(stackA,&topA);
printf("%d\n", temp->value);
if(temp->left) push(stackB,temp->left,&topB);
if(temp->right) push(stackB,temp->right,&topB);
}
while(!isEmpty(&topB)){
struct TreeNode *temp = pop(stackB,&topB);
printf("%d\n", temp->value);
if(temp->right) push(stackA,temp->right,&topA);
if(temp->left) push(stackA,temp->left,&topA);
}
}
}
int main(){
struct TreeNode* root = new TreeNode();
root->value = 5;
root->left = NULL;
root->right = NULL;
struct TreeNode* first =new TreeNode();
first->value = 15;
first->left = NULL;
first->right = NULL;
root->left = first;
struct TreeNode* second = new TreeNode();
second->value = 235;
second->left = NULL;
second->right = NULL;
root->right = second;
struct TreeNode *third = new TreeNode();
third->value = 45;
third->left = NULL;
third->right = NULL;
first->left = third;
struct TreeNode *fourth = new TreeNode();
fourth->value = 55;
fourth->left = NULL;
fourth->right = NULL;
first->right = fourth;
printZigZag(root);
return 0;
}
希望对您有所帮助!
关于c - 之字形树打印,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/13322743/