以二叉链表作为二叉树的存储结构。设计算法求二叉树中第一条最长的路径长度，并输出此路径上各结点的值。要求：（1）给出二叉链表中结点类型BTNode定义；（2）给出算法的基本设计思想；（3）根据设计思想，采用C或者C++语言描述算法

1. BTNode的定义：

typedef struct BTNode{
    char data; //结点数据
    struct BTNode *lchild, *rchild; //左右孩子指针
}BTNode, *BiTree;

2. 基本设计思想

我们从根节点开始，遍历二叉树，对于每个节点，我们计算从该节点向下的最长路径长度，然后将其与从左右子节点向下的最长路径长度相加，得到从该节点向上的最长路径长度。如果该路径长度大于当前最长路径长度，则更新最长路径长度，并更新最长路径上的节点。

3. 算法描述

int maxPathLength = 0; //最长路径长度
BTNode* maxPathNode = NULL; //最长路径上的节点
int getLongestPath(BTNode* root) {
    if (root == NULL) {
        return 0;
    }
    int leftPath = getLongestPath(root->lchild); //向左的最长路径
    int rightPath = getLongestPath(root->rchild); //向右的最长路径
    int curPathLength = leftPath + rightPath + 1; //从该节点向上的最长路径
    if (curPathLength > maxPathLength) { //如果当前路径长度大于最长路径长度，则更新
        maxPathLength = curPathLength;
        maxPathNode = root;
    }
    return max(leftPath, rightPath) + 1; //返回从该节点向下的最长路径
}

void printPath(BTNode* root) { //输出最长路径上的节点
    if (root == NULL) {
        return;
    }
    printPath(root->lchild);
    printf("%c ", root->data);
    printPath(root->rchild);
}

void getAndPrintLongestPath(BTNode* root) { //获取最长路径并输出
    getLongestPath(root);
    printf("The longest path length is %d\n", maxPathLength);
    printf("The nodes on the longest path are: ");
    printPath(maxPathNode);
}

4. 完整代码（C++）

#include <iostream>
using namespace std;

typedef struct BTNode{
    char data;
    struct BTNode *lchild, *rchild;
}BTNode, *BiTree;

int maxPathLength = 0;
BTNode* maxPathNode = NULL;

int getLongestPath(BTNode* root) {
    if (root == NULL) {
        return 0;
    }
    int leftPath = getLongestPath(root->lchild);
    int rightPath = getLongestPath(root->rchild);
    int curPathLength = leftPath + rightPath + 1;
    if (curPathLength > maxPathLength) {
        maxPathLength = curPathLength;
        maxPathNode = root;
    }
    return max(leftPath, rightPath) + 1;
}

void printPath(BTNode* root) {
    if (root == NULL) {
        return;
    }
    printPath(root->lchild);
    cout << root->data << " ";
    printPath(root->rchild);
}

void getAndPrintLongestPath(BTNode* root) {
    getLongestPath(root);
    cout << "The longest path length is " << maxPathLength << endl;
    cout << "The nodes on the longest path are: ";
    printPath(maxPathNode);
}

int main() {
    BiTree root = new BTNode{'A', NULL, NULL};
    root->lchild = new BTNode{'B', NULL, NULL};
    root->rchild = new BTNode{'C', NULL, NULL};
    root->lchild->lchild = new BTNode{'D', NULL, NULL};
    root->rchild->lchild = new BTNode{'E', NULL, NULL};
    root->rchild->rchild = new BTNode{'F', NULL, NULL};
    root->rchild->lchild->rchild = new BTNode{'G', NULL, NULL};
    getAndPrintLongestPath(root);
    return 0;
}