当前位置： 首页 > news >正文

二叉树--递归遍历--层次遍历--非递归遍历--详解

news 2025/5/14 11:22:01


//数据结构--树-------------------------------------------------------------------------
// 树是一个n个结点的有限集，n为0时，为空树
// 1.树的定义是递归的，即定义中用到了自身
// 2.树的根节点没有前驱，其他所有结点有且只有一个前驱
// 3.树中的所有结点有0个或者多个后驱
//二叉树--------------------------------------------------
// 1.一种特殊的数据结构
// 2.每个结点只有两个子树
// 遍历方式：
// 根节点的遍历顺序 前 中 后
// 前序 根->左->右
// 中序 左->根->右
// 后序 左->右->根
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
创建一个结点
typedef struct TreeNode
{
    char data;
    struct TreeNode* Lchild;//左子串
    struct TreeNode* Rchild;//右子串
}TreeNode;
//创建二叉树--先序
void createTree(TreeNode** T,int *index)
//要改变树中的内容，需要传二级指针,
//data --数据  index--索引
{
    //获取一个数据
    char ch;
    scanf("%c", &ch);
    *index += 1;//计数，计算data的长度
    //如果输入的是# 则为空结点
    if (ch == '#')
    {
        *T = NULL;
    }
    //不是空结点
    else
    {
        //给T开辟空间
        *T = (TreeNode*)malloc(sizeof(TreeNode));
        //给data赋值
        (*T)->data = ch;
        //创建两个子树.引用创建树的函数本身，逻辑一致，进行递归
        //左子树
        createTree(&((*T)->Lchild),index);
        //右子树
        createTree(&((*T)->Rchild),index);
    }
}
//前序遍历
void preOrder(TreeNode* T)
{
    //如果为空
    if (T == NULL)
    { 
        return;
    }
    else
    {
        //先输出根数据
        printf("%c ", T->data);
        //输出左子树
        preOrder(T->Lchild);
        //输出右子树
        preOrder(T->Rchild);
    }
}
//中序遍历
void inOrder(TreeNode* T)
{
    //如果为空
    if (T == NULL)
    {
        return;
    }
    else
    {
        //输出左子树
        inOrder(T->Lchild);
        //输出根数据
        printf("%c ", T->data);
        //输出右子树
        inOrder(T->Rchild);
    }

}
//后序遍历
void postOrder(TreeNode* T)
{
    //如果为空
    if (T == NULL)
    {
        return;
    }
    else
    {
        //输出左子树
        postOrder(T->Lchild);
        //输出右子树
        postOrder(T->Rchild);
        //输出根数据
        printf("%c ", T->data);
    }
}
int main()
{
    TreeNode* T;
    int index = 0;
    createTree(&T, &index);
    preOrder(T);
    printf("\n");
    inOrder(T);
    printf("\n");
    postOrder(T);
    return 0;
}
//二叉树层次遍历--------------------------------------------------
// 按层遍历：利用队列先进先出原则，一层一层出栈
//创建一个树结点
typedef struct TreeNode
{
    char data;
    struct TreeNode* Lchild;//左子串
    struct TreeNode* Rchild;//右子串
}TreeNode;
//创建一个链式队列结点
typedef struct QueNode
{
    TreeNode* data;
    struct QueNode* prev;
    struct QueNode* next;
}QueNode;
//创建一个树
void createTree(TreeNode** T,int *index)
//要改变树中的内容，需要传二级指针,
//data --数据  index--索引
{
    //获取一个数据
    char ch;
    scanf("%c", &ch);
    *index += 1;//计数，计算data的长度
    //如果输入的是# 则为空结点
    if (ch == '#')
    {
        *T = NULL;
    }
    //不是空结点
    else
    {
        //给T开辟空间
        *T = (TreeNode*)malloc(sizeof(TreeNode));
        //给data赋值
        (*T)->data = ch;
        //创建两个子树.引用创建树的函数本身，逻辑一致，进行递归
        //左子树
        createTree(&((*T)->Lchild),index);
        //右子树
        createTree(&((*T)->Rchild),index);
    }
}
前序遍历检查
void preOrder(TreeNode* T)
{
    //如果为空
    if (T == NULL)
    { 
        return;
    }
    else
    {
        //先输出根数据
        printf("%c ", T->data);
        //输出左子树
        preOrder(T->Lchild);
        //输出右子树
        preOrder(T->Rchild);
    }
}
//建立队列头结点--使用双头循环链表
QueNode* InitQueue()
{
    QueNode* Q = (QueNode*)malloc(sizeof(QueNode));
    Q->data = NULL;
    Q->prev = Q;
    Q->next = Q;

    return Q;
}
//入队
void EnQueue(QueNode* Q,TreeNode* data)
{
    //创建一个队员结点
    QueNode* node = (QueNode*)malloc(sizeof(QueNode));
    //data赋值
    node->data = data;
    //尾插
    //prev指向队尾成员
    node->prev = Q->prev;
    //next指向头结点
    node->next = Q;
    //头结点指向的队尾成员的next指向node
    Q->prev->next = node;
    //头结点的prev指向node，成为新的队尾
    Q ->prev = node;
}
//判断是否为空
int IsEmpty(QueNode* Q)
{
    return Q->next == Q;//为空返回true，不为空返回false
}
//出队
QueNode* DeQueue(QueNode* Q)
{
    assert(!IsEmpty(Q));//断言是否为空
    //不为空
    //出队
    QueNode* Qnode = Q->next;//记录队头出队的结点
    Q->next = Qnode->next;//头结点指向出队数据的下一个结点
    Qnode->next->prev = Q;//出队数据的下一个结点的prev指向头结点
    //返回node
    return Qnode;
}
//层次遍历
void levelTraverse(QueNode* Q, TreeNode* T)
{
    //根节点入队
    EnQueue(Q, T);
    //不为空,按层次遍历访问，直到队列为空
    while (!IsEmpty(Q))
    {
        //出队
        QueNode* Qnode = DeQueue(Q);
        //打印指向树结点的数据
        printf("%c ", Qnode->data->data);
        //如果入队的根结点的左子树不为空,继续入队
        if (Qnode->data->Lchild)
        {
            EnQueue(Q, Qnode->data->Lchild);
        }
        //如果入队的根结点的右子树不为空,继续入队
        if (Qnode->data->Rchild)
        {
            EnQueue(Q, Qnode->data->Rchild);
        }
    }
    printf("\n");
}
int main()
{
    TreeNode* T;
    int index = 0;
    QueNode* Q = InitQueue();
    createTree(&T, &index);
    preOrder(T);
    levelTraverse(Q, T);

    return 0;
}
//二叉树非递归遍历---------------------------------------------------------------------
//利用栈的后进先出规则
// 前序
// 1.先访问，再入栈
// 2.循环，直到左子树为NULL
// 3.出栈，访问结点，入栈右子树
//
// 中序
// 1.先入栈
// 2.循环，直到左子树为NULL
// 3.出栈，再访问结点，入栈右子树
// 
// 后续
// 1.先入栈
// 2.循环，直到左子树为NULL
// 3.判断此时右子树是否为空，且是否被访问过，不为空且未被访问过则入栈
// 4.当左右子树为空时，则出栈，进行访问
// 
// 层层退出
//创建树的结点
typedef struct TreeNode
{
    char data;
    struct TreeNode* Lchild;
    struct TreeNode* Rchild;
}TreeNode;
//创建栈
typedef struct StackNode
{
    TreeNode* data;
    struct StackNode* next;
}StackNode;
//创建一个树
void createTree(TreeNode** T, int* index)
//要改变树中的内容，需要传二级指针,
//data --数据  index--索引
{
    //获取一个数据
    char ch;
    scanf("%c", &ch);
    *index += 1;//计数，计算data的长度
    //如果输入的是# 则为空结点
    if (ch == '#')
    {
        *T = NULL;
    }
    //不是空结点
    else
    {
        //给T开辟空间
        *T = (TreeNode*)malloc(sizeof(TreeNode));
        //给data赋值
        (*T)->data = ch;
        //创建两个子树.引用创建树的函数本身，逻辑一致，进行递归
        //左子树
        createTree(&((*T)->Lchild), index);
        //右子树
        createTree(&((*T)->Rchild), index);
    }
}
//初始化栈
StackNode* InitStack()
{
    StackNode* S = (StackNode*)malloc(sizeof(StackNode));
    S->data = NULL;
    S->next = NULL;
    return S;
}
//入栈
void PushStack(StackNode* S, TreeNode* data)
{
    //创建一个栈的新结点
    StackNode* node = (StackNode*)malloc(sizeof(StackNode));
    //赋值
    node->data = data;
    //头插
    //新节点的next指向->头结点指向的下一个结点
    node->next = S->next;
    //头结点指向新节点
    S->next = node;
}
//判断栈是否为空
int IsEmpty(StackNode* S)
{
    //为空返回真，不为空返回假
    return S->next == NULL;
}
//出栈
StackNode* PopStack(StackNode* S)
{
    //如果栈为空
    if (IsEmpty(S))
    {
        return NULL;
    }
    else
    {
        //出栈
        StackNode* node = S->next;
        //头结点指向下一个结点
        S->next = node->next;
        //返回Node
        return node;
    }
}
//递归遍历检查
void preOrder(TreeNode* T)
{
    //如果为空
    if (T == NULL)
    {
        return;
    }
    else
    {
        //先输出根数据
        printf("%c ", T->data);
        //输出左子树
        preOrder(T->Lchild);
        //输出右子树
        preOrder(T->Rchild);
    }
}
//非递归前序遍历
void PreOrder(TreeNode* T)
{
    //创建变量接收T
    TreeNode* node = T;
    //创建一个栈
    StackNode* S = InitStack();
    //当node不为空，或者栈不为空，执行循环
    while (node || !IsEmpty(S))
    {
        //树结点不为空
        if (node)
        {
            //先访问
            printf("%c ", node->data);
            //入栈
            PushStack(S, node);
            //node往后从左子树迭代，进入深层，直到左子树为空
            node = node->Lchild;
        }
        //左子树为空
        else
        {
            //出栈,用node记录出栈树结点
            node = PopStack(S)->data;
            //node迭代到出栈树节点的右子树，不为空就可入栈，为空则继续出栈
            //将node指向上一层的结点，便可继续遍历右子树，层层退出来
            node = node->Rchild;
        }
    }
}
//非递归中序遍历
void InOrder(TreeNode* T)
{
    //创建变量接收T
    TreeNode* node = T;
    //创建一个栈
    StackNode* S = InitStack();
    //当node不为空，或者栈不为空，执行循环
    while (node || !IsEmpty(S))
    {
        //树结点不为空
        if (node)
        {
            //先入栈
            PushStack(S, node);
            //node往后从左子树迭代，进入深层，直到左子树为空
            node = node->Lchild;
        }
        //左子树为空
        else
        {
            //出栈,用node记录出栈树结点
            node = PopStack(S)->data;
            //出栈后再访问
            printf("%c ", node->data);
            //node迭代到出栈树节点的右子树，不为空就可入栈，为空则继续出栈
            //将node指向上一层的结点，访问后，便可继续遍历右子树，层层退出来
            node = node->Rchild;
        }
    }
}
//非递归后序遍历
typedef struct TreeNode
{
    char data;
    struct TreeNode* Lchild;
    struct TreeNode* Rchild;
    int flag;//后序中需要判断右子树是否为空，且是否被访问过，做一个标识，如果访问过为1
    //没有访问过需要入栈
}TreeNode;
//创建栈
typedef struct StackNode
{
    TreeNode* data;
    struct StackNode* next;
}StackNode;
//创建一个树
void createTree(TreeNode** T, int* index)
//要改变树中的内容，需要传二级指针,
//data --数据  index--索引
{
    //获取一个数据
    char ch;
    scanf("%c", &ch);
    *index += 1;//计数，计算data的长度
    //如果输入的是# 则为空结点
    if (ch == '#')
    {
        *T = NULL;
    }
    //不是空结点
    else
    {
        //给T开辟空间
        *T = (TreeNode*)malloc(sizeof(TreeNode));
        //给data赋值
        (*T)->data = ch;
        //
        (*T)->flag = 0;

        //创建两个子树.引用创建树的函数本身，逻辑一致，进行递归
        //左子树
        createTree(&((*T)->Lchild), index);
        //右子树
        createTree(&((*T)->Rchild), index);
    }
}
//初始化栈
StackNode* InitStack()
{
    StackNode* S = (StackNode*)malloc(sizeof(StackNode));
    S->data = NULL;
    S->next = NULL;
    return S;
}
//入栈
void PushStack(StackNode* S, TreeNode* data)
{
    //创建一个栈的新结点
    StackNode* node = (StackNode*)malloc(sizeof(StackNode));
    //赋值
    node->data = data;
    //头插
    //新节点的next指向->头结点指向的下一个结点
    node->next = S->next;
    //头结点指向新节点
    S->next = node;
}
//判断栈是否为空
int IsEmpty(StackNode* S)
{
    //为空返回真，不为空返回假
    return S->next == NULL;
}
//出栈
StackNode* PopStack(StackNode* S)
{
    //如果栈为空
    if (IsEmpty(S))
    {
        return NULL;
    }
    else
    {
        //出栈
        StackNode* node = S->next;
        //头结点指向下一个结点
        S->next = node->next;
        //返回Node
        return node;
    }
}
//获取栈顶数据
StackNode* GetTop(StackNode* S)
{
    if (IsEmpty(S))
    {
        return NULL;
    }
    else
    {
        //取值
        StackNode* node = S->next;
        //返回
        return node;
    }
}
//非递归后续遍历
void PostOrder(TreeNode*T)
{
    //创建变量接收T
    TreeNode* node = T;
    //创建栈
    StackNode* S = InitStack();
    //当node不为空，或者栈不为空，执行循环
    while(node|| !IsEmpty(S))
    {
        if (node)
        {
            //入栈
            PushStack(S, node);
            //node往后迭代,左子树入栈，直到node为NULL；
            node = node->Lchild;
        }
        //当左子树为空
        else
        {
            //获取栈顶数据
            TreeNode* top = GetTop(S)->data;
            //如果栈顶数据的右子树不为空，且未被访问过
            if (top->Rchild && top->Rchild->flag == 0)
            {
                //将top指向右子树
                top = top->Rchild;
                //入栈右子树
                PushStack(S, top);
                //node往后迭代，直到左子树为NULL
                node = top->Lchild;
            }
            //右子树为空，此时左右子树皆为NULL
            else
            {
                //出栈
                top = PopStack(S)->data;
                //访问
                printf("%c ", top->data);
                //标识被访问过
                top->flag = 1;
            }
        }
    }
}

int main()
{
    TreeNode* T;
    int index = 0;
    createTree(&T,&index);
    /*preOrder(T);
    printf("\n");
    PreOrder(T);
    printf("\n");
    InOrder(T);
    printf("\n");*/
    PostOrder(T);
    return 0;
}


http://www.mrgr.cn/news/16148.html

相关文章：

  • 500Kg载重无线遥控履带式无人车技术详解
  • Python tuple元数据操作：提升你的数据处理能力
  • [Day 68] 區塊鏈與人工智能的聯動應用：理論、技術與實踐
  • cannot import name ‘greycomatrix‘ from ‘skimage.feature.texture‘ 解决方法
  • YoloV8实战：数据集制作|两种高效的Labelme转Yolo脚本|适用于YoloV5、V7、V8、V9、V10
  • 电子检测报告如何盖骑缝章？
  • 存储 IO 性能优化策略、方案与瓶颈分析
  • 学院个人信息|基于SprinBoot+vue的学院个人信息管理系统(源码+数据库+文档)
  • 你真的理解编程语言里的数据相等吗
  • JavaScript练习（一）
  • Python使用OpenCV识别图片人脸
  • 成都高温限电：当电动汽车「无电可充」
  • 【高中数学\基本不等式】已知a,b皆为正数，且2/(a+2)+1/(a+2b)=1,则a+b的最小值是多少，此时a等于几？
  • 如何打造免费体育馆场地预约系统？php vue技术实现，简易操作指南
  • ChatGPT、Claude 和 Gemini 在数据分析方面的合作（第 3 部分）：机器学习的最佳 AI 助手
  • Windows中pip换源
  • Codeforces Round 969 (Div. 2)
  • 让PDF格式为LLM应用做好准备：探索Marker开源工具
  • Halcon轮廓的生成
  • springbootmybatis中数组和字符串数据类型的转换