資料結構
網路
關係型資料庫管理系統
作業系統
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 次瀏覽
廣告