Printing the sequence in breadth first order using

问题:

Given a process tree

             A
           /   \
          /     \
         B       C
        / \     / \
       D   E   F   G

I am asked to print the sequence in BFS order, i.e A-B-C-D-E-F-G using fork() system call, where each node represents a process with the same parent-child construct as shown in tree(i.e A is parent of B and C, B is parent of D and E like that).

I figured out this solution, but I really don't understand how to make it print recursively.

static int count;
char *msg[] = {"A", "B", "C", "D", "E", "F", "G"};
main(){
  if(!fork()){ //Child 1
    printf("%s\t\t%d\t\t%d\n", msg[count++], (int)getpid(), (int)getppid());
  }
  else{
    if(!fork()){ //Child 2
        printf("%s\t\t%d\t\t%d\n", msg[count++], (int)getpid(), (int)getppid());
    }
  } 
}

This logic prints only A-B-C, How to make it recursive so that it will print till G? Please help. Thanks.

回答1:

Following code does what you need but does not guarantee which leaf will be printed first (print order of the same level).

#include <stdio.h>
#include <sys/types.h>
#include <unistd.h>
#include <sys/wait.h>
#include <linux/wait.h>

typedef struct node {
  char data;
  struct node *left;
  struct node *right;
} node;

void pretty_print(node *nodes[], int size)
{
  int fork_cnt = 0;

  for (int i=0; i < size; i++) {
    if (fork() == 0) {
      // Child path.
      printf("%c (pid: %d, parent: %d)\n", nodes[i]->data, (int)getpid(), (int)getppid());
      node *children_nodes[256];
      int children_sizes = 0;
      if (nodes[i]->left)
    children_nodes[children_sizes++] = nodes[i]->left;
      if (nodes[i]->right)
    children_nodes[children_sizes++] = nodes[i]->right;
      if (children_sizes) {
    if (fork() == 0) {
      pretty_print(children_nodes, children_sizes);
      return;
    }
      }
      return;
    } else {
      // Parent path.
      fork_cnt++;
    }
  }

  for (int i=0; i < fork_cnt; i++) {
    // wait all children.
    int status;
    wait(&status);
  }
}

int main(void) 
{
  node g = {'G', NULL, NULL};
  node f = {'F', NULL, NULL};
  node e = {'E', NULL, NULL};
  node d = {'D', NULL, NULL};
  node b = {'B', &d, &e};
  node c = {'C', &f, &g};
  node a = {'A', &b, &c};

  node *root[1] = {&a};
  pretty_print(root, 1);
  return 0;
}