中序遍歷(中序遍歷的遍歷方式是什么)

中序遍歷的遍歷方法為:對于當前結點,首先遍歷左子樹,然后訪問當前節點,最后遍歷右子樹。中序遍歷是二叉樹遍歷的一種,也叫做中根遍歷、中序周游。

本教程操作環境:windows7系統、C++17版本、Dell G3電腦。

二叉樹是一種重要的數據結構,對二叉樹的遍歷也很重要。這里簡單介紹三種二叉樹中序遍歷的方法。二叉樹的中序遍歷就是首先遍歷左子樹,然后訪問當前節點,最后遍歷右子樹。對于下面的二叉樹,中序遍歷結果如下:

結果:[5,10,6,15,2]

直觀來看,二叉樹的中序遍歷就是將節點投影到一條水平的坐標上。如圖:

1、遞歸法

這是思路最簡單的方法,容易想到并且容易實現。遞歸的終止條件是當前節點是否為空。首先遞歸調用遍歷左子樹,然后訪問當前節點,最后遞歸調用右子樹。代碼如下:

//recursiveclassSolution1{public:vector<int>inorderTraversal(TreeNode*root){vector<int>ret;if(root==NULL)returnret;inorderHelper(ret,root);returnret;}private:voidinorderHelper(vector<int>&ret,TreeNode*root){if(root==NULL)return;inorderHelper(ret,root->left);ret.push_back(root->val);inorderHelper(ret,root->right);}};

2、迭代法

在迭代方法中,從根節點開始找二叉樹的最左節點,將走過的節點保存在一個棧中,找到最左節點后訪問,對于每個節點來說,它都是以自己為根的子樹的根節點,訪問完之后就可以轉到右兒子上了。代碼如下:

//iterate,usingastackclassSolution2{public:vector<int>inorderTraversal(TreeNode*root){vector<int>ret;if(root==NULL)returnret;TreeNode*curr=root;stack<TreeNode*>st;while(!st.empty()||curr!=NULL){while(curr!=NULL){st.push(curr);curr=curr->left;}curr=st.top();st.pop();ret.push_back(curr->val);curr=curr->right;}returnret;}};

這種方法時間復雜度是O(n),空間復雜度也是O(n)。

3、Morris法

這種方法是Morris發明的,看完之后感覺精妙無比。這種方法不使用遞歸,不使用棧,O(1)的空間復雜度完成二叉樹的遍歷。這種方法的基本思路就是將所有右兒子為NULL的節點的右兒子指向后繼節點(對于右兒子不為空的節點,右兒子就是接下來要訪問的節點)。這樣,對于任意一個節點,當訪問完它后,它的右兒子已經指向了下一個該訪問的節點。對于最右節點,不需要進行這樣的操作。注意,這樣的操作是在遍歷的時候完成的,完成訪問節點后會把樹還原。整個循環的判斷條件為當前節點是否為空。例如上面的二叉樹,遍歷過程如下(根據當前節點c的位置):

(1)當前節點為10,因為左兒子非空,不能訪問,找到c的左子樹的最右節點p:

結果:[]

(2)找節點c的左子樹的最右節點有兩種終止條件,一種右兒子為空,一種右兒子指向當前節點。下面是右兒子為空的情況,這種情況先要構造,將節點p的右兒子指向后繼節點c,然后c下移:

結果:[]

(3)當前節點c的左兒子為空,進行訪問。訪問后將c指向右兒子(即后繼節點):

結果:[5]

(4)繼續尋找左子樹的最右節點,這次的終止條件是最右節點為當前節點。這說明當前節點的左子樹遍歷完畢,訪問當前節點后,還原二叉樹,將當前節點指向后繼節點:

結果:[5,10]

(5)重復上述過程,直到c指向整棵二叉樹的最右節點:

左兒子為空,進行訪問,c轉到右兒子。右兒子為空,不滿足判斷條件,循環結束,遍歷完成。結果如下:

[5,10,6,15,2]

這就是Morris方法,時間復雜度為O(n),空間復雜度是O(1)。代碼如下:

//Morristraversal,withoutastackclassSolution3{public:vector<int>inorderTraversal(TreeNode*root){vector<int>ret;if(root==NULL)returnret;TreeNode*curr=root;TreeNode*pre;while(curr){if(curr->left==NULL){ret.push_back(curr->val);curr=curr->right;}else{pre=curr->left;while(pre->right&&pre->right!=curr)pre=pre->right;if(pre->right==NULL){pre->right=curr;curr=curr->left;}else{ret.push_back(curr->val);pre->right=NULL;curr=curr->right;}}}returnret;}};

到此,關于“中序遍歷的遍歷方式是什么”的學習就結束了,希望能夠解決大家的疑惑。理論與實踐的搭配能更好的幫助大家學習,快去試試吧!若想繼續學習更多相關知識,請繼續關注本站網站,小編會繼續努力為大家帶來更多實用的文章!