c++递归计算二叉树的高度
时间: 2023-08-06 13:08:37 浏览: 83
好的,可以使用以下代码实现二叉树高度的递归计算:
```cpp
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
int getHeight(TreeNode* root) {
if (!root) {
return 0;
}
int leftHeight = getHeight(root->left);
int rightHeight = getHeight(root->right);
return max(leftHeight, rightHeight) + 1;
}
```
其中,getHeight() 函数为递归函数,用于计算二叉树的高度。如果当前节点为空,返回 0。否则,分别递归计算左子树和右子树的高度,取两者的较大值并加 1,即为当前节点所在子树的高度。最终返回整棵树的高度即可。
相关问题
非递归遍历二叉树c++
非递归遍历二叉树是指在不使用递归函数的情况下,对二叉树进行遍历的方法。以下是三种非递归遍历二叉树的方法:
1. 非递归中序遍历二叉树
中序遍历二叉树的顺序是:左子树 -> 根节点 -> 右子树。使用栈来保存未被访问的节点,具体步骤如下:
1)从根节点开始,将当前节点入栈。
2)如果当前节点有左子树,则将左子树入栈并进入左子树,重复步骤2,直到左子树为空。
3)从栈中弹出节点,访问该节点。
4)如果该节点有右子树,则将右子树入栈并进入右子树,重复步骤2、3、4。
2. 非递归先序遍历二叉树
先序遍历二叉树的顺序是:根节点 -> 左子树 -> 右子树。使用栈来保存未被访问的节点,具体步骤如下:
1)从根节点开始,将当前节点入栈。
2)从栈中弹出节点,访问该节点。
3)如果该节点有右子树,则将右子树入栈。
4)如果该节点有左子树,则将左子树入栈。
5)重复步骤2、3、4,直到栈为空。
3. 非递归后序遍历二叉树
后序遍历二叉树的顺序是:左子树 -> 右子树 -> 根节点。使用两个栈来实现,具体步骤如下:
1)将根节点入栈1。
2)从栈1中弹出节点,并将该节点入栈2。
3)如果该节点有左子树,则将左子树入栈1。
4)如果该节点有右子树,则将右子树入栈1。
5)重复步骤2、3、4,直到栈1为空。
6)从栈2中依次弹出节点并访问。
递归遍历二叉树 c++ 代码
递归遍历二叉树的C代码如下所示:
```
// 定义二叉树节点的数据结构
typedef struct TreeNode{
int val;
struct TreeNode* left;
struct TreeNode* right;
} TreeNode;
// 递归遍历二叉树的函数
void recursiveTraversal(TreeNode* node){
// 递归终止条件:节点为空
if(node == NULL){
return;
}
// 先序遍历:先访问根节点,再递归遍历左右子树
printf("%d ", node->val);
recursiveTraversal(node->left);
recursiveTraversal(node->right);
// 中序遍历:先递归遍历左子树,再访问根节点,最后递归遍历右子树
recursiveTraversal(node->left);
printf("%d ", node->val);
recursiveTraversal(node->right);
// 后序遍历:先递归遍历左右子树,再访问根节点
recursiveTraversal(node->left);
recursiveTraversal(node->right);
printf("%d ", node->val);
}
```
以上代码定义了二叉树节点的数据结构`TreeNode`,其中包含节点的值、左子节点和右子节点。`recursiveTraversal`函数是递归遍历二叉树的主函数,传入根节点作为参数。
在函数内部,首先判断节点是否为空,如果为空则直接返回。然后按照先序遍历、中序遍历和后序遍历的顺序,依次对根节点、左子树和右子树进行递归遍历。在先序遍历中,先访问根节点,再递归遍历左右子树。在中序遍历中,先递归遍历左子树,然后访问根节点,最后递归遍历右子树。在后序遍历中,先递归遍历左右子树,再访问根节点。
在每个遍历过程中,可以根据实际需求对节点进行操作,例如将节点的值打印出来。
以上就是递归遍历二叉树的C代码,通过递归的方式可以方便地遍历整个二叉树。