c - 使用双指针进行二叉树层次顺序遍历

Question

创建二叉树并不重要。我可以看到 LevelOrder 的打印结果，但它一直显示错误。如何修复更改并最大程度地减少更改？我得快点:(我认为 print DELETE() 是问题所在。我尝试了很多方法但无法修复它。我必须使用双指针、结构节点类型和队列。

#include <stdio.h>
#include <stdlib.h>

struct node **queue;
int front = 0, rear = -1, nodeCnt = 0;

struct node {
    struct node *llink;
    int data;
    struct node *rlink;
};

struct node *binaryTree(int a[], int left, int right) { //Creating Tree
    int mid;
    struct node *p = NULL;
    if (left <= right) {
        mid = (left + right) / 2;
        p = (struct node *)malloc(sizeof(struct node));
        nodeCnt++;
        printf("%d\n", a[mid]);
        p->data = a[mid];
        p->llink = binaryTree(a, left, mid - 1);
        p->rlink = binaryTree(a, mid + 1, right);
    }

    return p;
}

int ADD(struct node *data) { //Queue Add function
    if (rear == nodeCnt) {
        printf("Queue is full!\n");
        return -1;
    }

    queue[++rear] = data;
    return 0;
}

int DELETE() { //Queue Delete function
    struct node *node = NULL;
    if (front > rear) {
        printf("Queue is empty!");
        return -1;
    }

    node = queue[front++];
    return node;
}

int LevelOrder(struct node *str) { //Level order traversal function
    struct node *p = NULL; 
    if (str != NULL) {  
        ADD(str); //call ADD()
        while (1) {
            p = DELETE();
            if (str == NULL)
                break;
            printf("%d  ", p->data); //I think here and under this code is the problem
            if (p->llink != NULL)
                ADD(p->llink);
            if (p->rlink != NULL)
                ADD(p->rlink);
        }
    }
}

int main() {
    int a[] = { 3, 5, 7, 10, 15, 17, 20, 25, 28, 31, 33, 35 };
    struct node *root;
    int n = sizeof(a) / sizeof(int);
    int i;

    root = binaryTree(a, 0, n - 1); //call binaryTree function

    printf("\n");
    printf("\n");

    queue = (struct node **)malloc(sizeof(struct node *) *nodeCnt);
    //define queue with struct node type double pointer

    LevelOrder(root);


    return 0;
}

Answer 1

有 2 个问题:

1. 在 LevelOrder 函数中，您错误地使用了 (str==NULL) 而不是 (p == NULL)

2. DELETE() 的返回类型不正确

下面是工作代码:

#include <stdio.h>
#include <stdlib.h>

struct node **queue;
int front = 0, rear = -1, nodeCnt = 0;

struct node
{
  struct node *llink;
  int data;
  struct node *rlink;
};

struct node *
binaryTree (int a[], int left, int right)
{               //Creating Tree
  int mid;
  struct node *p = NULL;
  if (left <= right)
    {
      mid = (left + right) / 2;
      p = (struct node *) malloc (sizeof (struct node));
      nodeCnt++;
      printf ("%d\n", a[mid]);
      p->data = a[mid];
      p->llink = binaryTree (a, left, mid - 1);
      p->rlink = binaryTree (a, mid + 1, right);
    }

  return p;
}

int
ADD (struct node *data)
{               //Queue Add function
  if (rear == nodeCnt)
    {
      printf ("Queue is full!\n");
      return -1;
    }

  queue[++rear] = data;
  return 0;
}

struct node *
DELETE ()
{               //Queue Delete function
  struct node *node = NULL;
  if (front > rear)
    {
      printf ("Queue is empty!");
      return NULL;
    }

  node = queue[front++];
  return node;
}

void
LevelOrder (struct node *str)
{               //Level order traversal function
  struct node *p = NULL;
  if (str != NULL)
    {
      ADD (str);        //call ADD()
      while (1)
    {
      p = DELETE ();
      if (p == NULL)
        break;
      printf ("%d  ", p->data); //I think here and under this code is the problem
      if (p->llink != NULL)
        ADD (p->llink);
      if (p->rlink != NULL)
        ADD (p->rlink);
    }
    }
}

int
main ()
{
  int a[] = { 3, 5, 7, 10, 15, 17, 20, 25, 28, 31, 33, 35 };
  struct node *root;
  int n = sizeof (a) / sizeof (int);
  int i;

  root = binaryTree (a, 0, n - 1);  //call binaryTree function

  printf ("\n");
  printf ("\n");

  queue = (struct node **) malloc (sizeof (struct node *) * nodeCnt);
  //define queue with struct node type double pointer

  LevelOrder (root);


  return 0;
}

输出:

17
7
3
5
10
15
28
20
25
33
31
35


17  7  28  3  10  20  33  5  15  25  31  35  Queue is empty!

此外，您需要完全删除二叉树。下面是删除完整二叉树的函数:

void
deletetree (struct node *root)
{
  if (root == NULL)
    return;


  deletetree (root->llink);
  deletetree (root->rlink);

  printf ("\n Deleting node: %d", root->data);
  free (root);
  root = NULL;
}

在主函数末尾需要添加:

  deletetree (root);
  free (queue);