2

我想以之字形顺序打印树。这是我的代码，但它没有运行。有人可以指出错误吗？我创建了两个堆栈来做同样的事情，当其中两个为空时，我的算法终止，如果其中任何一个包含一些节点，则打印这些节点并将其子节点推入另一个堆栈。这个过程一直持续到两个堆栈都变空。

#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;
}
4

1 回答 1

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;
}

希望能帮助到你！

于 2012-11-10T18:23:09.747 回答