C++实现获取树的高度 |21xrx.com

C++实现获取树的高度

2023-07-05 07:47:37 深夜i -- --

C++ 获取树高度

C++是一门广泛应用于计算机编程的高级编程语言，它能够实现各种复杂的算法和数据结构。其中，二叉树是一种重要的数据结构，它是由节点及其指针所组成的树形结构，其中每个节点最多只有两个子节点。在C++语言中，获取树的高度是一项基本的操作，它可以帮助我们了解树的深度和结构。

首先，我们需要理解树的高度是如何计算的。树的高度是指从根节点到最远叶子节点的最长路径上的节点数。在C++代码中，可以使用递归函数的方式来计算树的高度。递归函数是一种函数调用自身的过程，它通常可以用于解决递归问题。对于获取树的高度来说，递归函数可以先计算出根节点的左子树的高度和右子树的高度，然后将它们中的最大值加1即可得到整个树的高度。

以下是一个简单的C++程序，可以用于获取二叉树的高度。


#include <iostream>
using namespace std;
//定义二叉树的结构体
struct BinaryTree
{
  int data;
  BinaryTree *left;
  BinaryTree *right;
};
//函数：获取二叉树的高度
int getTreeHeight(BinaryTree *root)
{
  //如果根节点为空，返回0
  if (root == nullptr) return 0;
  
  //计算左子树和右子树的高度
  int leftHeight = getTreeHeight(root->left);
  int rightHeight = getTreeHeight(root->right);
  
  //返回左子树和右子树中的最大值加1
  return max(leftHeight, rightHeight) + 1;
}
int main()
{
  //初始化二叉树
  BinaryTree *root = new BinaryTree nullptr;
  root->left = new BinaryTree nullptr;
  root->right = new BinaryTree3;
  root->left->left = new BinaryTree4;
  root->left->right = new BinaryTree5;
  root->right->left = new BinaryTree nullptr;
  root->right->right = new BinaryTree7;
  
  //获取二叉树的高度
  int treeHeight = getTreeHeight(root);
  
  //输出二叉树的高度
  cout<<"Binary tree height: "<<treeHeight<<endl;
  
  return 0;
}

在这个程序中，我们首先定义了一个二叉树的结构体，它包含了根节点数据和指向左右子树的指针。然后，我们定义了一个函数getTreeHeight，它用于计算二叉树的高度。在getTreeHeight函数中，我们使用递归函数的方式计算左子树和右子树的高度，并将它们中的最大值加1作为整个二叉树的高度。最后，在程序的主函数中，我们构建了一个二叉树，并输出了它的高度。

综上所述，C++语言可以很方便地实现获取树的高度的操作。对于需要计算树的高度的问题，我们可以使用递归函数的方式来解决。这种方式既简单又高效，可以帮助我们更好地理解树的深度和结构。

上一篇: idea打包java可执行jar包

下一篇: C++中i++和++i有何区别？

评论区

()

相似文章