正经题解|Gold King的二叉树遍历

没什么，自己看注释

#include<iostream>
using namespace std;
 
// 定义二叉树节点结构体
struct TreeNode{
    int val;           // 节点值 
    TreeNode *left,*right;  // 左右子节点指针 
    // 构造函数，初始化节点值和左右子节点为nullptr 
    TreeNode(int x):val(x),left(nullptr),right(nullptr){};
};
 
// 递归删除整棵二叉树（后序遍历删除）
void deleteTree(TreeNode* root){
    if(root==nullptr) return;  // 空节点直接返回
    deleteTree(root->left);    // 删除左子树
    deleteTree(root->right);   // 删除右子树
    delete root;               // 删除当前节点
}
 
// 向二叉搜索树中插入节点 
TreeNode* insert(TreeNode* root,int x){
    if(root==nullptr) return new TreeNode(x);  // 找到插入位置，创建新节点
    // 如果x小于当前节点值，插入到左子树；否则插入到右子树 
    x<root->val?root->left=insert(root->left,x):root->right=insert(root->right,x);
    return root;  // 返回根节点
}
 
// 前序遍历：根-左-右 
void preord(TreeNode* root){
    if(root==nullptr) return;      // 空节点直接返回
    cout<<root->val<<" ";          // 访问根节点 
    preord(root->left);            // 遍历左子树
    preord(root->right);           // 遍历右子树 
}
 
// 中序遍历：左-根-右
void inord(TreeNode* root){
    if(root==nullptr) return;      // 空节点直接返回
    inord(root->left);             // 遍历左子树 
    cout<<root->val<<" ";          // 访问根节点
    inord(root->right);            // 遍历右子树 
}
 
// 后序遍历：左-右-根 
void postord(TreeNode* root){
    if(root==nullptr) return;      // 空节点直接返回
    postord(root->left);           // 遍历左子树 
    postord(root->right);          // 遍历右子树 
    cout<<root->val<<" ";          // 访问根节点
}
 
int main(){
    int n=0,a[105]={0};            // n为节点个数，a数组存储输入的数据 
    cin>>n;                        // 输入节点个数
    TreeNode* tree=nullptr;        // 初始化二叉搜索树根节点为空 
    
    for(int i=1;i<=n;++i){         // 循环读入n个数据并插入到二叉搜索树中
        cin>>a[i];                 // 读入第i个数据 
        tree=insert(tree,a[i]);    // 插入到二叉搜索树中
    }
    
    preord(tree);                  // 输出前序遍历结果 
    cout<<"\n";                    // 换行
    inord(tree);                   // 输出中序遍历结果 
    cout<<"\n";                    // 换行
    postord(tree);                 // 输出后序遍历结果
    deleteTree(tree);              // 删除整棵树，释放内存
    return 0;
}