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

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。

相关文章

SpringBoot3实现Gzip压缩优化的技术指南

SpringBoot3实现Gzip压缩优化的技术指南

《SpringBoot3实现Gzip压缩优化的技术指南》随着Web应用的用户量和数据量增加,网络带宽和页面加载速度逐渐成为瓶颈,为了减少数据传输量,提高用户体验,我们可以使用Gzip压缩HTTP响应,... 目录1、简述2、配置2.1 添加依赖2.2 配置 Gzip 压缩3、服务端应用4、前端应用4.1 N
阅读更多...
SpringBoot实现数据库读写分离的3种方法小结

SpringBoot实现数据库读写分离的3种方法小结

《SpringBoot实现数据库读写分离的3种方法小结》为了提高系统的读写性能和可用性,读写分离是一种经典的数据库架构模式,在SpringBoot应用中,有多种方式可以实现数据库读写分离,本文将介绍三... 目录一、数据库读写分离概述二、方案一：基于AbstractRoutingDataSource实现动态
阅读更多...
Python FastAPI+Celery+RabbitMQ实现分布式图片水印处理系统

Python FastAPI+Celery+RabbitMQ实现分布式图片水印处理系统

《PythonFastAPI+Celery+RabbitMQ实现分布式图片水印处理系统》这篇文章主要为大家详细介绍了PythonFastAPI如何结合Celery以及RabbitMQ实现简单的分布式... 实现思路FastAPI 服务器Celery 任务队列RabbitMQ 作为消息代理定时任务处理完整
阅读更多...
springboot循环依赖问题案例代码及解决办法

springboot循环依赖问题案例代码及解决办法

《springboot循环依赖问题案例代码及解决办法》在SpringBoot中,如果两个或多个Bean之间存在循环依赖（即BeanA依赖BeanB,而BeanB又依赖BeanA）,会导致Spring的... 目录1. 什么是循环依赖？2. 循环依赖的场景案例3. 解决循环依赖的常见方法方法 1：使用 @La
阅读更多...
Java枚举类实现Key-Value映射的多种实现方式

Java枚举类实现Key-Value映射的多种实现方式

《Java枚举类实现Key-Value映射的多种实现方式》在Java开发中,枚举(Enum)是一种特殊的类,本文将详细介绍Java枚举类实现key-value映射的多种方式,有需要的小伙伴可以根据需要... 目录前言一、基础实现方式1.1 为枚举添加属性和构造方法二、http://www.cppcns.co
阅读更多...
使用Python实现快速搭建本地HTTP服务器

使用Python实现快速搭建本地HTTP服务器

《使用Python实现快速搭建本地HTTP服务器》：本文主要介绍如何使用Python快速搭建本地HTTP服务器,轻松实现一键HTTP文件共享,同时结合二维码技术,让访问更简单,感兴趣的小伙伴可以了... 目录1. 概述2. 快速搭建 HTTP 文件共享服务2.1 核心思路2.2 代码实现2.3 代码解读3.
阅读更多...
使用C#代码在PDF文档中添加、删除和替换图片

使用C#代码在PDF文档中添加、删除和替换图片

《使用C#代码在PDF文档中添加、删除和替换图片》在当今数字化文档处理场景中,动态操作PDF文档中的图像已成为企业级应用开发的核心需求之一,本文将介绍如何在.NET平台使用C#代码在PDF文档中添加、... 目录引言用C#添加图片到PDF文档用C#删除PDF文档中的图片用C#替换PDF文档中的图片引言在当
阅读更多...
C#使用SQLite进行大数据量高效处理的代码示例

C#使用SQLite进行大数据量高效处理的代码示例

《C#使用SQLite进行大数据量高效处理的代码示例》在软件开发中,高效处理大数据量是一个常见且具有挑战性的任务,SQLite因其零配置、嵌入式、跨平台的特性,成为许多开发者的首选数据库,本文将深入探... 目录前言准备工作数据实体核心技术批量插入：从乌龟到猎豹的蜕变分页查询：加载百万数据异步处理：拒绝界面
阅读更多...
MySQL双主搭建+keepalived高可用的实现

MySQL双主搭建+keepalived高可用的实现

《MySQL双主搭建+keepalived高可用的实现》本文主要介绍了MySQL双主搭建+keepalived高可用的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,... 目录一、测试环境准备二、主从搭建1.创建复制用户2.创建复制关系3.开启复制，确认复制是否成功4.同
阅读更多...
Java实现文件图片的预览和下载功能

Java实现文件图片的预览和下载功能

《Java实现文件图片的预览和下载功能》这篇文章主要为大家详细介绍了如何使用Java实现文件图片的预览和下载功能,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... Java实现文件（图片）的预览和下载 @ApiOperation("访问文件") @GetMapping("
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2