用前序遍历方法创建二叉树 C++

前序遍历是一种常见的二叉树遍历方法，它的顺序是“根节点 -> 左子树 -> 右子树”。在C++中，我们可以使用递归的方式来实现这个过程。以下是一个简单的前序遍历函数示例：

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

// 前序遍历函数
void preorderTraversal(TreeNode* root) {
    if (root != NULL) { // 如果当前节点非空
        // 输出当前节点的值
        cout << root->val << " ";
        
        // 递归遍历左子树
        preorderTraversal(root->left);
        
        // 递归遍历右子树
        preorderTraversal(root->right);
    }
}

在这个函数中，我们首先检查根节点是否为空。如果不为空，就先访问根节点，然后递归地对左子树和右子树进行同样的操作。

相关问题

前序遍历创建二叉树c++

可以通过递归方式实现前序遍历创建二叉树的算法，具体步骤如下（假设二叉树的节点类型为Node）：

// 定义一个全局变量，用于记录前序遍历序列中的当前节点下标
int index = 0;

// 递归函数，用于创建二叉树
Node* createTree(vector<int>& preorder, int left, int right) {
    // 如果左下标大于右下标，说明已经遍历完该子树，返回空节点
    if (left > right) {
        return nullptr;
    }
    // 创建当前节点
    Node* root = new Node(preorder[index]);
    // 前序遍历序列中的下一个节点
    index++;
    // 递归创建左子树
    root->left = createTree(preorder, left, index - 1);
    // 递归创建右子树
    root->right = createTree(preorder, index, right);
    return root;
}

// 主函数，用于调用递归函数创建二叉树
Node* buildTree(vector<int>& preorder) {
    return createTree(preorder, 0, preorder.size() - 1);
}

其中，preorder为前序遍历序列，left和right分别为当前子树在前序遍历序列中的左右下标。在递归函数中，首先判断左下标是否大于右下标，如果是则返回空节点；否则，创建当前节点，并将前序遍历序列中的下一个节点作为左子树的根节点，递归创建左子树和右子树。最后，返回根节点即可。

C++用前序遍历创建二叉树

以下是C++用前序遍历创建二叉树的代码示例：

#include <iostream>
using namespace std;

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

TreeNode* buildTree() {
    int val;
    cin >> val;
    if (val == -1) { // -1表示空节点
        return NULL;
    }
    TreeNode* root = new TreeNode(val);
    root->left = buildTree();
    root->right = buildTree();
    return root;
}

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

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

int main() {
    TreeNode* root = buildTree();
    cout << "前序遍历结果为：";
    preorder(root);
    cout << endl;
    cout << "中序遍历结果为：";
    inorder(root);
    cout << endl;
    return 0;
}

输入格式为一串数字，其中-1表示空节点。例如，输入序列为1 2 -1 -1 3 4 -1 -1 5 -1 -1，则表示如下二叉树：

     1
   /   \
  2     3
       / \
      4   5

输出结果为：

前序遍历结果为：1 2 3 4 5 
中序遍历结果为：2 1 4 3 5