给出指定二叉树求其先中后序遍历

函数递归法(深度优先：先中后序；广度优先：层序)

先序递归

在这里插入图片描述

void PreOrder(BiTree T)
{
    /*先序遍历：递归遍历*/
    if (T != nullptr)
    {
        visit(T);//访问根节点
        PreOrder(T->lChild);//遍历左子树
        PreOrder(T->rChild);//遍历右子树
    }
}
中序递归

在这里插入图片描述

void InOrder(BiTree T)
{
    /*中序遍历：递归遍历*/
    if (T != nullptr)
    {
        InOrder(T->lChild);//遍历左子树
        visit(T);//访问根节点
        InOrder(T->rChild);//遍历右子树
    }
}
后序递归

在这里插入图片描述

void PostOrder(BiTree T)
{
    /*后序遍历：递归办法*/
    if (T != nullptr)
    {
        PostOrder(T->lChild);//遍历左子树
        PostOrder(T->rChild);//遍历右子树
        visit(T);//访问根节点
    }
}
层序递归（循环中递归）

在这里插入图片描述

void levelOrder_old(BiTree root,int level){
    /*递归求层序遍历结果（每一层）*/
    if(root == nullptr || level < 1){
        return;
    }
    if(level == 1){
        visit(root);
    }
    levelOrder_old(root->lChild,level - 1);
    levelOrder_old(root->rChild,level - 1);
}
int highLength(BiTree root){
    /*递归求树的高度*/
    int l_length = 0;
    int r_length = 0;
    if(root == nullptr){
        return 0;
    }
    else{
        l_length = highLength(root->lChild);
        r_length = highLength(root->rChild);
        if(l_length < r_length){
            return r_length + 1;
        }
        else{
            return l_length + 1;
        }
    }
}
void levelOrder(BiTree T){
    /*递归遍历层序*/
    if(T == nullptr){
        return;
    }
    int depth = highLength(T);
    for(int i = 1; i <= depth; i++){
        levelOrder_old(T,i);
    }
}

循环实现法

先序循环（一个栈）

在这里插入图片描述

void PreOrder_Loop(BiTree T)
{
    /*先序遍历：循环办法*/
    BiTree s = T;//设置s为遍历指针
    BiTree node;//设置指针node指向栈顶元素
    ClearStack(&stack_Order);//对栈做清空操作，使之备用
    while (!stack_Order.empty() || s != nullptr)
    {//当栈为空且同时遍历指针S为空的时候，先序访问结束，退出循环
        if (s != nullptr)
        {
            visit(s);           //访问当前节点
            stack_Order.push(s);//并将其入栈
            s = s->lChild;      //若其左孩子不空，则一直向左走
        }
        else
        {
            node = stack_Order.top();//s为空，取出栈顶元素
            stack_Order.pop();       //栈顶元素出栈
            s = node->rChild;        //转向栈顶元素的右子树
        }
    }
}
中序循环（一个栈）

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

void InOrder_Loop(BiTree T)
{
    /*中序遍历：循环办法*/
    BiTree s = T;//设置S为遍历指针
    BiTree node;//设置node指向栈顶元素
    ClearStack(&stack_Order);//对栈做清空操作，使之备用
    while (!stack_Order.empty() || s != nullptr)
    { //当栈为空且同时遍历指针S为空的时候，中序访问结束，退出循环
        if (s != nullptr)
        {
            stack_Order.push(s);//s不空，s入栈
            s = s->lChild;      //左孩子不空，则一直向左走
        }
        else
        {
            node = stack_Order.top();//s为空，node取栈顶元素
            stack_Order.pop();       //栈顶元素出栈
            visit(node);             //访问栈顶元素
            s = node->rChild;        //转向栈顶元素的右子树
        }
    }
}
后序循环（双栈）

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

void PostOrder_Loop(BiTree T)
{
    /*后序遍历：循环办法,两个栈*/
    BiTree s = T; //设置S为遍历指针
    BiTree node;  //设置node指向栈顶元素
    ClearStack(&stack_Order); //对栈做清空操作，使之备用
    ClearStack(&stack_PostOutput); //对栈做清空操作，使之备用
    while (!stack_Order.empty() || s != nullptr)
    { //当栈为空且同时遍历指针S为空的时候，后序访问结束，退出循环
        if (s != nullptr)
        {
            stack_Order.push(s);     //s不空 则s入order栈 
            stack_PostOutput.push(s);//s入output栈 ：入栈顺序：根、右、左，则出栈顺序为后序的顺序：左、右、根
            s = s->rChild;           //若右孩子不空，则一路向右
        }
        else
        {
            node = stack_Order.top();//s为空，node取order栈栈顶元素
            stack_Order.pop();       //order栈弹出栈顶元素
            s = node->lChild;        //s指向栈顶元素的左子树
        }
    }
    while (!stack_PostOutput.empty())
    { // output栈 ：入栈顺序：根、右、左，则出栈顺序为后序的顺序：左、右、根
        visit(stack_PostOutput.top());
        stack_PostOutput.pop();
    }
}
后序循环（单栈）

在这里插入图片描述

void PostOrder_Loop_new_singleStack(BiTree T)
{
    /*后序遍历：循环办法，只用一个栈实现*/
    ClearStack(&stack_Order);
    BiTree s = T; //作为遍历指针
    BiTree node;  //指向栈顶节点
    BiTree prior_node = nullptr; //指向前一个刚刚访问过的指针

    while(s!=nullptr || !stack_Order.empty()){
        if(s != nullptr)
        {
            stack_Order.push(s);//s不空，则入栈
            s = s->lChild;      //s一路向左
        }
        else
        {
            node = stack_Order.top();//当s为空时，node取栈顶元素
            if(node->rChild && node->rChild != prior_node)
            {//若栈顶元素的右子树存在且尚未被访问过，则s转向栈顶元素node的右子树
                s = node->rChild;
            }
            else
            {
                visit(node);      //若其没有右子树或者其右子树已经访问过了，访问node栈顶元素本身
                stack_Order.pop();//弹出栈顶元素node
                prior_node = node;//将node元素设为刚刚访问的元素
                s = nullptr;      //s被置空
            }
        }
    }
}
层序循环（队列）

在这里插入图片描述

void levelOrder_new(BiTree T)
{
    /*层序遍历：利用队列搜索*/
    ClearQueue(&queue_LevelOrder);
    if (T != nullptr)
    {
        queue_LevelOrder.push(T);
    }
    while (!queue_LevelOrder.empty())
    {
        //s出队，s的左右子树顺序入队，访问出队的s,实现层序遍历
        BiTree s = queue_LevelOrder.front();
        queue_LevelOrder.pop();
        if (s->lChild != nullptr)
        {
            queue_LevelOrder.push(s->lChild);
        }
        if (s->rChild != nullptr)
        {
            queue_LevelOrder.push(s->rChild);
        }
        visit(s);
    }
}

源代码验证实现

//
// Created by 15328 on 2022/1/26.
//
#include <bits/stdc++.h>
typedef double elementType;//任意给定某个数据类型作为此二叉树的节点的数据类型
using namespace std;
typedef struct BiTNode
{
    elementType data;
    struct BiTNode *lChild, *rChild;
    // struct BiTNode *parent;//父节点指针
} BiTNode, *BiTree;

elementType test_value = 0;

BiTree initTree()
{
    /*初始化一个根节点
     * （或者初始化非根节点的时候调用此函数参与构造）*/
    BiTree root = (BiTree)malloc(sizeof(BiTNode));
    root->data = -1;
    root->lChild = nullptr;
    root->rChild = nullptr;
    return root;
}
BiTree insertBiTree_left(BiTree root, elementType newData)
{
    /*在root节点之后插入新左侧节点*/
    if (root != nullptr)
    {
        BiTree newBiNode = initTree();
        newBiNode->data = newData;
        root->lChild = newBiNode;
        return root->lChild;
    }
    else
    {
        return nullptr;
    }
}
BiTree insertBiTree_right(BiTree root, elementType newData)
{
    /*在root节点之后插入新右侧节点*/
    if (root != nullptr)
    {
        BiTree newBiNode = initTree();
        newBiNode->data = newData;
        root->rChild = newBiNode;
        return root->rChild;
    }
    else
    {
        return nullptr;
    }
}
void visit(BiTree T)
{
    if (T != nullptr)
    {
        /*访问该结点的操作函数*/
        std::cout << T->data << "\t";
    }
    else
    {
        std::cout << "null"
                  << "\t";
    }
}

/*二叉树的先中后序遍历：*/

void PreOrder(BiTree T)
{
    /*先序遍历：递归遍历*/
    if (T != nullptr)
    {
        visit(T);//访问根节点
        PreOrder(T->lChild);//遍历左子树
        PreOrder(T->rChild);//遍历右子树
    }
}
void InOrder(BiTree T)
{
    /*中序遍历：递归遍历*/
    if (T != nullptr)
    {
        InOrder(T->lChild);//遍历左子树
        visit(T);//访问根节点
        InOrder(T->rChild);//遍历右子树
    }
}
void PostOrder(BiTree T)
{
    /*后序遍历：递归办法*/
    if (T != nullptr)
    {
        PostOrder(T->lChild);//遍历左子树
        PostOrder(T->rChild);//遍历右子树
        visit(T);//访问根节点
    }
}

std::stack<BiTree> stack_Order;      /*三种遍历的单栈法都要用到存储栈*/
std::stack<BiTree> stack_PostOutput; /*双栈法后序遍历中存储需要输出的遍历序列*/
std::queue<BiTree> queue_LevelOrder; /*层序遍历中利用队列的先进先出的性质实现层序访问*/

bool ClearStack(std::stack<BiTree>* stack)
{/*清空栈*/
    if (stack != nullptr)
    {
        while (!(*stack).empty())
        {
            (*stack).pop();
        }
        return true;
    }
    else
    {
        return false;
    }
}
bool ClearQueue(std::queue<BiTree>* queue)
{/*清空队列*/
    if (queue != nullptr)
    {
        while (!(*queue).empty())
        {
            (*queue).pop();
        }
        return true;
    }
    else
    {
        return false;
    }
}

void PreOrder_Loop(BiTree T)
{
    /*先序遍历：循环办法*/
    BiTree s = T;//设置s为遍历指针
    BiTree node;//设置指针node指向栈顶元素
    ClearStack(&stack_Order);//对栈做清空操作，使之备用
    while (!stack_Order.empty() || s != nullptr)
    {//当栈为空且同时遍历指针S为空的时候，先序访问结束，退出循环
        if (s != nullptr)
        {
            visit(s);           //访问当前节点
            stack_Order.push(s);//并将其入栈
            s = s->lChild;      //若其左孩子不空，则一直向左走
        }
        else
        {
            node = stack_Order.top();//s为空，取出栈顶元素
            stack_Order.pop();       //栈顶元素出栈
            s = node->rChild;        //转向栈顶元素的右子树
        }
    }
}
void InOrder_Loop(BiTree T)
{
    /*中序遍历：循环办法*/
    BiTree s = T;//设置S为遍历指针
    BiTree node;//设置node指向栈顶元素
    ClearStack(&stack_Order);//对栈做清空操作，使之备用
    while (!stack_Order.empty() || s != nullptr)
    { //当栈为空且同时遍历指针S为空的时候，中序访问结束，退出循环
        if (s != nullptr)
        {
            stack_Order.push(s);//s不空，s入栈
            s = s->lChild;      //左孩子不空，则一直向左走
        }
        else
        {
            node = stack_Order.top();//s为空，node取栈顶元素
            stack_Order.pop();       //栈顶元素出栈
            visit(node);             //访问栈顶元素
            s = node->rChild;        //转向栈顶元素的右子树
        }
    }
}
void PostOrder_Loop(BiTree T)
{
    /*后序遍历：循环办法,两个栈*/
    BiTree s = T; //设置S为遍历指针
    BiTree node;  //设置node指向栈顶元素
    ClearStack(&stack_Order); //对栈做清空操作，使之备用
    ClearStack(&stack_PostOutput); //对栈做清空操作，使之备用
    while (!stack_Order.empty() || s != nullptr)
    { //当栈为空且同时遍历指针S为空的时候，后序访问结束，退出循环
        if (s != nullptr)
        {
            stack_Order.push(s);     //s不空 则s入order栈 
            stack_PostOutput.push(s);//s入output栈 ：入栈顺序：根、右、左，则出栈顺序为后序的顺序：左、右、根
            s = s->rChild;           //若右孩子不空，则一路向右
        }
        else
        {
            node = stack_Order.top();//s为空，node取order栈栈顶元素
            stack_Order.pop();       //order栈弹出栈顶元素
            s = node->lChild;        //s指向栈顶元素的左子树
        }
    }
    while (!stack_PostOutput.empty())
    { // output栈 ：入栈顺序：根、右、左，则出栈顺序为后序的顺序：左、右、根
        visit(stack_PostOutput.top());
        stack_PostOutput.pop();
    }
}
void PostOrder_Loop_new_singleStack(BiTree T)
{
    /*后序遍历：循环办法，只用一个栈实现*/
    ClearStack(&stack_Order);
    BiTree s = T; //作为遍历指针
    BiTree node;  //指向栈顶节点
    BiTree prior_node = nullptr; //指向前一个刚刚访问过的指针

    while(s!=nullptr || !stack_Order.empty()){
        if(s != nullptr)
        {
            stack_Order.push(s);//s不空，则入栈
            s = s->lChild;      //s一路向左
        }
        else
        {
            node = stack_Order.top();//当s为空时，node取栈顶元素
            if(node->rChild && node->rChild != prior_node)
            {//若栈顶元素的右子树存在且尚未被访问过，则s转向栈顶元素node的右子树
                s = node->rChild;
            }
            else
            {
                visit(node);      //若其没有右子树或者其右子树已经访问过了，访问node栈顶元素本身
                stack_Order.pop();//弹出栈顶元素node
                prior_node = node;//将node元素设为刚刚访问的元素
                s = nullptr;      //s被置空
            }
        }
    }
}
void levelOrder_old(BiTree root, int level)
{
    /*递归求层序遍历结果（每一层）*/
    if (root == nullptr || level < 1)
    {
        return;
    }
    if (level == 1)
    {
        visit(root);
    }
    levelOrder_old(root->lChild, level - 1);
    levelOrder_old(root->rChild, level - 1);
}
int highLength(BiTree root)
{
    /*递归求树的高度*/
    int l_length = 0;
    int r_length = 0;
    if (root == nullptr)
    {
        return 0;
    }
    else
    {
        l_length = highLength(root->lChild);
        r_length = highLength(root->rChild);
        if (l_length < r_length)
        {
            return r_length + 1;
        }
        else
        {
            return l_length + 1;
        }
    }
}
void levelOrder(BiTree T)
{
    /*递归遍历层序*/
    if (T == nullptr)
    {
        return;
    }
    int depth = highLength(T);
    for (int i = 1; i <= depth; i++)
    {
        levelOrder_old(T, i);
    }
}
void levelOrder_new(BiTree T)
{
    /*层序遍历：利用队列搜索*/
    ClearQueue(&queue_LevelOrder);
    if (T != nullptr)
    {
        queue_LevelOrder.push(T);
    }
    while (!queue_LevelOrder.empty())
    {
        //s出队，s的左右子树顺序入队，访问出队的s,实现层序遍历
        BiTree s = queue_LevelOrder.front();
        queue_LevelOrder.pop();
        if (s->lChild != nullptr)
        {
            queue_LevelOrder.push(s->lChild);
        }
        if (s->rChild != nullptr)
        {
            queue_LevelOrder.push(s->rChild);
        }
        visit(s);
    }
}
void test()
{
    BiTree root = initTree();
    BiTree root1 = root;
    srand(time(nullptr));
    /*用当前时间设置一个随机数种子*/
    root->data = 5779*5607%100;
    for (int i = 1; i < 3; i++)
    {
        test_value = rand() % 100;
        //获取一百以内elementType类型随机数
        root1 = insertBiTree_left(root1, test_value);
        test_value = rand() % 100;
        root1 = insertBiTree_right(root1, test_value);
    }
    root1 = root;
    for (int i = 1; i < 3; i++)
    {
        test_value = rand() % 100;
        root1 = insertBiTree_right(root1, test_value);
        test_value = rand() % 100;
        root1 = insertBiTree_left(root1, test_value);
    }
    /*BiTree root2 = root;
    root1 = insertBiTree_left(root1,2);
    root2 = insertBiTree_right(root2,5);
    root2 = root1;
    root1 = insertBiTree_left(root1,3);
    root2 = insertBiTree_right(root2,4);*/
    std::cout << "先序递归：      ";
    PreOrder(root);
    std::cout << endl;
    std::cout << "中序递归：      ";
    InOrder(root);
    std::cout << endl;
    std::cout << "后序递归：      ";
    PostOrder(root);
    std::cout << endl;
    std::cout << "层序递归：      ";
    levelOrder(root);
    std::cout << endl;
    std::cout << "先序循环：      ";
    PreOrder_Loop(root);
    std::cout << endl;
    std::cout << "中序循环:       ";
    InOrder_Loop(root);
    std::cout << endl;
    std::cout << "后序循环(双栈): ";
    PostOrder_Loop(root);
    std::cout << endl;
    std::cout << "后序循环(单栈): ";
    PostOrder_Loop_new_singleStack(root);
    std::cout << endl;
    std::cout << "层序循环：      ";
    levelOrder_new(root);
    std::cout << std::endl;
}

int main()
{
    test();
}

验证结果

在这里插入图片描述

# 数据结构 # cocos2d
Logo
开放原子开发者工作坊

开放原子开发者工作坊旨在鼓励更多人参与开源活动，与志同道合的开发者们相互交流开发经验、分享开发心得、获取前沿技术趋势。工作坊有多种形式的开发者活动，如meetup、训练营等，主打技术交流，干货满满，真诚地邀请各位开发者共同参与！

更多推荐

第二届开放原子大赛首批创新成果集结武汉，诚邀广大开发者共鉴开源技术盛宴

第二届开放原子大赛首批创新成果集结武汉，诚邀广大开发者共鉴开源技术盛宴

avatar 开放原子开发者工作坊

诚邀报名 | 开源基础设施能力建设分论坛：打造开源生态的“心脏”

诚邀报名 | 开源基础设施能力建设分论坛：打造开源生态的“心脏”

avatar 开放原子开发者工作坊

诚邀报名 | 编程语言分论坛：AI时代的技术革新与开源实践

诚邀报名 | 编程语言分论坛：AI时代的技术革新与开源实践

avatar 开放原子开发者工作坊