从根结点到叶子结点的路径

以下是从根结点到叶子结点的路径的实现方法：

1. 采用先序遍历方法输出所有从叶子结点到根结点的逆路径

static void all_path1(BTNode *b, ElemType path[], int path_len) {
  int i;
  if (b != NULL) {
    path[path_len] = b->data;
    path_len++;
    if (b->lchild == NULL && b->rchild == NULL) {
      for (i = path_len - 1; i >= 0; i--) {
        printf("%c ", path[i]);
      }
      printf("\n");
    } else {
      all_path1(b->lchild, path, path_len);
      all_path1(b->rchild, path, path_len);
    }
  }
}

2. 采用先序遍历方法输出第一条最长的逆路径

static void longest_path(BTNode *b, ElemType path[], int path_len, int *max_len, ElemType longest_path[]) {
  int i;
  if (b != NULL) {
    path[path_len] = b->data;
    path_len++;
    if (b->lchild == NULL && b->rchild == NULL) {
      if (path_len > *max_len) {
        *max_len = path_len;
        for (i = path_len - 1; i >= 0; i--) {
          longest_path[i] = path[i];
        }
      }
    } else {
      longest_path(b->lchild, path, path_len, max_len, longest_path);
      longest_path(b->rchild, path, path_len, max_len, longest_path);
    }
  }
}

3. 采用后序非递归遍历方法输出所有从叶子结点到根结点的逆路径

static void all_path2(BTNode *b) {
  BTNode *p;
  int flag;
  BTNode *stack[MaxSize];
  int top = -1;
  BTNode *pre = NULL;
  p = b;
  while (p != NULL || top != -1) {
    if (p != NULL) {
      stack[++top] = p;
      p = p->lchild;
    } else {
      p = stack[top];
      if (p->rchild != NULL && p->rchild != pre) {
        p = p->rchild;
        stack[++top] = p;
        p = p->lchild;
      } else {
        if (p->lchild == NULL && p->rchild == NULL) {
          for (int i = top; i >= 0; i--) {
            printf("%c ", stack[i]->data);
          }
          printf("\n");
        }
        pre = p;
        top--;
        p = NULL;
      }
    }
  }
}

4. 采用层次遍历方法输出所有从叶子结点到根结点的逆路径

static void all_path3(BTNode *b) {
  BTNode *p;
  BTNode *queue[MaxSize];
  int front = 0, rear = 0;
  int flag;
  queue[rear] = b;
  rear = (rear + 1) % MaxSize;
  while (front != rear) {
    p = queue[front];
    front = (front + 1) % MaxSize;
    if (p->lchild == NULL && p->rchild == NULL) {
      while (p != NULL) {
        printf("%c ", p->data);
        p = p->parent;
      }
      printf("\n");
    }
    if (p->lchild != NULL) {
      queue[rear] = p->lchild;
      rear = (rear + 1) % MaxSize;
    }
    if (p->rchild != NULL) {
      queue[rear] = p->rchild;
      rear = (rear + 1) % MaxSize;
    }
  }
}