二叉树的中序遍历递归算法

二叉树的中序遍历是指从根节点开始，先遍历左子树，然后访问根节点，最后遍历右子树。递归实现中序遍历的算法如下：

1. 如果当前节点为空，则返回
2. 递归遍历左子树
3. 访问当前节点
4. 递归遍历右子树

以下是示例代码实现：

void inorderTraversal(TreeNode* root) {
    if(root == NULL) {
        return;
    }
    inorderTraversal(root->left); // 遍历左子树
    cout << root->val << " "; // 访问当前节点
    inorderTraversal(root->right); // 遍历右子树
}

相关问题

二叉树中序遍历递归算法c语言实现

二叉树的中序遍历可以通过递归算法来实现，在C语言中可以使用以下代码：

#include <stdio.h>
#include <stdlib.h>

// 定义二叉树节点结构
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
};

// 中序遍历函数
void inorderTraversal(struct TreeNode* root) {
    if (root == NULL) {
        return;
    }
    inorderTraversal(root->left);   // 递归遍历左子树
    printf("%d ", root->val);       // 打印当前节点的值
    inorderTraversal(root->right);  // 递归遍历右子树
}

// 创建新节点
struct TreeNode* createNode(int val) {
    struct TreeNode* newNode = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    newNode->val = val;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}

int main() {
    // 创建二叉树
    struct TreeNode* root = createNode(1);
    root->left = createNode(2);
    root->right = createNode(3);
    root->left->left = createNode(4);
    root->left->right = createNode(5);
    
    // 中序遍历
    printf("Inorder traversal: ");
    inorderTraversal(root);
    
    return 0;
}

运行以上代码，将会输出二叉树的中序遍历结果。希望对你有所帮助！

前序遍历二叉树的递归算法 中序遍历二叉树的递归算法 层序遍历二叉树的递归算法

前序遍历二叉树的递归算法：

1. 如果根节点为空，则返回。
2. 访问根节点。
3. 对根节点的左子树进行前序遍历。
4. 对根节点的右子树进行前序遍历。

代码实现：

void preorderTraversal(TreeNode* root) {
if (root == nullptr) {
return;
}
cout << root->val << " ";
preorderTraversal(root->left);
preorderTraversal(root->right);
}

中序遍历二叉树的递归算法：

1. 如果根节点为空，则返回。
2. 对根节点的左子树进行中序遍历。
3. 访问根节点。
4. 对根节点的右子树进行中序遍历。

代码实现：

void inorderTraversal(TreeNode* root) {
if (root == nullptr) {
return;
}
inorderTraversal(root->left);
cout << root->val << " ";
inorderTraversal(root->right);
}

层序遍历二叉树的递归算法：

层序遍历一般使用队列实现，递归实现效率低且不太方便，下面是非递归代码实现。

void levelOrderTraversal(TreeNode* root) {
if (root == nullptr) {
return;
}
queue<TreeNode*> q;
q.push(root);
while (!q.empty()) {
TreeNode* node = q.front();
q.pop();
cout << node->val << " ";
if (node->left != nullptr) {
q.push(node->left);
}
if (node->right != nullptr) {
q.push(node->right);
}
}
}

注意：这里的层序遍历使用了 BFS 的思想，所以需要使用队列。