数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究用 C++ 编写程序查找树的最大深度或高度
在这个问题中，我们给定一棵二叉树。我们的任务是编写一个程序来查找给定树的最大深度或高度。
让我们举个例子来理解这个问题，
树的高度为 3。
为了找到树的最大高度，我们将检查其左子树和右子树的高度，并在两者中的最大值上加 1。这是一个递归过程，它将持续到找到树的最后一个节点，并逐步添加 1 以找到子树的高度。
以上示例使用此方法解决。
查找树的高度，即 height(3) = max(height(5),height(7)) + 1。
为此，我们将计算值为 5 和 7 的节点的高度。
height(5) = max(height(1),height(9)) + 1 以及
height(7) = 1，它没有可以形成的子树。
类似地，height(1) = height(9) = 1
height(5) = max(1,1) +1 = 2
height(3) = max(height(5),height(7)) + 1 = max(2,1) + 1 = 3。
所以高度变为 3。
程序说明解决方案，
示例
#include <iostream>
using namespace std;
class node {
public:
int data;
node* left;
node* right;
};
int height(node* node) {
if (node == NULL)
return 0;
else {
int lDepth = height(node->left);
int rDepth = height(node->right);
if (lDepth > rDepth)
return(lDepth + 1);
else return(rDepth + 1);
}
}
node* insertNode(int data) {
node* Node = new node();
Node->data = data;
Node->left = NULL;
Node->right = NULL;
return(Node);
}
int main() {
node *root = insertNode(4);
root->left = insertNode(5);
root->right = insertNode(0);
root->left->left = insertNode(1);
root->left->right = insertNode(9);
cout<<"The height of the given binary tree is "<<height(root);
return 0;
}输出
The height of the given binary tree is 3
更新于: 2020年4月20日
644 次查看
广告