用c写按先序序列构造一棵二叉链表表示的二叉树T并求二叉树中第一条最长的路径长度,并输出此路径上各结点。
时间: 2023-12-10 16:40:02 浏览: 79
求二叉树的一条最长路径
以下是按照先序序列构造二叉树的代码:
```c
#include<stdio.h>
#include<stdlib.h>
typedef struct TreeNode {
int value;
struct TreeNode *left;
struct TreeNode *right;
} TreeNode;
int index = 0; // 全局变量,记录当前遍历到先序序列的位置
// 根据先序序列构造二叉树
TreeNode* buildTree(int *preorder) {
int val = preorder[index++];
if (val == -1) { // -1表示当前节点为空
return NULL;
}
TreeNode *node = (TreeNode*)malloc(sizeof(TreeNode));
node->value = val;
node->left = buildTree(preorder);
node->right = buildTree(preorder);
return node;
}
// 计算二叉树中第一条最长的路径长度,并输出此路径上各结点
int maxDepth(TreeNode *node, TreeNode **path, int *len) {
if (node == NULL) {
return 0;
}
int leftDepth = maxDepth(node->left, path, len);
int rightDepth = maxDepth(node->right, path, len);
if (leftDepth + rightDepth > *len) {
*len = leftDepth + rightDepth;
path[0] = node;
if (node->left == NULL) {
path[1] = node->right;
} else if (node->right == NULL) {
path[1] = node->left;
} else {
path[1] = leftDepth > rightDepth ? node->left : node->right;
}
}
return leftDepth > rightDepth ? leftDepth+1 : rightDepth+1;
}
// 输出路径上各结点
void printPath(TreeNode **path, int len) {
for (int i = 0; i < len; i++) {
printf("%d ", path[i]->value);
}
printf("\n");
}
int main() {
int preorder[] = {1, 2, -1, -1, 3, -1, 4, 5, -1, -1, 6, -1, -1, 7, -1, -1};
TreeNode *root = buildTree(preorder);
TreeNode *path[2];
int len = 0;
maxDepth(root, path, &len);
printf("The length of the longest path in the binary tree is %d\n", len);
printf("The nodes on the longest path are: ");
printPath(path, 2);
return 0;
}
```
其中,-1表示当前节点为空。在调用 `maxDepth` 函数时,需要传入一个长度为2的 `TreeNode` 数组,用于记录最长路径上的两个节点。
阅读全文