如何用C++实现二叉树的前序

在C++中，可以使用递归的方式来实现二叉树的前序遍历（Preorder Traversal）。前序遍历的顺序是根节点 -> 左子树 -> 右子树。下面是简单的C++代码示例：

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

void preorderTraversal(TreeNode* root) {
    if (root == nullptr) return; // 避免空指针异常
    cout << root->val << " "; // 访问根节点
    preorderTraversal(root->left); // 递归遍历左子树
    preorderTraversal(root->right); // 递归遍历右子树
}

在这个例子中，`preorderTraversal`函数接收一个指向二叉树根节点的指针。如果当前节点为空，则返回；否则，先访问当前节点的值，然后对左子树和右子树分别进行前序遍历。

相关问题

c++编写二叉树前序遍历非递归

下面是C++编写二叉树前序遍历非递归的代码：

#include<iostream>
#include<stack>
using namespace std;

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

void preorderTraversal(TreeNode* root) {
    if(root == NULL) {
        return;
    }
    stack<TreeNode*> stk;
    stk.push(root);
    while(!stk.empty()) {
        TreeNode* node = stk.top();
        stk.pop();
        cout<<node->val<<" ";
        if(node->right != NULL) {
            stk.push(node->right);
        }
        if(node->left != NULL) {
            stk.push(node->left);
        }
    }
}

int main() {
    // test case
    TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);
    root->left->left = new TreeNode(4);
    root->left->right = new TreeNode(5);
    root->right->left = new TreeNode(6);
    root->right->right = new TreeNode(7);
    cout<<"preorderTraversal:"<<endl;
    preorderTraversal(root);
    return 0;
}

上面的代码通过使用栈来模拟递归过程，实现了二叉树的前序遍历。

c++扩展二叉树前序遍历序列构建二叉树并计算该二叉树的深度

在扩展二叉树中，空节点用"#"表示。通过扩展二叉树的前序遍历序列可以构建该二叉树，具体步骤如下：

1. 从前序序列中取出第一个元素作为根节点；
2. 如果序列中下一个元素不是"#", 则递归创建其左子树；
3. 如果序列中下一个元素不是"#", 则递归创建其右子树。

以下是C++代码实现：

#include<iostream>
using namespace std;
 
struct TreeNode{
    char val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(char x): val(x), left(nullptr), right(nullptr) {}
};
 
TreeNode* buildTree(string s, int& index){
    if(index >= s.size()){
        return nullptr;
    }
    if(s[index] == '#'){
        index++;
        return nullptr;
    }
    TreeNode* root = new TreeNode(s[index]);
    index++;
    root->left = buildTree(s, index);
    root->right = buildTree(s, index);
    return root;
}
 
int maxDepth(TreeNode* root){
    if(root == nullptr){
        return 0;
    }
    int leftDepth = maxDepth(root->left);
    int rightDepth = maxDepth(root->right);
    return max(leftDepth, rightDepth) + 1;
}
 
int main(){
    string s = "ABC##DE#G##F###";
    int index = 0;
    TreeNode* root = buildTree(s, index);
    cout << "该二叉树的深度为：" << maxDepth(root) << endl;
    return 0;
}