大家好，感謝邀請，今天來為大家分享一下二叉樹的4種遍歷方法圖解的問題，以及和二叉樹遍歷過程看不懂的一些困惑，大家要是還不太明白的話，也沒有關系，因為接下來將為大家分享，希望可以幫助到大家，解決大家的問題，下面就開始吧！
一棵二叉樹的先序遍歷
1、先序遍歷第一個為樹的根，先序遍歷是先根再左子樹最后右子樹，第一個肯定是樹的根，先畫A，A再中序遍歷中左右都有，說明A有左子樹也有右子樹。
2、然后看先序第一個值是B，在中序中為A的前面，所以B是A的左子樹
3、繼續看先序，接下來是C、D，C再中序中再B的前面，所以C是B的左子樹，D在B后面，D是B的
4、接下來是E，E在中序是在D后面A前面，所以E是D的右子樹
5、接著先序中是F，F在中序為A后面，是A的右子樹
先根遍歷和后根遍歷怎樣確定一棵二叉樹
前序和后序在本質上都是將父節點與子結點進行分離，但并沒有指明左子樹和右子樹的能力，因此得到這兩個序列只能明確父子關系，而不能確定一個二叉樹。
由二叉樹的中序和前序遍歷序列可以唯一確定一棵二叉樹，由前序和后序遍歷則不能唯一確定一棵二叉樹由二叉樹的中序和后序遍歷序列可以唯一確定一棵二叉樹，由前序和后序遍歷則不能唯一確定一棵二叉樹
二叉樹遞歸遍歷和非遞歸遍歷的優點和缺點
遞歸和非遞歸只是解決問題的方法的不同，本質還是一樣的。
2.遞歸算法相對于非遞歸算法來說效率通常都會更低2.1遞歸算法會有更多的資源需要壓棧和出棧操作（不僅僅是參數，還有函數地址等）
2.2由于編譯器對附加的一些棧保護機制會導致遞歸執行的更加低效3.使用循環代替遞歸算法，通常可以獲得更好的執行效率和空間效率，在二叉樹層次較深的情況下，采用非遞歸方式遍歷能夠有效的提升遍歷的性能。
二叉樹的后序遍歷結構表示法
1、遞歸法
直接上代碼：
//recursion
classSolution1{
public:
vector<int>postorderTraversal(TreeNode*root){
vector<int>ret;
postHelper(ret,root);
returnret;
}
private:
voidpostHelper(vector<int>&ret,TreeNode*root)
{
if(root==NULL)return;
postHelper(ret,root->left);
postHelper(ret,root->right);
ret.push_back(root->val);
}
};
2、迭代法
迭代法使用一個棧來保存當前不需要訪問的節點。不過，不同于中序遍歷與前序遍歷，在后序遍歷中每一個節點需要一個標志位，來標識當前節點的左右子樹是否被訪問。因為在后序遍歷中，只有一個節點的左右子樹被訪問后它才能被訪問。因此，壓入棧中的數據類型需要是一個pair<TreeNode*,int>，其中用1來表示當前節點的左右子樹正被訪問，當再次訪問到此節點時可以訪問此節點；用0表示當前節點的左右子樹未被訪問，再次訪問到此節點時需要首先訪問此節點的左右子樹。代碼如下：
//iteration
classSolution1{
public:
vector<int>postorderTraversal(TreeNode*root){
vector<int>ret;
if(root==NULL)returnret;
stack<pair<TreeNode*,int>>st;
st.push(make_pair(root,0));
while(!st.empty())
{
TreeNode*curr=st.top().first;
if(st.top().second==1)
{
ret.push_back(curr->val);
st.pop();
}
else
{
st.top().second=1;
if(curr->right)st.push(make_pair(curr->right,0));
if(curr->left)st.push(make_pair(curr->left,0));
}
}
returnret;
}
}
3、迭代法：按照根、右、左的順序訪問然后取反
這種方法就是按照根、右、左的順序訪問，然后將結果取反即可。后序遍歷的順序是左、右、根。這種方法就可以在前序遍歷的基礎上修改即可。代碼如下：
classSolution3{
public:
vector<int>postorderTraversal(TreeNode*root){
vector<int>ret;
if(root==NULL)returnret;
stack<TreeNode*>st;
st.push(root);
while(!st.empty())
{
TreeNode*curr=st.top();
st.pop();
if(curr->left)st.push(curr->left);
if(curr->right)st.push(curr->right);
ret.push_back(curr->val);
}
reverse(ret.begin(),ret.end());
returnret;
}
};
在按照根、右、左的順序遍歷時，每個節點訪問一遍，最后將結果取反時，每個節點也訪問一遍，因此節點的總訪問次數和方法2相同。
4、Morris方法
后序遍歷的Morris方法思路比較難。但整體上還是一樣的，對原來的二叉樹的修改也是一樣的，不同的是訪問的順序。而在后序遍歷中，訪問時比較麻煩。下面是整個算法的工作過程;
首先建立一個臨時節點dump，令其左兒子是root。并且還需要一個子過程，就是倒序輸出某兩個節點之間路徑上的各個節點。
步驟：
當前節點設置為臨時節點dump。
（1）如果當前節點的左兒子為空，則將其右兒子作為當前節點；
（2）如果當前節點的左兒子非空，在當前節點的左子樹中找到當前節點在中序遍歷下的前驅節點；
a)如果前驅節點的右孩子為空，將它的右兒子設置為當前節點。當前節點更新為當前節點的左兒子；
b)如果前驅節點的右兒子為當前節點，將它的右孩子重新設為空。倒序輸出從當前節點的左兒子到該前驅節點這條路徑上的所有節點。當前節點更新為當前節點的右兒子；
（3）重復以上（1）（2）直到當前節點為空。
代碼如下：
//morris
classSolution4{
public:
vector<int>postorderTraversal(TreeNode*root){
vector<int>ret;
TreeNode*dump=newTreeNode(0);
dump->left=root;
TreeNode*curr=dump;
TreeNode*pre;
while(curr)
{
if(curr->left==NULL)
{
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
{
reverseAddNodes(curr->left,pre,ret);
pre->right=NULL;
curr=curr->right;
}
}
}
returnret;
}
private:
voidreverseAddNodes(TreeNode*begin,TreeNode*end,vector<int>&ret)
{
reverseNodes(begin,end);
TreeNode*curr=end;
while(true)
{
ret.push_back(curr->val);
if(curr==begin)break;
curr=curr->right;
}
reverseNodes(end,begin);
}
voidreverseNodes(TreeNode*begin,TreeNode*end)
{
TreeNode*pre=begin;
TreeNode*curr=pre->right;
TreeNode*post;
while(pre!=end)
{
post=curr->right;
curr->right=pre;
pre=curr;
curr=post;
}
}
}
設完全二叉樹的順序存儲結構中存儲數據ABCDE,畫出該二叉樹的鏈式存儲結構
6．設完全二叉樹的順序存儲結構中存儲數據ABCDE，要求給出該二叉樹的鏈式存儲結構并給出該二叉樹的前序、中序和后序遍歷序列
任何一棵二叉樹不可能沒有葉子結點
是的
二叉樹有如下性質：在任意一棵二叉樹中，度為0的結點(即葉子結點)總是比度為2的結點多一個，所以度為2的結點為1-1=0個，可以得出共有11個度為1的結點，那么該二叉樹每一層上只能有一個結點，共12層，即深度為12。
以上僅僅為個人觀點。
關于本次二叉樹的4種遍歷方法圖解和二叉樹遍歷過程看不懂的問題分享到這里就結束了，如果解決了您的問題，我們非常高興。
