二叉树前中后序遍历代码实现

2024-08-23 23:08
文章标签 代码 二叉树 遍历 实现 后序 前中

本文主要是介绍二叉树前中后序遍历代码实现，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

 二叉树的递归遍历实现起来比较简单，而且代码简洁；而非递归遍历则不那么简单，我们需要借助另一种数据结构---栈来实现。二叉树的遍历又可以分为前序、中序和后序三种，它们是按照根结点在遍历时的位置划分的，前序遍历则根结点先被遍历，中序则根结点在左右叶子节点之间被遍历，后序则是根结点最后被遍历。三种非递归遍历中，前序和中序都不是太复杂，而后序遍历则相对较难。


一、前序遍历

        我们这里前序遍历按照“根-左-右”的顺序来遍历。这里按照”递归--非递归“的次序来研究，之后的几种亦是如此。

        1、递归的实现：

[cpp]  view plain copy 在CODE上查看代码片 派生到我的代码片
  1. void travel_3(node* r) {  
  2.         if (r != NULL) {  
  3.             cout << r->key << ' ';  
  4.             travel_3(r->left);  
  5.             travel_3(r->right);  
  6.         }  
  7.     }  


        2、非递归的实现：

        非递归的实现中肯定是需要用到循环结构的，前序遍历又要求先根后左然后右，所以我们肯定是首先需要遍历左节点的，但是遍历左节点之后还需要我们继续遍历右节点，而且右节点也有可能还有左子树需要先遍历。于是乎，这里我们需要一个栈来保存我们已经遍历完的节点，在遍历完左右的左节点之后，再将栈里保存的节点出栈，然后再遍历节点的右子树，然后将右子树的节点带入循环中，这样比较底层的节点会靠近栈顶，也会被先出栈，如此就可以实现非递归的前序遍历。具体步骤如下：


        ①先输出节点的值，然后将节点入栈


        ②然后判断节点的左子节点是否为空，如果不为空，则继续循环①；如果为空，则证明这一条线路上的节点值已经被遍历完了，则跳出循环进行出栈操作，只要栈不为空，则节点出栈，并让节点等于他的右子节点，继续进行①号循环


        ③直到所有节点都已经出栈，且循环到节点为空，则遍历结束


[cpp]  view plain copy 在CODE上查看代码片 派生到我的代码片
  1. void travel_4(node* r) {  
  2.     if (r != NULL) {  
  3.         stack<node*> s;  
  4.         while (r != NULL || !s.empty()) {  
  5.             while (r != NULL) {  
  6.                 cout << r->key << ' ';  
  7.                 s.push(r);  
  8.                 r = r->left;  
  9.             }  
  10.   
  11.             if (!s.empty()) {  
  12.                 r = s.top();  
  13.                 s.pop();  
  14.                 r = r->right;  
  15.             }  
  16.         }  
  17.     }  
  18. }  


二、中序遍历

        中序遍历与前序遍历有些类似，只是按照“左-根-右”的顺序遍历。


        1、递归的实现：


[cpp]  view plain copy 在CODE上查看代码片 派生到我的代码片
  1. void travel_1(node* r) {  
  2.     if (r != NULL) {  
  3.         travel_1(r->left);  
  4.         cout << r->key << ' ';  
  5.         travel_1(r->right);  
  6.     }  
  7. }  



        2、非递归的实现：


        非递归的实现中序遍历跟前序遍历的非递归实现差不多，差别只在于输出节点的key值位置变了，不再是在取左子节点之前输出，而是在出栈之后才输出节点的值，这样会从最左边的节点开始输出，然后再是根节点和右边的节点。


        ①直接将节点入栈


        ②然后判断节点的左子节点是否为空，如果不为空，则继续循环①；如果为空，则证明这一条线路上的已经都入栈了，则跳出循环进行出栈操作，只要栈不为空，则节点出栈，输出节点的值，并让节点等于他的右子节点，继续进行①号循环


        ③直到所有节点都已经出栈，且循环到节点为空，则遍历结束


[cpp]  view plain copy 在CODE上查看代码片 派生到我的代码片
  1. void travel_2(node* r) {  
  2.     if (r != NULL) {  
  3.         stack<node*> s;  
  4.         while (r != NULL || !s.empty()) {  
  5.             while (r != NULL) {  
  6.                 s.push(r);  
  7.                 r = r->left;  
  8.             }  
  9.   
  10.             if (!s.empty()) {  
  11.                 r = s.top();  
  12.                 s.pop();  
  13.                 cout << r->key << ' ';  
  14.                 r = r->right;  
  15.             }  
  16.         }  
  17.     }  
  18. }  



三、后序遍历


        后序遍历的递归实现跟之前的没什么差别，但是非递归实现则比较复杂。


        1、递归的实现：


[cpp]  view plain copy 在CODE上查看代码片 派生到我的代码片
  1. void travel_5(node* r) {  
  2.     if (r != NULL) {  
  3.         travel_5(r->left);  
  4.         travel_5(r->right);  
  5.         cout << r->key << ' ';  
  6.     }  
  7. }  


        2、非递归的实现：


        这里我们依旧需要用到栈，但是我们需要保证根结点一定要在左右子节点遍历完之后才被遍历。如何保证这一点呢？可以像下面这样做：


        ①拿到一个节点，先将其入栈，则它一定在比较靠栈底的地方，比较晚出栈


        ②如果这个节点没有左右子节点，则我们大可以直接输出它


        ③如果这个节点有左或者右子节点或者两者都有，那么我们可以再将其左右子节点也入栈


        ④在出栈的时候，我们会发现左右子节点总是在根结点之前出栈，也就是在其之前被遍历，但是还是有问题


        ⑤我们需要在出栈判断到底是只有左节点还是只有右节点或者是两者都有或者是都没有。如果我们发现它左右子节点都为空，则大可直接输出它；或者，如果发现前一个出栈的节点是它的左节点或者右子节点，则也可以输出它。否则，表示这个节点是一个新的节点，我们需要先将其左右子节点入栈。



[cpp]  view plain copy 在CODE上查看代码片 派生到我的代码片
  1. void travel_6(node* r) {  
  2.     if(r==NULL){  
  3.         return;  
  4.     }  
  5.     stack<node*> s;  
  6.     node* current_pointer;  
  7.     node* last_pointer; //记录前一次循环的指针  
  8.   
  9.     s.push(r); //先将根结点压栈  
  10.   
  11.     while (!s.empty()) {  
  12.         current_pointer = s.top(); //每次循环都要更新当前指针为新的栈顶  
  13.   
  14.         if ((current_pointer->left == NULL && current_pointer->right == NULL)  
  15.                 || (last_pointer != NULL  
  16.                         && (last_pointer == current_pointer->left  
  17.                                 || last_pointer == current_pointer->right))) {  
  18.   
  19.             cout << current_pointer->key << ' ';  
  20.             s.pop();  
  21.             last_pointer = current_pointer;  
  22.         } else {  
  23.             if (current_pointer->right != NULL) {  
  24.                 s.push(current_pointer->right);  
  25.             }  
  26.             if (current_pointer->left != NULL) {  
  27.                 s.push(current_pointer->left);  
  28.             }  
  29.         }  
  30.     }  
  31. }  


完整代码：


[cpp]  view plain copy 在CODE上查看代码片 派生到我的代码片
  1. struct node {  
  2.     int key;  
  3.     node* parent;  
  4.     node* left;  
  5.     node* right;  
  6.     node() :  
  7.             key(0), parent(), left(NULL), right(NULL) {  
  8.     }  
  9.   
  10.     node(int k) :  
  11.             key(k), parent(), left(NULL), right(NULL) {  
  12.     }  
  13.   
  14.     ~node() {  
  15.         key = 0;  
  16.     }  
  17. };  
  18.   
  19. class bintree {  
  20.   
  21. public:  
  22.     node* root;  
  23.   
  24.     bintree() :  
  25.             root() {  
  26.     }  
  27.   
  28.     ~bintree() {  
  29.         //做一些清理的工作，防止内存泄露  
  30.         delete_tree(root);  
  31.     }  
  32.   
  33.     void delete_tree(node* p) {  
  34.         if (p != NULL) {  
  35.             node* right = p->right;  
  36.             node* left = p->left;  
  37.             delete_tree(left);  
  38.             delete p;  
  39.             delete_tree(right);  
  40.             p = NULL;  
  41.             right = NULL;  
  42.             left = NULL;  
  43.         }  
  44.     }  
  45.   
  46.       
  47.   
  48.     /* 
  49.      * 中序遍历，递归方式 
  50.      */  
  51.     void travel_1(node* r) {  
  52.         if (r != NULL) {  
  53.             travel_1(r->left);  
  54.             cout << r->key << ' ';  
  55.             travel_1(r->right);  
  56.         }  
  57.     }  
  58.   
  59.     void travel_1() {  
  60.         travel_1(root);  
  61.         cout << endl;  
  62.     }  
  63.   
  64.     /* 
  65.      * 中序遍历，非递归方式 
  66.      */  
  67.     void travel_2(node* r) {  
  68.         if (r != NULL) {  
  69.             stack<node*> s;  
  70.             while (r != NULL || !s.empty()) {  
  71.                 while (r != NULL) {  
  72.                     s.push(r);  
  73.                     r = r->left;  
  74.                 }  
  75.   
  76.                 if (!s.empty()) {  
  77.                     r = s.top();  
  78.                     s.pop();  
  79.                     cout << r->key << ' ';  
  80.                     r = r->right;  
  81.                 }  
  82.             }  
  83.         }  
  84.     }  
  85.   
  86.     void travel_2() {  
  87.         travel_2(root);  
  88.         cout << endl;  
  89.     }  
  90.   
  91.     /* 
  92.      * 前序遍历，递归方式 
  93.      */  
  94.   
  95.     void travel_3(node* r) {  
  96.         if (r != NULL) {  
  97.             cout << r->key << ' ';  
  98.             travel_3(r->left);  
  99.             travel_3(r->right);  
  100.         }  
  101.     }  
  102.     void travel_3() {  
  103.         travel_3(root);  
  104.         cout << endl;  
  105.     }  
  106.   
  107.     /* 
  108.      * 前序遍历，非递归方式 
  109.      */  
  110.     void travel_4(node* r) {  
  111.         if (r != NULL) {  
  112.             stack<node*> s;  
  113.             while (r != NULL || !s.empty()) {  
  114.                 while (r != NULL) {  
  115.                     cout << r->key << ' ';  
  116.                     s.push(r);  
  117.                     r = r->left;  
  118.                 }  
  119.   
  120.                 if (!s.empty()) {  
  121.                     r = s.top();  
  122.                     s.pop();  
  123.                     r = r->right;  
  124.                 }  
  125.             }  
  126.         }  
  127.     }  
  128.   
  129.     void travel_4() {  
  130.         travel_4(root);  
  131.         cout << endl;  
  132.     }  
  133.   
  134.     /* 
  135.      * 后序方式，递归 
  136.      */  
  137.   
  138.     void travel_5(node* r) {  
  139.         if (r != NULL) {  
  140.             travel_5(r->left);  
  141.             travel_5(r->right);  
  142.             cout << r->key << ' ';  
  143.         }  
  144.     }  
  145.   
  146.     void travel_5() {  
  147.         travel_5(root);  
  148.         cout << endl;  
  149.   
  150.     }  
  151.   
  152.     /* 
  153.      * 后序方式，非递归 
  154.      */  
  155.   
  156.     void travel_6(node* r) {  
  157.         if(r==NULL){  
  158.             return;  
  159.         }  
  160.         stack<node*> s;  
  161.         node* current_pointer;  
  162.         node* last_pointer; //记录前一次循环的指针  
  163.   
  164.         s.push(r); //先将根结点压栈  
  165.   
  166.         while (!s.empty()) {  
  167.             current_pointer = s.top(); //每次循环都要更新当前指针为新的栈顶  
  168.   
  169.             if ((current_pointer->left == NULL && current_pointer->right == NULL)  
  170.                     || (last_pointer != NULL  
  171.                             && (last_pointer == current_pointer->left  
  172.                                     || last_pointer == current_pointer->right))) {  
  173.   
  174.                 cout << current_pointer->key << ' ';  
  175.                 s.pop();  
  176.                 last_pointer = current_pointer;  
  177.             } else {  
  178.                 if (current_pointer->right != NULL) {  
  179.                     s.push(current_pointer->right);  
  180.                 }  
  181.                 if (current_pointer->left != NULL) {  
  182.                     s.push(current_pointer->left);  
  183.                 }  
  184.             }  
  185.         }  
  186.     }  
  187.   
  188.     void travel_6() {  
  189.         travel_6(root);  
  190.         cout << endl;  
  191.     }  
  192.   
  193. };  

这篇关于二叉树前中后序遍历代码实现的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/1100753。

相关文章

关于集合与数组转换实现方法

关于集合与数组转换实现方法

《关于集合与数组转换实现方法》：本文主要介绍关于集合与数组转换实现方法,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录1、Arrays.asList()1.1、方法作用1.2、内部实现1.3、修改元素的影响1.4、注意事项2、list.toArray()2.1、方
阅读更多...
使用Python实现可恢复式多线程下载器

使用Python实现可恢复式多线程下载器

《使用Python实现可恢复式多线程下载器》在数字时代,大文件下载已成为日常操作,本文将手把手教你用Python打造专业级下载器,实现断点续传,多线程加速,速度限制等功能,感兴趣的小伙伴可以了解下... 目录一、智能续传：从崩溃边缘抢救进度二、多线程加速：榨干网络带宽三、速度控制：做网络的好邻居四、终端交互
阅读更多...
java实现docker镜像上传到harbor仓库的方式

java实现docker镜像上传到harbor仓库的方式

《java实现docker镜像上传到harbor仓库的方式》：本文主要介绍java实现docker镜像上传到harbor仓库的方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地... 目录1. 前 言2. 编写工具类2.1 引入依赖包2.2 使用当前服务器的docker环境推送镜像2.2
阅读更多...
C++20管道运算符的实现示例

C++20管道运算符的实现示例

《C++20管道运算符的实现示例》本文简要介绍C++20管道运算符的使用与实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧... 目录标准库的管道运算符使用自己实现类似的管道运算符我们不打算介绍太多，因为它实际属于c++20最为重要的
阅读更多...
Java easyExcel实现导入多sheet的Excel

Java easyExcel实现导入多sheet的Excel

《JavaeasyExcel实现导入多sheet的Excel》这篇文章主要为大家详细介绍了如何使用JavaeasyExcel实现导入多sheet的Excel,文中的示例代码讲解详细,感兴趣的小伙伴可... 目录1.官网2.Excel样式3.代码1.官网easyExcel官网2.Excel样式3.代码
阅读更多...
Java中调用数据库存储过程的示例代码

Java中调用数据库存储过程的示例代码

《Java中调用数据库存储过程的示例代码》本文介绍Java通过JDBC调用数据库存储过程的方法,涵盖参数类型、执行步骤及数据库差异,需注意异常处理与资源管理,以优化性能并实现复杂业务逻辑,感兴趣的朋友... 目录一、存储过程概述二、Java调用存储过程的基本javascript步骤三、Java调用存储过程示
阅读更多...
Visual Studio 2022 编译C++20代码的图文步骤

Visual Studio 2022 编译C++20代码的图文步骤

《VisualStudio2022编译C++20代码的图文步骤》在VisualStudio中启用C++20import功能,需设置语言标准为ISOC++20,开启扫描源查找模块依赖及实验性标... 默认创建Visual Studio桌面控制台项目代码包含C++20的import方法。右键项目的属性：
阅读更多...
python实现对数据公钥加密与私钥解密

python实现对数据公钥加密与私钥解密

《python实现对数据公钥加密与私钥解密》这篇文章主要为大家详细介绍了如何使用python实现对数据公钥加密与私钥解密,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录公钥私钥的生成使用公钥加密使用私钥解密公钥私钥的生成这一部分，使用python生成公钥与私钥，然后保存在两个文
阅读更多...
浏览器插件cursor实现自动注册、续杯的详细过程

浏览器插件cursor实现自动注册、续杯的详细过程

《浏览器插件cursor实现自动注册、续杯的详细过程》Cursor简易注册助手脚本通过自动化邮箱填写和验证码获取流程,大大简化了Cursor的注册过程,它不仅提高了注册效率,还通过友好的用户界面和详细... 目录前言功能概述使用方法安装脚本使用流程邮箱输入页面验证码页面实战演示技术实现核心功能实现1. 随机
阅读更多...
Golang如何对cron进行二次封装实现指定时间执行定时任务

Golang如何对cron进行二次封装实现指定时间执行定时任务

《Golang如何对cron进行二次封装实现指定时间执行定时任务》：本文主要介绍Golang如何对cron进行二次封装实现指定时间执行定时任务问题,具有很好的参考价值,希望对大家有所帮助,如有错误... 目录背景cron库下载代码示例【1】结构体定义【2】定时任务开启【3】使用示例【4】控制台输出总结背景
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2