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

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。

相关文章

使用animation.css库快速实现CSS3旋转动画效果

使用animation.css库快速实现CSS3旋转动画效果

《使用animation.css库快速实现CSS3旋转动画效果》随着Web技术的不断发展，动画效果已经成为了网页设计中不可或缺的一部分，本文将深入探讨animation.css的工作原理，如何使用以及... 目录1. css3动画技术简介2. animation.css库介绍2.1 animation.cs
阅读更多...
Java进行日期解析与格式化的实现代码

Java进行日期解析与格式化的实现代码

《Java进行日期解析与格式化的实现代码》使用Java搭配ApacheCommonsLang3和Natty库,可以实现灵活高效的日期解析与格式化,本文将通过相关示例为大家讲讲具体的实践操作,需要的可以... 目录一、背景二、依赖介绍1. Apache Commons Lang32. Natty三、核心实现代
阅读更多...
SpringBoot实现接口数据加解密的三种实战方案

SpringBoot实现接口数据加解密的三种实战方案

《SpringBoot实现接口数据加解密的三种实战方案》在金融支付、用户隐私信息传输等场景中,接口数据若以明文传输,极易被中间人攻击窃取,SpringBoot提供了多种优雅的加解密实现方案,本文将从原... 目录一、为什么需要接口数据加解密？二、核心加解密算法选择1. 对称加密（AES）2. 非对称加密（R
阅读更多...
基于Go语言实现Base62编码的三种方式以及对比分析

基于Go语言实现Base62编码的三种方式以及对比分析

《基于Go语言实现Base62编码的三种方式以及对比分析》Base62编码是一种在字符编码中使用62个字符的编码方式,在计算机科学中,,Go语言是一种静态类型、编译型语言,它由Google开发并开源,... 目录一、标准库现状与解决方案1. 标准库对比表2. 解决方案完整实现代码（含边界处理）二、关键实现细
阅读更多...
使用Python自动化生成PPT并结合LLM生成内容的代码解析

使用Python自动化生成PPT并结合LLM生成内容的代码解析

《使用Python自动化生成PPT并结合LLM生成内容的代码解析》PowerPoint是常用的文档工具,但手动设计和排版耗时耗力,本文将展示如何通过Python自动化提取PPT样式并生成新PPT,同时... 目录核心代码解析1. 提取 PPT 样式到 jsON关键步骤：代码片段：2. 应用 JSON 样式到
阅读更多...
python通过curl实现访问deepseek的API

python通过curl实现访问deepseek的API

《python通过curl实现访问deepseek的API》这篇文章主要为大家详细介绍了python如何通过curl实现访问deepseek的API,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编... API申请和充值下面是deepeek的API网站https://platform.deepsee
阅读更多...
SpringBoot实现二维码生成的详细步骤与完整代码

SpringBoot实现二维码生成的详细步骤与完整代码

《SpringBoot实现二维码生成的详细步骤与完整代码》如今,二维码的应用场景非常广泛,从支付到信息分享,二维码都扮演着重要角色,SpringBoot是一个非常流行的Java基于Spring框架的微... 目录一、环境搭建二、创建 Spring Boot 项目三、引入二维码生成依赖四、编写二维码生成代码五
阅读更多...
MyBatisX逆向工程的实现示例

MyBatisX逆向工程的实现示例

《MyBatisX逆向工程的实现示例》本文主要介绍了MyBatisX逆向工程的实现示例,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学... 目录逆向工程准备好数据库、表安装MyBATisX插件项目连接数据库引入依赖pom.XML生成实体类、
阅读更多...
C#实现查找并删除PDF中的空白页面

C#实现查找并删除PDF中的空白页面

《C#实现查找并删除PDF中的空白页面》PDF文件中的空白页并不少见,因为它们有可能是作者有意留下的,也有可能是在处理文档时不小心添加的,下面我们来看看如何使用Spire.PDFfor.NET通过C#... 目录安装 Spire.PDF for .NETC# 查找并删除 PDF 文档中的空白页C# 添加与删
阅读更多...
Java实现MinIO文件上传的加解密操作

Java实现MinIO文件上传的加解密操作

《Java实现MinIO文件上传的加解密操作》在云存储场景中,数据安全是核心需求之一,MinIO作为高性能对象存储服务,支持通过客户端加密（CSE）在数据上传前完成加密,下面我们来看看如何通过Java... 目录一、背景与需求二、技术选型与原理1. 加密方案对比2. 核心算法选择三、完整代码实现1. 加密上
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2