C语言二叉树的三种遍历方式的实现及原理
二叉树遍历分为三种:前序、中序、后序,其中序遍历最为重要。为啥叫这个名字?是根据根节点的顺序命名的。
比如上图正常的一个满节点,A:根节点、B:左节点、C:右节点,前序顺序是ABC(根节点排最先,然后同级先左后右);中序顺序是BAC(先左后根最后右);后序顺序是BCA(先左后右最后根)。
比如上图二叉树遍历结果
前序遍历:ABCDEFGHK
中序遍历:BDCAEHGKF
后序遍历:DCBHKGFEA
分析中序遍历如下图,中序比较重要(java很多树排序是基于中序,后面讲解分析)
下面介绍一下,二叉树的三种遍历方式,其中每一种遍历方式都有三种实现方式。
节点定义:
struct TreeNode { int val; TreeNode *left,*right; TreeNode(int val){ this->val = val; this ->left = this->right = NULL; } };
先序遍历
以上面这张图为例:我们讲讲树的三种遍历方式:
先序遍历:先访问根节点,然后访问左孩子,最后访问右孩子。
所以,上面遍历的结果是:GEDACHS。
下面,我们来看看具体代码实现
1.递归实现
void preOrder(TreeNode *root){ if (root==NULL) return; cout<<root->val<<endl; preOrder(root->left); preOrder(root->right); }
2.使用辅助栈
实现思路:1.将根节点入栈
2.每次从栈顶弹出一个节点,访问该节点
3.把当前节点的右孩子入栈
4.把当前节点的左孩子入栈
具体实现:
void preOrder2(TreeNode *root){ if (root == NULL) return; stack<TreeNode*> stk; //开辟一个栈空间 stk.push(root); while(!stk.empty()){ TreeNode* pNode = stk.pop(); cout<<pNode->val; if (pNode->right!=NULL) stk.push(pNode->right); if (pNode->left!=NULL) stk.push(pNode->left); } }
3.Morris遍历
Morris遍历,常数的空间即可在O(n)时间内完成二叉树的遍历。
O(1)空间进行遍历困难之处在于在遍历的子结点的时候如何重新返回其父节点?
在Morris遍历算法中,通过修改叶子结点的左右空指针来指向其前驱或者后继结点来实现的。
其本质:线索二叉树(Threaded Binary Tree),通过利用叶子节点空的right指针,指向中序遍历的后继节点,从而避免了对 stack 的依赖。
具体实现:
void preOrder(TreeNode* root){ if (root == NULL) return; TreeNode* pNode = root; while(pNode != NULL){ if (pNode->left == NULL) { cout<<pNode->val<<endl; pNode = pNode->right; } else{ TreeNode* pPre = pNode->left; while(pPre->right != NULL && pPre->right != pNode){ pPre = pPre->right; } if (pPre->right == NULL) { /* code */ pPre->right = pNode; cout<<pNode->val<<endl; pNode = pNode->left; } else{ pPre->right = NULL; pNode = pNode->right; } } } }
中序遍历
中序遍历:先访问左孩点,然后访问根节点,最后访问右孩子。
所以,上面遍历的结果是:DEAGHCS。
下面,我们来看看具体代码实现
1.递归实现
void InOrder(TreeNode *root){ if (root==NULL) return; InOrder(root->left); cout<<root->val<<endl; InOrder(root->right); }
2.使用辅助栈
实现思路:
初始化一个二叉树结点pNode指向根结点;
若pNode非空,那么就把pNode入栈,并把pNode变为其左孩子;(直到最左边的结点)
若pNode为空,弹出栈顶的结点,并访问该结点,将pNode指向其右孩子(访问最左边的结点,并遍历其右子树)
具体实现:
void InOrder(TreeNode *root){ if (root==NULL) { return; } stack<TreeNode*> stk; TreeNode *pNode = root; while(pNode!=NULL || !stk.empty()){ if (pNode != NULL) { stk.push(pNode); pNode = pNode->left; } else{ pNode = stk.pop(); stk.pop(); cout<<pNode->val<<endl; pNode = pNode->right; } } }
3.Morris遍历
实现思路:
1.如果当前节点pNode的左孩子为空,那么输出该节点,并把该节点的右孩子作为当前节点
2.如果当前节点pNode的左孩子非空,那么找出该节点在中序遍历的前驱结点prev
当第一次访问该前驱结点prev时,其右孩子必定为空,那么就将其右孩子设置为当前结点,以便根据这个指针返回到当前结点pNode中,并将当前结点pNode设置为其左孩子;
当该前驱结点pPre的右孩子为当前结点,那么就输出当前结点,并把前驱结点的右孩子设置为空(恢复树的结构),将当前结点更新为当前结点的右孩子;
3.重复以上两步,直到当前结点为空。
具体实现:
void InOrder(TreeNode *root){ if (root == NULL) return; TreeNode* pNode = root; while(pNode != NULL){ if (pNode->left == NULL) { cout<<pNode->val<<endl; pNode = pNode->right; } else{ TreeNode* pPre = pNode->left; while(pPre->right != NULL && pPre->right != pNode){ pPre = pPre->right; } if (pPre->right == NULL) { /* code */ pPre->right = pNode; pNode = pNode->left; } else{ pPre->right = NULL; cout<<pNode->val<<endl; pNode = pNode->right; } } } }
后序遍历
后序遍历:先访问左孩子,然后访问右孩子,最后访问根节点。
所以,上面遍历的结果是:DAEHSCG。
下面,我们来看看具体代码实现:
1.递归实现
void PostOrder(TreeNode *root){ if (root==NULL) return; PostOrder(root->left); PostOrder(root->right); cout<<root->val<<endl; }
2.使用辅助栈
void postOrder(TreeNode *root) { if(root == NULL) return; stack<TreeNode *> stk; stk.push(root); TreeNode *prev = NULL; while(!stk.empty()) { TreeNode *pNode = stk.top(); if(!prev || prev->left == pNode || prev->right == pNode) { // traverse down if(pNode->left) stk.push(pNode->left); else if(pNode->right) stk.push(pNode->right); /* else { cout << pNode->val << endl; stk.pop(); } */ } else if(pNode->left == prev) { // traverse up from left if(pNode->right) stk.push(pNode->right); } /* else if(pNode->right == prev) { // traverse up from right cout << pNode->val << endl; stk.pop(); } */ else { cout << pNode->val << endl; stk.pop(); } prev = pNode; } }
双辅助栈实现思路:
- 设置两个栈stk, stk2;
- 将根结点压入第一个栈stk;
- 弹出stk栈顶的结点,并把该结点压入第二个栈stk2;
- 将当前结点的左孩子和右孩子先后分别入栈stk;
- 当所有元素都压入stk2后,依次弹出stk2的栈顶结点,并访问之。
- 第一个栈的入栈顺序是:根结点,左孩子和右孩子;于是,压入第二个栈的顺序是:根结点,右孩子和左孩子。
因此,弹出的顺序就是:左孩子,右孩子和根结点。
void PostOrder2(TreeNode *root){ //两个栈实现 if (root == NULL) return; stack<TreeNode*> stk,stk2; stk.push(root); while(!stk.empty()){ TreeNode* pNode = stk.top(); stk.pop(); stk2.push(pNode);// 将根节点压栈 if (pNode->left != NULL) // 如果左孩子不为空,则压栈 { stk.push(pNode->left); } if (pNode->right != NULL) // 如果左孩子不为空,则压栈 { stk.push(pNode->right); } } while(!stk2.empty()){ cout<<stk2.top()->val<<endl; stk2.pop(); } }
3.Morris遍历实现
实现思路:
1.先建立一个临时结点dummy,并令其左孩子为根结点root,将当前结点设置为dummy;
2.如果当前结点的左孩子为空,则将其右孩子作为当前结点;
3.如果当前结点的左孩子不为空,则找到其在中序遍历中的前驱结点,
- -如果前驱结点的右孩子为空,将它的右孩子设置为当前结点,将当前结点更新为当前结点的左孩子;
- -如果前驱结点的右孩子为当前结点,倒序输出从当前结点的左孩子到该前驱结点这条路径上所有的结点。将前驱结点的右孩子设置为空,将当前结点更新为当前结点的右孩子。
4.重复以上过程,直到当前结点为空。
具体实现:
void reverse(TreeNode* p1,TreeNode *p2){ if (p1 == p2) return; TreeNode* x = p1; TreeNode* y = p1->right; while(true){ TreeNode* tmp = y->right; y->right = x; x = y; y = tmp; if (x == p2) break; } }
void printReverse(TreeNode* p1,TreeNode *p2){ reverse(p1,p2); TreeNode* pNode = p2; while(true){ cout<<pNode->val<<endl; if (pNode == p1) break; pNode = pNode->right; } reverse(p2,p1); }
void PostOrder3(TreeNode* root){ if(root == NULL) return; TreeNode *dummy = new TreeNode(-1); dummy->left = root; TreeNode *pNode = dummy; while(pNode != NULL) { if(pNode->left == NULL) pNode = pNode->right; else { TreeNode *pPrev = pNode->left; while(pPrev->right != NULL && pPrev->right != pNode) pPrev = pPrev->right; if(pPrev->right == NULL) { pPrev->right = pNode; pNode = pNode->left; } else { printReverse(pNode->left, pPrev); pPrev->right = NULL; pNode = pNode->right; } } } }
总结
上述三种遍历方式时间复杂度和空间复杂度分析:
1.递归遍历和非递归遍历 时间复杂度0(n) 空间复杂度O(n)
2.Morris遍历 时间复杂度0(n) 空间复杂度O(1)
以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持猪先飞。
相关文章
- 这篇文章主要为大家详细介绍了C语言实现放烟花的程序,有音乐播放,文中示例代码介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们可以参考一下...2021-02-23
- 本篇文章主要介绍C语言中char的知识,并附有代码实例,以便大家在学习的时候更好的理解,有需要的可以看一下...2020-04-25
- 这篇文章主要介绍了详解如何将c语言文件打包成exe可执行程序,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2021-02-25
- 下面小编就为大家带来一篇js遍历json的key和value的实例。小编觉得挺不错的,现在就分享给大家,也给大家做个参考。一起跟随小编过来看看吧...2017-01-26
- free函数是释放之前某一次malloc函数申请的空间,而且只是释放空间,并不改变指针的值。下面我们就来详细探讨下...2020-04-25
JavaScript中的数组遍历forEach()与map()方法以及兼容写法介绍
下面小编就为大家带来一篇JavaScript中的数组遍历forEach()与map()方法以及兼容写法介绍。小编觉得挺不错的,现在分享给大家,也给大家做个参考。一起跟随小编过来看看吧...2016-05-20- 这篇文章主要介绍了C语言中计算正弦的相关函数总结,包括正弦和双曲线正弦以及反正弦的函数,需要的朋友可以参考下...2020-04-25
详解C语言中的rename()函数和remove()函数的使用方法
这篇文章主要介绍了详解C语言中的rename()函数和remove()函数的使用方法,是C语言入门学习中的基础知识,需要的朋友可以参考下...2020-04-25- 这篇文章主要介绍了C语言中求和、计算平均值、方差和标准差的实例,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2020-12-10
- 这篇文章主要介绍了c# 遍历 Dictionary的四种方式,帮助大家更好的理解和使用c#,感兴趣的朋友可以了解下...2020-12-08
jQuery遍历DOM的父级元素、子级元素和同级元素的方法总结
借助jQuery我们可以轻松地堆DOM元素进行向上、向下遍历以及同级的遍历,本文我们即来整理jQuery遍历DOM的父级元素、子级元素和同级元素的方法总结:...2016-07-25- 本篇文章主要讲解C语言 基本语法,这里提供简单的示例和代码来详细讲解C语言的基本语法,开始学习C语言的朋友可以看一下,希望能够给你带来帮助...2021-09-18
- 下面就为大家带来一篇jquery对Json的各种遍历方法总结(必看篇)。小编觉得挺不错的,现在就分享给大家,也给大家做个参考。一起跟随小编过来看看吧...2016-10-02
- 这篇文章主要介绍了C# 遍历datatable字段名和value的案例,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2021-01-19
- 这篇文章主要介绍了C语言中send()函数和sendto()函数的使用方法,是C语言入门学习中的基础知识,需要的朋友可以参考下...2020-04-25
- 这篇文章主要为大家详细介绍了JS中的二叉树遍历,何为二叉树,什么是二叉树的遍历,感兴趣的小伙伴们可以参考一下...2016-03-22
- 今天小编就为大家分享一篇C语言实现从文件读入一个3*3数组,并计算每行的平均值,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2020-04-25
- 这篇文章主要介绍了使用C语言操作文件的基本函数整理,包括创建和打开以及关闭文件的操作方法,需要的朋友可以参考下...2020-04-25
- 这篇文章主要介绍了C语言中memcpy 函数的用法详解的相关资料,需要的朋友可以参考下...2020-04-25
- 这篇文章主要介绍了Xml中使用foreach遍历对象实现代码,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下...2020-12-04