数据结构代码集训day17（适合考研、自学、期末和专升本）

news/2025/1/15 21:49:13/

习题来自B站up：白话拆解数据结构

今日习题如下：

1、写出二叉树的前、中、后序遍历

2、写出二叉树的非递归前序和中序遍历

        二叉树有多种存储结构：双亲存储法、孩子兄弟链存储结构，二叉链表存储结构等，一般我们写代码题都用的二叉链表：

typedef struct Bitnode{

    int data;

    struct Bitnode *lchild,*rchild;

}Bitnode,* Bitree;

        如上所示，有三个域，一个数据域，一个左孩子指针域，一个右孩子指针域。对于m叉链表来说，有一个数据域，m个指针域，指针域非空的个数对应该结点的度。下图是一个四叉链表示意图：

题1 

        对于二叉树的前序遍历，我们可以采取递归的做法，因为前序遍历是PLR，所以我们先打印根结点的值，再递归左子树，然后再递归右子树就行了。

    void preorder(Bitree T){    //PLR

        if(T!=NULL){

            printf("%d ",T->data);

           

            preorder(T->lchild);

            preorder(T->rchild);

        }

    }

        对于这种递归的题目，可以采取抽象的方法，下面是一个最简单的二叉树模型：

        对于稍复杂的二叉树，我们可以把他抽象成上述模型，左边的是根结点的左子树，右边是根结点的右子树。

         然后递归左子树preorder(T->lchild)部分，就是把左子树当成一棵新的树，然后把这个新的树再次抽象，一直递归下去！本题的递归出口是T==NULL。

        能理解上述部分，那中序和后序也是一样的，代码如下：

    void inorder(Bitree T){     //LPR

        if(T!= NULL){

            inorder(T->lchild);

           

            printf("%d ",T->data);

            inorder(T->rchild);

        }

    }

    void postorder(Bitree T){       //LRP

        if(T!=NULL){

            postorder(T->lchild);

            postorder(T->rchild);

            printf("%d ",T->data);  

        }

    }

        下面我们来造一个例子，这里采用二叉排序树的递归造法，如下所示：

Bitree createnode(int data){        // 造结点

    Bitree T=(Bitree)malloc(sizeof(Bitnode));

    if (T!=NULL){

        T->data = data;

        T->lchild=NULL;

        T->rchild=NULL;

    }

    return T;

}

Bitree insertnode(Bitree T,int data){        // 二叉排序树插入结点

    if(T==NULL){

        return createnode(data);

    }

    if(data<T->data)

        T->lchild=insertnode(T->lchild,data);

    else if(data>T->data)

        T->rchild=insertnode(T->rchild,data);

    return T;

}

         我们来造这么一棵二叉树：

         我们运行一下：验证是否成功就看中序序列是否有序就行了。

         完整代码如下：

#include <iostream>
#include <cstdio>#include <ctime>
using namespace std;typedef struct Bitnode{int data;struct Bitnode *lchild,*rchild;
}Bitnode,* Bitree;Bitree createnode(int data){Bitree T=(Bitree)malloc(sizeof(Bitnode));if (T!=NULL){T->data = data;T->lchild=NULL;T->rchild=NULL;}return T;
}Bitree insertnode(Bitree T,int data){if(T==NULL){return createnode(data);}if(data<T->data)T->lchild=insertnode(T->lchild,data);else if(data>T->data)T->rchild=insertnode(T->rchild,data);return T;
}// 前中后序遍历
class Solution{
public:void preorder(Bitree T){    //PLRif(T!=NULL){printf("%d ",T->data);preorder(T->lchild);preorder(T->rchild);}}void inorder(Bitree T){     //LPRif(T!= NULL){inorder(T->lchild);printf("%d ",T->data);inorder(T->rchild);}}void postorder(Bitree T){       //LRPif(T!=NULL){postorder(T->lchild);postorder(T->rchild);printf("%d ",T->data);  }}
};int main(){Bitree T=NULL;T=insertnode(T,10);T=insertnode(T,7);T=insertnode(T,8);T=insertnode(T,6);T=insertnode(T,12);T=insertnode(T,14);T=insertnode(T,11);Solution s;printf("preorder is:");s.preorder(T);printf("\n");printf("inorder is:");s.inorder(T);printf("\n");printf("postorder is:");s.postorder(T);printf("\n");return 0;}

题2

        非递归一般要借助栈，对于非递归前序遍历二叉树，这个栈实际上是个指针类型的栈，里面存的是指针；借助上面那个图来说明，我们先将T指针（指向根节点的指针）入栈。

         根据前序遍历的特点，根左右，我们入根结点后，立马出栈（需要有一个辅助指针始终指向栈顶），由于temp先指向的T，此时T出栈了，temp依然指向T，根据栈后进先出的特点，我们需要先入temp的右孩子，再入他的左孩子，这样能保持在进入下一轮循环时temp指向左孩子，如下图所示：（10已出栈）。

         下一轮循环开始，我们先出栈栈顶指针，然后重复，先压入temp指针右孩子，再左孩子（7已出栈）。

        此时temp左右孩子都没了，到下一轮直接出栈就行，先出6再出8，最后回退到了12，就开始右子树的遍历了，过程一致。代码如下：

 void preorder_nodigui(Bitree T){

        if(T==NULL)     return;

        stack<Bitree> s;        // 栈存的类型是Bitree指针

        s.push(T);        

        while(!s.empty()){

            Bitnode *temp=s.top();        // 每一轮循环temp指向栈顶

            printf("%d ",temp->data);        

            s.pop();        // 出栈

            if(temp->rchild!=NULL)

                s.push(temp->rchild);

            if(temp->lchild!=NULL)

                s.push(temp->lchild);

        }

    }

        然后是非递归中序遍历，根据LPR的特点，我们需要先将所有的左入栈，同样借助栈，还需要一个辅助指针current， current指针往左下走，将其压栈，直到为空。current指针也需要一直指向栈顶。

        然后我们出栈，先出6，因为6没有孩子，根据LPR原则，直接出P就行！然后current指针就指向7了，把7出栈，因为对于根结点的左子树部分，L已经访问完了，该P部分了，但是7有右孩子，将其右孩子压栈，再出栈（因为8没有孩子）。至此T的左子树部分全部遍历完了，指针也刚好回退到10这里，对于这整棵树，L部分已经完了，该P了，10出栈，然后10有右孩子，将右孩子12入栈，再重复上述过程（入11，出11，出12，入14，出14）。

    void inorder_nodigui(Bitree T){

        if(T==NULL)     return;

        stack<Bitree> s;

        Bitnode *current=T;

        while(current||!s.empty()){

            while(current!=NULL)

            {

                s.push(current);

                current=current->lchild;

            }

            current=s.top();

            printf("%d ",current->data);

            s.pop();

            current = current->rchild;

        }

    }

实践一下：还是可以通过中序序列来判断是否做对。

 

完整代码如下：

#include <iostream>
#include <cstdio>
#include <stack>
#include <ctime>
using namespace std;typedef struct Bitnode{int data;struct Bitnode *lchild,*rchild;
}Bitnode,* Bitree;Bitree createnode(int data){Bitree T=(Bitree)malloc(sizeof(Bitnode));if (T!=NULL){T->data = data;T->lchild=NULL;T->rchild=NULL;}return T;
}Bitree insertnode(Bitree T,int data){if(T==NULL){return createnode(data);}if(data<T->data)T->lchild=insertnode(T->lchild,data);else if(data>T->data)T->rchild=insertnode(T->rchild,data);return T;
}class Solution{
public:void preorder_nodigui(Bitree T){if(T==NULL)     return;stack<Bitree> s;s.push(T);while(!s.empty()){Bitnode *temp=s.top();printf("%d ",temp->data);s.pop();if(temp->rchild!=NULL)s.push(temp->rchild);if(temp->lchild!=NULL)s.push(temp->lchild);}}void inorder_nodigui(Bitree T){if(T==NULL)     return;stack<Bitree> s;Bitnode *current=T;while(current||!s.empty()){while(current!=NULL){s.push(current);current=current->lchild;}current=s.top();printf("%d ",current->data);s.pop();current = current->rchild;}}
};int main(){Bitree T=NULL;T=insertnode(T,10);T=insertnode(T,7);T=insertnode(T,8);T=insertnode(T,6);T=insertnode(T,12);T=insertnode(T,14);T=insertnode(T,11);Solution s;printf("preorder is:");s.preorder_nodigui(T);printf("\n");printf("inorder is:");s.inorder_nodigui(T);printf("\n");}

 


http://www.ppmy.cn/news/1521397.html

相关文章

Android之LiveTemplate注释模板

Android之LiveTemplate注释模板

目录 效果图步骤 效果图 步骤 1.首先通过File->Setting->Editor->LiveTemplate 我是放在Android下的&#xff0c;然后点击右侧&#xff08;新版本的话不在右侧&#xff09;加号&#xff0c; 点击&#xff08;加号&#xff09;之后&#xff0c;如图 /*** author:T…
阅读更多...
什么是上下文管理器

什么是上下文管理器

1. 什么是上下文管理器？ 上下文管理器是一个帮助你自动管理资源的工具。最常见的例子是文件操作，通常我们需要打开文件并确保在使用完之后关闭文件。上下文管理器可以帮我们自动处理这些步骤。 2. 最简单的上下文管理器例子 使用 with 语句来简化文件的打开和关闭操作： …
阅读更多...
基于STM32的猫狗宠物喂养系统设计(微信小程序)(215)

基于STM32的猫狗宠物喂养系统设计(微信小程序)(215)

文章目录 一、前言1.1 项目介绍【1】项目功能介绍【2】设计实现的功能【3】项目硬件模块组成1.2 设计思路【1】整体设计思路【2】ESP8266工作模式配置1.3 项目开发背景【1】选题的意义【2】可行性分析【3】参考文献【4】摘要【5】选题背景【6】国内外技术发展现状【7】研究的目…
阅读更多...
学习node.js十三，文件的上传于下载

学习node.js十三，文件的上传于下载

文件上传 文件上传的方案&#xff1a; 大文件上传&#xff1a;将大文件切分成较小的片段&#xff08;通常称为分片或块&#xff09;&#xff0c;然后逐个上传这些分片。这种方法可以提高上传的稳定性&#xff0c;因为如果某个分片上传失败&#xff0c;只需要重新上传该分片而…
阅读更多...
IDEA2024.2最新工具下载

IDEA2024.2最新工具下载

​软件使用 1、解压缩包 2、打开如图第三个 3、运行过十来秒等待提示以下信息即可
阅读更多...
如何认清自己--三观篇

如何认清自己--三观篇

目录 三观的重要性 一、世界观 二、人生观 三、价值观 三观的重要性 “三观”是指世界观、人生观和价值观&#xff0c;它们是一个人对世界、生命和价值的根本看法和态度。三观对于个人和社会都具有极其重要的意义&#xff1a; 世界观&#xff1a;这是人们对整个世界的总体…
阅读更多...
前端知识HTMLCSS

前端知识HTMLCSS

目录 1. 前端开发介绍 1.1 认识前端开发 1.2 web标准 2. HTML & CSS 2.1 HTML快速入门 2.1.1 操作 2.1.2 总结 2.2 开发工具 2.3 基础标签 & 样式 2.3.1 标题实现 2.3.1.1 标题排版 2.3.1.1.1 分析 2.3.1.1.2 标签 2.3.1.1.2 实现 2.3.1.2 标题样式 2.…
阅读更多...
pdf转cad软件，5款快速上手转换软件分享

pdf转cad软件，5款快速上手转换软件分享

在当今快节奏的工作环境中&#xff0c;图纸文件的格式转换成为设计师、工程师等职业群体日常工作中不可或缺的一环。尤其是将PDF文件转换为CAD格式&#xff0c;不仅能够提升工作效率&#xff0c;还能确保设计数据的准确性和可编辑性。下面给大家分享5款能够快速上手转换软件&am…
阅读更多...
最新文章

Copyright @ 2022~2023