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