C++编程：输入二叉树，求其高度 |21xrx.com

C++编程：输入二叉树，求其高度

2023-06-28 04:18:24 深夜i -- --

C++ 二叉树高度输入求解

C++编程是面向对象的一种程序设计语言，它的语法特点简洁明了，这使得它被广泛用于计算机程序开发中。在计算机中，二叉树是一种常见的数据结构，它可以用来表示层次性的关系。

当我们需要处理一个二叉树时，通常需要知道它的高度，即从根节点到最远叶子节点的最长路径。在这篇文章中，我们将介绍如何在C++中输入一个二叉树，并计算其高度。

在C++中，我们可以使用结构体来表示一个二叉树节点。结构体中需要包含一个值域、左子树指针和右子树指针。如下所示：


struct TreeNode {
  int val;
  TreeNode* left;
  TreeNode* right;
  TreeNode(int x):val(x), left(nullptr), right(nullptr){}
};

然后，我们需要编写一个函数来输入这个二叉树。通常情况下，我们会按照二叉树的前序遍历顺序（根节点，左子树，右子树）来输入一个二叉树。代码如下：


TreeNode* buildTree() {
  int val;
  cin >> val;
  if (val == -1)
    return nullptr;
  
  TreeNode* root = new TreeNode(val);
  root->left = buildTree();
  root->right = buildTree();
  return root;
}

在这个函数中，如果输入的值为-1，则表示该节点为空，返回nullptr。否则，创建一个新的节点，并递归调用buildTree函数来构建这个节点的左子树和右子树。

最后，我们需要编写一个函数来求二叉树的高度。这个函数也是递归实现的。代码如下：


int treeHeight(TreeNode* root) {
  if (root == nullptr)
    return 0;
  
  int leftHeight = treeHeight(root->left);
  int rightHeight = treeHeight(root->right);
  return max(leftHeight, rightHeight) + 1;
}

在这个函数中，如果节点为空，则返回0。否则，递归计算左子树的高度和右子树的高度，然后将它们的最大值加1返回。

最后，我们只需要在main函数中调用buildTree函数构建树，然后调用treeHeight函数计算高度即可：


int main() {
  TreeNode* root = buildTree();
  int height = treeHeight(root);
  cout << "The height of the binary tree is: " << height << endl;
  return 0;
}

通过这个简单的例子，我们可以看到C++语言在处理二叉树问题中的优雅之处。它的语法简洁明了，易于理解和实现，非常适合进行算法编程。

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

下一篇: C++参数初始化的方式和规则

评论区

()

相似文章