数据结构
网络
关系型数据库管理系统
操作系统
Java
Microsoft Excel
iOS
HTML
CSS
Android
Python
C 语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
时尚研究
法律研究使用 C++ 来打印二叉树中从一个叶节点到另一个叶节点的最长路径
在本次教程中，我们将讨论一个程序，该程序用于打印给定二叉树中从一个叶节点到另一个叶节点的最长路径。
换句话说，我们必须打印出现在二叉树直径中的所有节点。此处，给定二叉树的直径（或宽度）被定义为从一个端节点到另一个端节点的最长路径中的节点数。
为了解决这个问题，我们使用高度函数来计算二叉树的直径。然后，我们找到二叉树左部分和右部分的最长路径。最后，要打印直径中的节点，我们需要打印左部分节点、根节点，然后打印右部分节点。
示例
#include <bits/stdc++.h>
using namespace std;
struct Node {
int data;
Node *left, *right;
};
struct Node* create_node(int data){
struct Node* node = new Node;
node->data = data;
node->left = node->right = NULL;
return (node);
}
int tree_height(Node* root, int& ans, Node*(&k), int& lh, int& rh, int& f){
if (root == NULL)
return 0;
int left_tree_height = tree_height(root->left, ans, k, lh, rh, f);
int right_tree_height = tree_height(root->right, ans, k, lh, rh, f);
if (ans < 1 + left_tree_height + right_tree_height){
ans = 1 + left_tree_height + right_tree_height;
k = root;
lh = left_tree_height;
rh = right_tree_height;
}
return 1 + max(left_tree_height, right_tree_height);
}
void print_roottonode(int ints[], int len, int f){
int i;
if (f == 0){
for (i = len - 1; i >= 0; i--) {
printf("%d ", ints[i]);
}
}
else if (f == 1) {
for (i = 0; i < len; i++) {
printf("%d ", ints[i]);
}
}
}
void print_pathr(Node* node, int path[], int pathLen, int max, int& f){
if (node == NULL)
return;
path[pathLen] = node->data;
pathLen++;
if (node->left == NULL && node->right == NULL) {
if (pathLen == max && (f == 0 || f == 1)) {
print_roottonode(path, pathLen, f);
f = 2;
}
}
else {
print_pathr(node->left, path, pathLen, max, f);
print_pathr(node->right, path, pathLen, max, f);
}
}
void calc_diameter(Node* root){
if (root == NULL)
return;
int ans = INT_MIN, lh = 0, rh = 0;
int f = 0;
Node* k;
int tree_height_of_tree = tree_height(root, ans, k, lh, rh, f);
int lPath[100], pathlen = 0;
print_pathr(k->left, lPath, pathlen, lh, f);
printf("%d ", k->data);
int rPath[100];
f = 1;
print_pathr(k->right, rPath, pathlen, rh, f);
}
int main(){
struct Node* root = create_node(12);
root->left = create_node(22);
root->right = create_node(33);
root->left->left = create_node(45);
root->left->right = create_node(57);
root->left->right->left = create_node(26);
root->left->right->right = create_node(76);
root->left->left->right = create_node(84);
root->left->left->right->left = create_node(97);
calc_diameter(root);
return 0;
}输出
97 84 45 22 57 26
更新时间：2019-11-01
319 次浏览
广告