C語(yǔ)言二叉樹(shù)的三種遍歷方式的實(shí)現(xiàn)及原理
二叉樹(shù)遍歷分為三種：前序、中序、后序，其中序遍歷最為重要。為啥叫這個(gè)名字？是根據(jù)根節(jié)點(diǎn)的順序命名的。
比如上圖正常的一個(gè)滿節(jié)點(diǎn)，A：根節(jié)點(diǎn)、B：左節(jié)點(diǎn)、C：右節(jié)點(diǎn)，前序順序是ABC（根節(jié)點(diǎn)排最先，然后同級(jí)先左后右）；中序順序是BAC(先左后根最后右）；后序順序是BCA（先左后右最后根）。
比如上圖二叉樹(shù)遍歷結(jié)果
前序遍歷：ABCDEFGHK
中序遍歷：BDCAEHGKF
后序遍歷：DCBHKGFEA
分析中序遍歷如下圖，中序比較重要（java很多樹(shù)排序是基于中序，后面講解分析）
下面介紹一下，二叉樹(shù)的三種遍歷方式，其中每一種遍歷方式都有三種實(shí)現(xiàn)方式。
節(jié)點(diǎn)定義：
struct TreeNode
{
int val;
TreeNode *left,*right;
TreeNode(int val){
this->val = val;
this ->left = this->right = NULL;
}
};
先序遍歷
以上面這張圖為例：我們講講樹(shù)的三種遍歷方式：
先序遍歷：先訪問(wèn)根節(jié)點(diǎn)，然后訪問(wèn)左孩子，最后訪問(wèn)右孩子。
所以，上面遍歷的結(jié)果是：GEDACHS。
下面，我們來(lái)看看具體代碼實(shí)現(xiàn)
1.遞歸實(shí)現(xiàn)
void preOrder(TreeNode *root){
if (root==NULL)
return;
cout<<root->val<<endl;
preOrder(root->left);
preOrder(root->right);
}
2.使用輔助?！?/strong>
實(shí)現(xiàn)思路：1.將根節(jié)點(diǎn)入棧
2.每次從棧頂彈出一個(gè)節(jié)點(diǎn)，訪問(wèn)該節(jié)點(diǎn)
3.把當(dāng)前節(jié)點(diǎn)的右孩子入棧
4.把當(dāng)前節(jié)點(diǎn)的左孩子入棧
具體實(shí)現(xiàn)：
void preOrder2(TreeNode *root){
if (root == NULL)
return;
stack<TreeNode*> stk; //開(kāi)辟一個(gè)?？臻g
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遍歷，常數(shù)的空間即可在O(n)時(shí)間內(nèi)完成二叉樹(shù)的遍歷。
O(1)空間進(jìn)行遍歷困難之處在于在遍歷的子結(jié)點(diǎn)的時(shí)候如何重新返回其父節(jié)點(diǎn)？
在Morris遍歷算法中，通過(guò)修改葉子結(jié)點(diǎn)的左右空指針來(lái)指向其前驅(qū)或者后繼結(jié)點(diǎn)來(lái)實(shí)現(xiàn)的。
其本質(zhì)：線索二叉樹(shù)（Threaded Binary Tree)，通過(guò)利用葉子節(jié)點(diǎn)空的right指針，指向中序遍歷的后繼節(jié)點(diǎn)，從而避免了對(duì) stack 的依賴。
具體實(shí)現(xiàn)：
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;
}
}
}
}
中序遍歷
中序遍歷：先訪問(wèn)左孩點(diǎn)，然后訪問(wèn)根節(jié)點(diǎn)，最后訪問(wèn)右孩子。
所以，上面遍歷的結(jié)果是：DEAGHCS。
下面，我們來(lái)看看具體代碼實(shí)現(xiàn)
1.遞歸實(shí)現(xiàn)
void InOrder(TreeNode *root){
if (root==NULL)
return;
InOrder(root->left);
cout<<root->val<<endl;
InOrder(root->right);
}
2.使用輔助棧
實(shí)現(xiàn)思路：
初始化一個(gè)二叉樹(shù)結(jié)點(diǎn)pNode指向根結(jié)點(diǎn)；
若pNode非空，那么就把pNode入棧，并把pNode變?yōu)槠渥蠛⒆樱唬ㄖ钡阶钭筮叺慕Y(jié)點(diǎn)）
若pNode為空，彈出棧頂?shù)慕Y(jié)點(diǎn)，并訪問(wèn)該結(jié)點(diǎn)，將pNode指向其右孩子（訪問(wèn)最左邊的結(jié)點(diǎn)，并遍歷其右子樹(shù)）
具體實(shí)現(xiàn)：
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遍歷
實(shí)現(xiàn)思路：
1.如果當(dāng)前節(jié)點(diǎn)pNode的左孩子為空，那么輸出該節(jié)點(diǎn)，并把該節(jié)點(diǎn)的右孩子作為當(dāng)前節(jié)點(diǎn)
2.如果當(dāng)前節(jié)點(diǎn)pNode的左孩子非空，那么找出該節(jié)點(diǎn)在中序遍歷的前驅(qū)結(jié)點(diǎn)prev
當(dāng)?shù)谝淮卧L問(wèn)該前驅(qū)結(jié)點(diǎn)prev時(shí)，其右孩子必定為空，那么就將其右孩子設(shè)置為當(dāng)前結(jié)點(diǎn)，以便根據(jù)這個(gè)指針?lè)祷氐疆?dāng)前結(jié)點(diǎn)pNode中，并將當(dāng)前結(jié)點(diǎn)pNode設(shè)置為其左孩子；
當(dāng)該前驅(qū)結(jié)點(diǎn)pPre的右孩子為當(dāng)前結(jié)點(diǎn)，那么就輸出當(dāng)前結(jié)點(diǎn)，并把前驅(qū)結(jié)點(diǎn)的右孩子設(shè)置為空（恢復(fù)樹(shù)的結(jié)構(gòu)），將當(dāng)前結(jié)點(diǎn)更新為當(dāng)前結(jié)點(diǎn)的右孩子；
3.重復(fù)以上兩步，直到當(dāng)前結(jié)點(diǎn)為空。
具體實(shí)現(xiàn)：
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;
}
}
}
}
后序遍歷
后序遍歷：先訪問(wèn)左孩子，然后訪問(wèn)右孩子，最后訪問(wèn)根節(jié)點(diǎn)。
所以，上面遍歷的結(jié)果是：DAEHSCG。
下面，我們來(lái)看看具體代碼實(shí)現(xiàn)：
1.遞歸實(shí)現(xiàn)
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;
}
}
雙輔助棧實(shí)現(xiàn)思路：
- 設(shè)置兩個(gè)棧stk, stk2；
- 將根結(jié)點(diǎn)壓入第一個(gè)棧stk；
- 彈出stk棧頂?shù)慕Y(jié)點(diǎn)，并把該結(jié)點(diǎn)壓入第二個(gè)棧stk2；
- 將當(dāng)前結(jié)點(diǎn)的左孩子和右孩子先后分別入棧stk；
- 當(dāng)所有元素都?jí)喝雜tk2后，依次彈出stk2的棧頂結(jié)點(diǎn)，并訪問(wèn)之。
- 第一個(gè)棧的入棧順序是：根結(jié)點(diǎn)，左孩子和右孩子；于是，壓入第二個(gè)棧的順序是：根結(jié)點(diǎn)，右孩子和左孩子。
因此，彈出的順序就是：左孩子，右孩子和根結(jié)點(diǎn)。
void PostOrder2(TreeNode *root){ //兩個(gè)棧實(shí)現(xiàn)
if (root == NULL)
return;
stack<TreeNode*> stk,stk2;
stk.push(root);
while(!stk.empty()){
TreeNode* pNode = stk.top();
stk.pop();
stk2.push(pNode);// 將根節(jié)點(diǎn)壓棧
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遍歷實(shí)現(xiàn)
實(shí)現(xiàn)思路：
1.先建立一個(gè)臨時(shí)結(jié)點(diǎn)dummy，并令其左孩子為根結(jié)點(diǎn)root，將當(dāng)前結(jié)點(diǎn)設(shè)置為dummy；
2.如果當(dāng)前結(jié)點(diǎn)的左孩子為空，則將其右孩子作為當(dāng)前結(jié)點(diǎn)；
3.如果當(dāng)前結(jié)點(diǎn)的左孩子不為空，則找到其在中序遍歷中的前驅(qū)結(jié)點(diǎn)，
- -如果前驅(qū)結(jié)點(diǎn)的右孩子為空，將它的右孩子設(shè)置為當(dāng)前結(jié)點(diǎn)，將當(dāng)前結(jié)點(diǎn)更新為當(dāng)前結(jié)點(diǎn)的左孩子；
- -如果前驅(qū)結(jié)點(diǎn)的右孩子為當(dāng)前結(jié)點(diǎn)，倒序輸出從當(dāng)前結(jié)點(diǎn)的左孩子到該前驅(qū)結(jié)點(diǎn)這條路徑上所有的結(jié)點(diǎn)。將前驅(qū)結(jié)點(diǎn)的右孩子設(shè)置為空，將當(dāng)前結(jié)點(diǎn)更新為當(dāng)前結(jié)點(diǎn)的右孩子。
4.重復(fù)以上過(guò)程，直到當(dāng)前結(jié)點(diǎn)為空。
具體實(shí)現(xiàn)：
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;
}
}
}
}
總結(jié)
上述三種遍歷方式時(shí)間復(fù)雜度和空間復(fù)雜度分析：
1.遞歸遍歷和非遞歸遍歷 時(shí)間復(fù)雜度0(n) 空間復(fù)雜度O(n)
2.Morris遍歷 時(shí)間復(fù)雜度0(n) 空間復(fù)雜度O(1)
以上就是本文的全部?jī)?nèi)容，希望對(duì)大家的學(xué)習(xí)有所幫助，也希望大家多多支持腳本之家。
相關(guān)文章
C++實(shí)現(xiàn)動(dòng)態(tài)規(guī)劃過(guò)程詳解
動(dòng)態(tài)規(guī)劃是解決一類最優(yōu)問(wèn)題的常用方法，它是解決最優(yōu)化問(wèn)題的一種途徑，在本文中，我們將討論如何使用C++實(shí)現(xiàn)動(dòng)態(tài)規(guī)劃算法，并提供一些示例來(lái)幫助您更好地理解該算法2023-05-05
大家好，本篇文章主要講的是C++關(guān)于指針,繼承和多態(tài)介紹，感興趣的同學(xué)趕快來(lái)看一看吧，對(duì)你有幫助的話記得收藏一下，方便下次瀏覽2022-01-01
淺析Boost智能指針:scoped_ptr shared_ptr weak_ptr
雖然通過(guò)弱引用指針可以有效的解除循環(huán)引用，但這種方式必須在程序員能預(yù)見(jiàn)會(huì)出現(xiàn)循環(huán)引用的情況下才能使用，也可以是說(shuō)這個(gè)僅僅是一種編譯期的解決方案，如果程序在運(yùn)行過(guò)程中出現(xiàn)了循環(huán)引用，還是會(huì)造成內(nèi)存泄漏的2013-09-09
c++實(shí)現(xiàn)的常見(jiàn)緩存算法和LRU
LRU緩存算法也叫LRU頁(yè)面置換算法，是一種經(jīng)典常用的頁(yè)面置換算法，下面這篇文章主要介紹了c++實(shí)現(xiàn)的常見(jiàn)緩存算法和LRU,需要的朋友可以參考借鑒，下面來(lái)一起看看吧。2017-01-01
本篇文章對(duì)c++的大數(shù)階乘進(jìn)行了代碼示例的介紹。需要的朋友參考下2013-05-05
QT實(shí)現(xiàn)QML側(cè)邊導(dǎo)航欄的最簡(jiǎn)方法
本文主要介紹了QT實(shí)現(xiàn)QML側(cè)邊導(dǎo)航欄的最簡(jiǎn)方法，文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2022-06-06
一起來(lái)學(xué)習(xí)C++的函數(shù)指針和函數(shù)對(duì)象
這篇文章主要為大家詳細(xì)介紹了C++函數(shù)指針和函數(shù)對(duì)象，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下，希望能夠給你帶來(lái)幫助2022-03-03
C語(yǔ)言 動(dòng)態(tài)內(nèi)存開(kāi)辟常見(jiàn)問(wèn)題解決與分析流程
動(dòng)態(tài)內(nèi)存是相對(duì)靜態(tài)內(nèi)存而言的。所謂動(dòng)態(tài)和靜態(tài)就是指內(nèi)存的分配方式。動(dòng)態(tài)內(nèi)存是指在堆上分配的內(nèi)存，而靜態(tài)內(nèi)存是指在棧上分配的內(nèi)存2022-03-03
這篇文章主要為大家介紹了C語(yǔ)言的函數(shù)棧幀，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下，希望能夠給你帶來(lái)幫助，希望能夠給你帶來(lái)幫助2021-11-11
C++AVL樹(shù)4種旋轉(zhuǎn)詳講(左單旋、右單旋、左右雙旋、右左雙旋)
AVL樹(shù)即平衡二叉搜索樹(shù),平衡因子bf=右子樹(shù)的高度-左子樹(shù)的高度,bf為0,-1,1時(shí),此樹(shù)即平衡,下面這篇文章主要給大家介紹了關(guān)于C++AVL樹(shù)4種旋轉(zhuǎn)(左單旋、右單旋、左右雙旋、右左雙旋)的相關(guān)資料,需要的朋友可以參考下2022-11-11