Data Structure--二叉树例题解析(2)--二叉树前序遍历--二叉树中序遍历--二叉树后序遍历-蒲公英云

Data Structure--二叉树例题解析(2)--二叉树前序遍历--二叉树中序遍历--二叉树后序遍历

二叉树例题解析2

- 二叉树前序遍历递归
- 二叉树前序遍历非递归
- 二叉树中序遍历非递归
- 二叉树后序遍历非递归

这里的三种遍历方法和之前讲的遍历方法也有关,有兴趣可以回顾一下.

二叉树前序遍历递归

我只写了前序遍历的递归方式,但是只要你将前序的掌握了,后面两种的递归方式也是大同小异,大家自己写哦.

int getSize(struct TreeNode* root){         //求大小的函数
    if (root){ 
        return  getSize(root->left) + getSize(root->right) + 1;
    }
    return 0;
}
void preorder(struct TreeNode* root, int* arr, int* idx){ 
    if (root){ 
        arr[*idx] = root->val;        //核心 将值进行赋予,并进行递归的操作
        (*idx)++;
        preorder(root->left, arr, idx);        //左子树
        preorder(root->right, arr, idx);    //右子树
    }
}
int* preorderTraversal(struct TreeNode* root, int* returnSize){ 
    int sz = getSize(root);        //先求长
    int* arr = (int*)malloc(sizeof(int)*sz);    //动态开辟
    int idx = 0;
    preorder(root, arr, &idx);        //函数调用
    *returnSize = idx;        //更新
    return arr;        //输出
}

二叉树前序遍历非递归

调用了栈的操作,接口我就不多描述了, 具体点击

int* preorderTraversal(struct TreeNode* root, int* returnSize){ 
    int sz = getSize(root);        //先求长 
    int* arr = malloc(sizeof(int)*sz);        //动态开辟
    stack st;        //栈开辟
    stackInit(&st);        //初始化
    int idx;        //定义整型变量
    //当前遍历的节点不为空,或栈不为空
    while (root || !stackEmpty(&st)){ 
        //1.访问左边路径
        while (root){                             //1.====前序
            arr[idx++] = root->val;
            //当前节点入栈
            stackPush(&st, root);                //2.====先访问左子树
            root = root->left;        
        }
        //2.获取栈顶元素,访问右子树
        root = stackTop(&st);                    //3.====再头结点,并出栈
        stackPop(&st);        
        root = root->right;                        //4.====再访问右子树
    }
    *returnSize = idx;
    return arr;        //返回值
}

二叉树中序遍历非递归

大题思路一致,只是访问的先后次序发生了变化

int* inorderTraversal(struct TreeNode* root, int* returnSize){ 
    int sz = getSize(root);        //得到大小
    int* arr = malloc(sizeof(int)*sz);        //动态开辟
    stack st;        //创建栈
    stackInit(&st);        //初始化
    int idx = 0;
    while (root || !stackEmpty(&st)){         //存在并不为空的条件下开始循环
                                            //1.====中序遍历
        //1.先遍历左边
        while (root){ 
            stackPush(&st, root);            //2.====左子树
            root = root->left;
        }
        //2.获取栈顶元素
        root = stackTop(&st);                //3.====栈顶
        stackPop(&st);
        arr[idx++] = root->val;
        //3.访问右子树
        root = root->right;                    //4.====右子树
    }
    *returnSize = idx;
    return arr;
}

二叉树后序遍历非递归

在这里插入图片描述

int* postorderTraversal(struct TreeNode* root, int* returnSize){ 
    int sz = getSize(root);
    int* arr = (int*)malloc(sizeof(int)*sz);
    stack st;
    stackInit(&st);
    int idx = 0;
    //prev:上次访问记得节点位置
    struct TreeNode* prev = NULL;
    while (root || !stackEmpty(&st)){ 
        //1.遍历左路径
        while (root){ 
            stackPush(&st, root);                        //1.====左子树
            root = root->left;
        }
        //top:栈顶的节点
        struct TreeNode* top = stackTop(&st);
        //这里要进行判断是否能访问栈顶
        //条件:没有右子树或者右子树访问完毕
        if (top->right == NULL || top->right == prev){     //2.====判断是否为头结点
            //访问栈顶元素
            arr[idx++] = top->val;
            stackPop(&st);
            prev = top;
        }
        else
            //访问右子树
            root = top->right;                            //3.====右子树
    }
    *returnSize = idx;
    return arr;
}