C++实现二叉树深度算法 |21xrx.com

C++实现二叉树深度算法

2023-06-29 04:40:53 深夜i -- --

C++ 二叉树深度算法实现

二叉树是一种有序的树结构，其中每个节点最多连接两个子节点。在二叉树中，节点的深度指的是它到根节点的距离。在许多情况下，确定二叉树的深度是一项重要的任务。在C++中，我们可以使用递归算法来确定二叉树的深度。

首先，我们需要定义二叉树的节点。每个节点应该包含一个值、一个左子节点和一个右子节点。因此，我们可以定义一个结构体来表示二叉树节点。


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

接下来，我们可以定义一个递归函数来计算二叉树的深度。该函数的参数为一个二叉树节点指针，返回值为该节点的深度。


int maxDepth(TreeNode* root) {
  if (root == NULL)
    return 0;
  
  int leftDepth = maxDepth(root->left);
  int rightDepth = maxDepth(root->right);
  return max(leftDepth, rightDepth) + 1;
}

在该函数中，我们首先检查传入的节点指针是否为NULL，如果是，说明该节点不存在，返回0。否则，我们递归调用该函数，计算该节点的左子树和右子树的深度。然后，我们返回左子树和右子树深度的较大值加1作为该节点的深度。

最后，我们可以在main函数中创建一颗二叉树并计算其深度。


int main() {
  TreeNode* root = new TreeNode(1);
  root->left = new TreeNode(2);
  root->right = new TreeNode(3);
  root->left->left = new TreeNode(4);
  root->right->left = new TreeNode(5);
  root->right->right = new TreeNode(6);
  int depth = maxDepth(root);
  cout << "The depth of the binary tree is " << depth << endl;
  return 0;
}

在上述代码中，我们创建了一颗具有6个节点的二叉树，并计算该树的深度。运行该程序，我们可以看到输出：

The depth of the binary tree is 3

表明该二叉树的深度为3。

通过上述方法，我们可以轻松地计算任何二叉树的深度。递归算法的优势在于它可以有效地处理树结构，并且代码简单易读。

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

下一篇: C++ 数组比较大小的方法

评论区

()

相似文章