用C++建立一棵二叉树，并用递归算法用前序遍历之。 前序遍历二叉树的操作定义为： 若二叉树为空，则空操作；否则 （1）访问根结点； （2）前序遍历左子树； （3）前序遍历右子树。

在C++中，我们可以使用结构体或类表示二叉树节点，并利用递归来实现前序遍历。这里是一个简单的二叉树节点定义以及前序遍历函数的例子：

// 定义二叉树节点
struct TreeNode {
    int val;   // 节点值
    TreeNode* left;   // 左子节点指针
    TreeNode* right;  // 右子节点指针
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}  // 构造函数
};

// 前序遍历（递归）
void preOrderTraversal(TreeNode* root) {
    if (root == nullptr) {  // 如果当前节点为空，返回
        return;
    }
    cout << root->val << " ";  // 访问根节点
    preOrderTraversal(root->left);  // 递归遍历左子树
    preOrderTraversal(root->right);  // 递归遍历右子树
}

这个`preOrderTraversal`函数首先检查给定的根节点是否为空，如果为空则直接返回。然后它会打印出当前节点的值，接着对左子树和右子树分别进行前序遍历。

相关问题

用C++建立一棵二叉树，并用递归算法用前序遍历之，并写出完整代码。 前序遍历二叉树的操作定义为： 若二叉树为空，则空操作；否则 （1）访问根结点； （2）前序遍历左子树； （3）前序遍历右子树。

在C++中，我们可以创建一个简单的二叉树结构，并使用递归实现前序遍历。首先，我们定义一个`Node`类表示二叉树的节点，包含一个值和两个指向左右子节点的指针。然后，我们提供一个名为`PreOrderTraversal`的函数来进行前序遍历。

#include <iostream>

// 定义二叉树节点
class Node {
public:
    int data;
    Node* left;
    Node* right;

    // 构造函数
    Node(int value) : data(value), left(nullptr), right(nullptr) {}
};

// 前序遍历函数
void PreOrderTraversal(Node* root) {
    if (root == nullptr) {
        return; // 如果根节点为空，直接返回
    }
    std::cout << root->data << " "; // 访问根节点
    PreOrderTraversal(root->left); // 遍历左子树
    PreOrderTraversal(root->right); // 遍历右子树
}

int main() {
    // 创建一个简单的二叉树示例
    Node* root = new Node(1);
    root->left = new Node(2);
    root->right = new Node(3);
    root->left->left = new Node(4);
    root->left->right = new Node(5);

    // 调用前序遍历
    PreOrderTraversal(root);

    return 0;
}

当运行这个程序时，它会按照前序遍历的方式打印出二叉树的节点值：1 2 4 5 3。

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

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

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 的思想，所以需要使用队列。