2

ツリーをジグザグに印刷したい。これが私のコードですが、実行されていません。誰かが間違いを指摘できますか？同じことを行うために2つのスタックを作成しました。そのうちの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の値を減らす必要があります。もう1つの間違いは、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 に答える