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

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

相关文章

hdu1043(八数码问题,广搜 + hash(实现状态压缩) )

利用康拓展开将一个排列映射成一个自然数,然后就变成了普通的广搜题。 #include<iostream>#include<algorithm>#include<string>#include<stack>#include<queue>#include<map>#include<stdio.h>#include<stdlib.h>#include<ctype.h>#inclu

【C++】_list常用方法解析及模拟实现

相信自己的力量,只要对自己始终保持信心,尽自己最大努力去完成任何事,就算事情最终结果是失败了,努力了也不留遗憾。💓💓💓 目录   ✨说在前面 🍋知识点一:什么是list? •🌰1.list的定义 •🌰2.list的基本特性 •🌰3.常用接口介绍 🍋知识点二:list常用接口 •🌰1.默认成员函数 🔥构造函数(⭐) 🔥析构函数 •🌰2.list对象

【Prometheus】PromQL向量匹配实现不同标签的向量数据进行运算

✨✨ 欢迎大家来到景天科技苑✨✨ 🎈🎈 养成好习惯,先赞后看哦~🎈🎈 🏆 作者简介:景天科技苑 🏆《头衔》:大厂架构师,华为云开发者社区专家博主,阿里云开发者社区专家博主,CSDN全栈领域优质创作者,掘金优秀博主,51CTO博客专家等。 🏆《博客》:Python全栈,前后端开发,小程序开发,人工智能,js逆向,App逆向,网络系统安全,数据分析,Django,fastapi

活用c4d官方开发文档查询代码

当你问AI助手比如豆包,如何用python禁止掉xpresso标签时候,它会提示到 这时候要用到两个东西。https://developers.maxon.net/论坛搜索和开发文档 比如这里我就在官方找到正确的id描述 然后我就把参数标签换过来

让树莓派智能语音助手实现定时提醒功能

最初的时候是想直接在rasa 的chatbot上实现,因为rasa本身是带有remindschedule模块的。不过经过一番折腾后,忽然发现,chatbot上实现的定时,语音助手不一定会有响应。因为,我目前语音助手的代码设置了长时间无应答会结束对话,这样一来,chatbot定时提醒的触发就不会被语音助手获悉。那怎么让语音助手也具有定时提醒功能呢? 我最后选择的方法是用threading.Time

Android实现任意版本设置默认的锁屏壁纸和桌面壁纸(两张壁纸可不一致)

客户有些需求需要设置默认壁纸和锁屏壁纸  在默认情况下 这两个壁纸是相同的  如果需要默认的锁屏壁纸和桌面壁纸不一样 需要额外修改 Android13实现 替换默认桌面壁纸: 将图片文件替换frameworks/base/core/res/res/drawable-nodpi/default_wallpaper.*  (注意不能是bmp格式) 替换默认锁屏壁纸: 将图片资源放入vendo

C#实战|大乐透选号器[6]:实现实时显示已选择的红蓝球数量

哈喽,你好啊,我是雷工。 关于大乐透选号器在前面已经记录了5篇笔记,这是第6篇; 接下来实现实时显示当前选中红球数量,蓝球数量; 以下为练习笔记。 01 效果演示 当选择和取消选择红球或蓝球时,在对应的位置显示实时已选择的红球、蓝球的数量; 02 标签名称 分别设置Label标签名称为:lblRedCount、lblBlueCount

poj 1258 Agri-Net(最小生成树模板代码)

感觉用这题来当模板更适合。 题意就是给你邻接矩阵求最小生成树啦。~ prim代码:效率很高。172k...0ms。 #include<stdio.h>#include<algorithm>using namespace std;const int MaxN = 101;const int INF = 0x3f3f3f3f;int g[MaxN][MaxN];int n

Kubernetes PodSecurityPolicy:PSP能实现的5种主要安全策略

Kubernetes PodSecurityPolicy:PSP能实现的5种主要安全策略 1. 特权模式限制2. 宿主机资源隔离3. 用户和组管理4. 权限提升控制5. SELinux配置 💖The Begin💖点点关注,收藏不迷路💖 Kubernetes的PodSecurityPolicy(PSP)是一个关键的安全特性,它在Pod创建之前实施安全策略,确保P

计算机毕业设计 大学志愿填报系统 Java+SpringBoot+Vue 前后端分离 文档报告 代码讲解 安装调试

🍊作者:计算机编程-吉哥 🍊简介:专业从事JavaWeb程序开发,微信小程序开发,定制化项目、 源码、代码讲解、文档撰写、ppt制作。做自己喜欢的事,生活就是快乐的。 🍊心愿:点赞 👍 收藏 ⭐评论 📝 🍅 文末获取源码联系 👇🏻 精彩专栏推荐订阅 👇🏻 不然下次找不到哟~Java毕业设计项目~热门选题推荐《1000套》 目录 1.技术选型 2.开发工具 3.功能