二叉树前序、中序、后序遍历（递归法、迭代法）

前序遍历：（练习题）

迭代法一：


int TreeSize(struct TreeNode* root){
    return root==NULL?0:TreeSize(root->left)+TreeSize(root->right)+1;
}
 
 
int* preorderTraversal(struct TreeNode* root, int* returnSize){
    if(root==NULL){
        *returnSize = 0;
        return (int*)malloc(sizeof(int)*0);
    }
    int size = TreeSize(root);//获得树的节点数
    int* ans = (int*)malloc(sizeof(int)*size);//开辟数组
    struct TreeNode** s = (struct TreeNode*)malloc(sizeof(struct TreeNode*)*size*2);//模拟栈
    int top = 0;
    int i = 0;
    struct TreeNode* node = root;
    while(i
        if(node){
            ans[i++] = node->val;
            s[top++] = node;
            node = node->left;
        }else{
           node = s[--top];
           node = node->right; 
        }
    }
    free(s);//释放内存
    *returnSize = size;
    return ans;
}

迭代法二：


 
int TreeSize(struct TreeNode* root){
    return root==NULL?0:TreeSize(root->left)+TreeSize(root->right)+1;
}
 
int* preorderTraversal(struct TreeNode* root, int* returnSize){
    if(root==NULL){
        *returnSize = 0;
        return (int*)malloc(sizeof(int)*0);
    }
    int size = TreeSize(root);//获得树的节点数
    int* ans = (int*)malloc(sizeof(int)*size);//开辟数组
    struct TreeNode** s = (struct TreeNode*)malloc(sizeof(struct TreeNode*)*size*2);//模拟栈
    int top = 0;
    int i = 0;
    s[top++] = root;
    while(i
        struct TreeNode* node = s[--top];//出栈
        if(node){
            if(node->right) s[top++] = node->right;
            if(node->left) s[top++] = node->left;
            s[top++] = node;
            s[top++] = NULL;//表明前一个根节点已经访问过子树
        }else{
            ans[i++] = s[--top]->val;
        }
 
    }
    free(s);//释放内存
    *returnSize = size;
    return ans;
}

迭代法三：


int TreeSize(struct TreeNode* root){
    return root==NULL?0:TreeSize(root->left)+TreeSize(root->right)+1;
}
 
int* preorderTraversal(struct TreeNode* root, int* returnSize){
    int size = TreeSize(root);//获得树的节点数
    int* ans = (int*)malloc(sizeof(int)*size);//开辟数组
    struct TreeNode** s = (struct TreeNode*)malloc(sizeof(struct TreeNode*)*size);//模拟栈
    int top = 0;
    int i = 0;
    s[top++] = root;
    while(i
        struct TreeNode* node = s[--top];//出栈
        ans[i++] = node->val;
        //左右子树入栈
        //根左右（栈先进后出，先入右子树后入左子树）
        if(node->right)  s[top++] = node->right;
        if(node->left)  s[top++] = node->left;
 
    }
    free(s);//释放内存
    *returnSize = size;
    return ans;
}

递归法：


void preorder(struct TreeNode* root,int* ans,int* i){
    if(root==NULL) return ;
    ans[(*i)++] = root->val;
    preorder(root->left,ans,i);
    preorder(root->right,ans,i);
}
 
int* preorderTraversal(struct TreeNode* root, int* returnSize){
    int* ans = (int*)malloc(sizeof(int)*101);
    int i= 0;
    preorder(root,ans,&i);
    *returnSize = i;
    return ans;
}

中序遍历：（练习题）

迭代法一：


 
int TreeSize(struct TreeNode* root){
    return root==NULL?0:TreeSize(root->left)+TreeSize(root->right)+1;
}
 
int* inorderTraversal(struct TreeNode* root, int* returnSize){
    if(root==NULL){
        *returnSize=0;
        return (int*)malloc(sizeof(int)*0);
    }
    int size = TreeSize(root);
    *returnSize = size;
    int* ans = (int*)malloc(sizeof(int)*size);
    struct TreeNode** s = (struct TreeNode*)malloc(sizeof(struct TreeNode*)*size*2);//模拟栈
    int i = 0;
    int top = 0;//栈顶
    s[top++] = root;
    while(i
        struct TreeNode* node = s[--top];
        if(node){
            if(node->right) s[top++] = node->right;
            s[top++] = node;
            s[top++] = NULL;
            if(node->left) s[top++] = node->left;
        }else{
            ans[i++] = s[--top]->val;
        }
    }
    free(s);
    return ans;
}

迭代法二：


//节点个数
int TreeSize(struct TreeNode* root){
    return root==NULL?0:TreeSize(root->left)+TreeSize(root->right)+1;
}
 
int* inorderTraversal(struct TreeNode* root, int* returnSize){
    if(!root){//空树
        *returnSize = 0;
        return (int*)malloc(sizeof(int*)*0);
    }
    int size = TreeSize(root);
    *returnSize = size;
    int* ans = (int*) malloc(sizeof(int)*size);
    struct TreeNode** s = (struct TreeNode*)malloc(sizeof(struct TreeNode*)*size*2);//模拟栈
    int i = 0;
    int top = 0;//栈顶
    struct TreeNode* node = root;
    while(i
        if(node){//一直检索左孩子
            s[top++] = node;//入栈
            node = node->left;//一路向左
        }else{//出栈
            node = s[--top];//栈顶元素出栈
            ans[i++] = node->val;
            node = node->right;//右子树
        }
    }
    free(s);
    return ans;
}

递归法：


int TreeSize(struct TreeNode* root){
    return root==NULL?0:TreeSize(root->left)+TreeSize(root->right)+1;
}
 
void inorder(struct TreeNode* root,int* ans,int* i){
    if(root==NULL) return;
    inorder(root->left,ans,i);
    ans[(*i)++] = root->val;
    inorder(root->right,ans,i);
}
 
int* inorderTraversal(struct TreeNode* root, int* returnSize){
    int size = TreeSize(root);
    int* ans = (int*)malloc(sizeof(int)*size);
    int i = 0;
    inorder(root,ans,&i);
    *returnSize = size;
    return ans;
}

后序遍历：（练习题）

迭代法一：


int TreeSize(struct TreeNode* root){
    return root==NULL?0:TreeSize(root->left)+TreeSize(root->right)+1;
}
 
 
int* postorderTraversal(struct TreeNode* root, int* returnSize){
    if(root==NULL) {
        *returnSize = 0;
        return (int*)malloc(sizeof(int)*0);  
    }
    int size = TreeSize(root);//获得树的节点数
    int* ans = (int*)malloc(sizeof(int)*size);//开辟数组
    struct TreeNode** s = (struct TreeNode*)malloc(sizeof(struct TreeNode*)*size*2);//模拟栈
    int top = 0;
    int i = 0;
    s[top++] = root;
    //先根右左进栈，之后左右根出栈
    //这里注意如果root本来就为空，下面则会发生越界 所以不建议while(top>0) 或者开头便判断是否为空
    while(i
        struct TreeNode* node = s[--top];//弹出栈顶元素 并且pop掉
        if(node){//元素不为NULL
            s[top++] = node;
            s[top++] = NULL;//NULL标记前面根节点已经被访问
            if(node->right) s[top++] = node->right;
            if(node->left) s[top++] = node->left;
        }else{
            ans[i++] = s[--top]->val;
        }
        
    }
    free(s);//释放内存
    *returnSize = size;
    return ans;
}

迭代法二：


 
int TreeSize(struct TreeNode* root){
    return root==NULL?0:TreeSize(root->left)+TreeSize(root->right)+1;
}
 
 
int* postorderTraversal(struct TreeNode* root, int* returnSize){
    if(root==NULL) {
        *returnSize = 0;
        return (int*)malloc(sizeof(int)*0);  
    }
    int size = TreeSize(root);//获得树的节点数
    int* ans = (int*)malloc(sizeof(int)*size);//开辟数组
    struct TreeNode** s = (struct TreeNode*)malloc(sizeof(struct TreeNode*)*size*2);//模拟栈
    int top = 0;
    int i = 0;
    struct TreeNode* node = root;
    struct TreeNode* r = NULL;
    while(i
        if(node){
            s[top++] = node;
            node = node->left;
        }
        else{
            node = s[top-1];
            if(node->right&&r!=node->right){//防止重复遍历右子树
                node = node->right;
            }
            else{
                r = s[--top];
                ans[i++] = r->val;
                node = NULL;
            }
        }
    }
    free(s);//释放内存
    *returnSize = size;
    return ans;
}

递归法：


int TreeSize(struct TreeNode* root){
    return root==NULL?0:TreeSize(root->left)+TreeSize(root->right)+1;
}
 
void postorder(struct TreeNode* root,int* ans,int* i){
    if(root==NULL) return ;
    postorder(root->left,ans,i);
    postorder(root->right,ans,i);
    ans[(*i)++] = root->val;
}
 
int* postorderTraversal(struct TreeNode* root, int* returnSize){
    *returnSize = TreeSize(root);
    int* ans = (int*)malloc(sizeof(int)*(*returnSize));
    int i = 0;
    postorder(root,ans,&i);
    return ans;
}

相关阅读:
APISpace 成语大全API
Hugging News #0912: Hugging Face 2 人入选时代周刊全球百大 AI 人物
 LeetCode 2000. Reverse Prefix of Word
vue打开一个新窗口
 PCL的MLS（移动最小二乘）
浅谈C++|多态篇
 计算机网络第三章数据链路层
 基于Kubernetes构建企业Jenkins master/slave CI/CD平台
 【Docker】搭建 Docker 镜像仓库
 Pico-I / O嵌入式模块提供48点数字I / O接口
原文地址：https://blog.csdn.net/bigBbug/article/details/133466804