以二叉链表作为二叉树的存储结构。设计算法求二叉树中第一条最长的路径长度,并输出此路径上各结点的值。要求:(1)给出二叉链表中结点类型BTNode定义;(2)给出算法的基本设计思想;(3)根据设计思想,采用C或者C++语言描述算法。
时间: 2024-02-01 18:13:38 浏览: 19
(1) 二叉链表中结点类型BTNode定义:
```
struct BTNode{
int data;
BTNode *lchild,*rchild;
};
```
(2) 算法的基本设计思想:
- 如果二叉树为空,直接返回0;
- 如果二叉树只有根节点,返回1;
- 递归求左子树和右子树的最大深度;
- 比较左子树最大深度、右子树最大深度和左子树的最长路径加上右子树的最长路径的和,取其中的最大值;
- 如果最大值为左子树的最长路径加上右子树的最长路径的和,则输出左子树的根节点和右子树的根节点;
- 否则,如果左子树的最大深度大于等于右子树的最大深度,输出左子树的根节点;
- 否则,输出右子树的根节点。
(3) C++实现代码:
```cpp
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
struct BTNode{
int data;
BTNode *lchild,*rchild;
};
int maxDepth(BTNode *root, vector<int> &path){
if(root == NULL) return 0; // 空树的深度为0
if(root->lchild == NULL && root->rchild == NULL){ // 只有根节点的树的深度为1
path.push_back(root->data);
return 1;
}
int leftDepth = maxDepth(root->lchild, path); // 求左子树最大深度
int rightDepth = maxDepth(root->rchild, path); // 求右子树最大深度
int curMax = leftDepth + rightDepth; // 当前节点的左子树最长路径加上右子树最长路径的和
if(curMax > max(leftDepth, rightDepth)){ // 如果当前节点的左子树最长路径加上右子树最长路径的和大于左子树最大深度和右子树最大深度
path.push_back(root->data); // 将当前节点加入路径
if(leftDepth >= rightDepth) return curMax; // 如果左子树的最大深度大于等于右子树的最大深度,返回左子树的最大深度
else return curMax; // 否则返回右子树的最大深度
}
else{ // 如果当前节点的左子树最长路径加上右子树最长路径的和小于等于左子树最大深度和右子树最大深度
if(leftDepth >= rightDepth){ // 如果左子树的最大深度大于等于右子树的最大深度
path.push_back(root->lchild->data); // 将左子树的根节点加入路径
return leftDepth; // 返回左子树的最大深度
}
else{ // 否则
path.push_back(root->rchild->data); // 将右子树的根节点加入路径
return rightDepth; // 返回右子树的最大深度
}
}
}
int main(){
BTNode *root = new BTNode{1, NULL, NULL};
root->lchild = new BTNode{2, NULL, NULL};
root->rchild = new BTNode{3, NULL, NULL};
root->lchild->lchild = new BTNode{4, NULL, NULL};
root->lchild->rchild = new BTNode{5, NULL, NULL};
root->rchild->lchild = new BTNode{6, NULL, NULL};
root->rchild->rchild = new BTNode{7, NULL, NULL};
vector<int> path;
int max_path_len = maxDepth(root, path);
cout<<"The maximum path length is "<<max_path_len<<endl;
cout<<"The path is: ";
for(auto it = path.rbegin(); it != path.rend(); ++it){
cout<<*it<<" ";
}
cout<<endl;
return 0;
}
```
输出:
```
The maximum path length is 4
The path is: 1 3 7
```