C++求二叉树高度 |21xrx.com

C++求二叉树高度

2023-06-22 15:13:13 深夜i 22 0

C++ 二叉树高度递归计算

二叉树是一种常见的数据结构，它由节点和链接组成，其中每个节点最多有两个子节点。在C++中求二叉树高度有很多方法，下面我们来介绍几种常见的方法。

1. 递归法

递归法是最简单的求解二叉树高度的方法。我们可以通过循环遍历整个二叉树，即一直递归到叶子节点，然后计算左右子树的高度，然后取最大值即可。

示例代码如下：

int getHeight(Node* root) {
  if (!root)
    return 0;
  
  int left = getHeight(root->left);
  int right = getHeight(root->right);
  return max(left, right) + 1;
}

2. 非递归法

非递归法也是一种比较常见的求解二叉树高度的方法，我们可以使用栈来实现。我们可以使用一个栈来存储节点，每次遍历到一个节点，就将它的左右子节点压入栈中，然后比较左右子树的高度，取最大值即可。

示例代码如下：

int getHeight(Node* root) {
  stack<Node*> s;
  if (root) s.push(root);
  int height = 0;
  while (!s.empty()) {
    int size = s.size();
    height++;
    for (int i = 0; i < size; i++) {
      Node* node = s.top();
      s.pop();
      if (node->left) s.push(node->left);
      if (node->right) s.push(node->right);
    }
  }
  return height;
}

3. 层序遍历法

层序遍历法也是一种比较常见的求解二叉树高度的方法，我们可以使用队列来实现。我们可以将根节点放入队列中，然后每次取出队列的元素判断是否有左右子节点，如果有的话将它们放入队列中，然后遍历完一层后高度加1，直到队列为空。

示例代码如下：

int getHeight(Node* root) {
  if (!root)
    return 0;
  
  queue<Node*> q;
  q.push(root);
  int height = 0;
  while (!q.empty()) {
    int size = q.size();
    height++;
    for (int i = 0; i < size; i++) {
      Node* node = q.front();
      q.pop();
      if (node->left) q.push(node->left);
      if (node->right) q.push(node->right);
    }
  }
  return height;
}

综上所述，以上三种方法都是求解二叉树高度比较常用的方法。对于一些较大的二叉树，使用非递归和层序遍历方法可能会更加高效。

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

下一篇: C++编程：交换一个三位数中的6和9

评论区

相似文章