二叉樹結構體定義：
struct node {
int data;
struct node *left;
struct node *right;
};
//非遞回代碼模板
先序遍歷：
void preOrder( struct node *root )
{
struct node **stack[500];
int top=-1;
struct node *p=root;
while(p!=NULL||top>=0)
{
if(p!=NULL) //從這里開始，這個if else塊我很難理解，一步一步推算的話我是知道代碼怎么走的，但是我不理解為什么會這樣走。大佬們是怎么想的？
{
printf("%d ",p->data);
stack[++top]=p;
p=p->left;
}
else //尤其是這個else塊感覺很有靈性，如何更好地理解這個else塊？
{
p=stack[top--];
p=p->right;
}
}
}
中序遍歷：
void inOrder( struct node *root)
{
struct node **stack[500];
int top=-1;
struct node *p=root;
while(p!=NULL||top>=0)
{
if(p!=NULL) //中序遍歷的也是一樣的疑惑
{
stack[++top]=p;
p=p->left;
}
else
{
p=stack[top--];
printf("%d ",p->data);
p=p->right;
}
}
}
后序遍歷：
void postOrder( struct node *root)
{
struct node **stack[500];
int top=-1;
struct node *p=root,*r=NULL;
while(p!=NULL||top>=0)
{
if(p!=NULL)
{
stack[++top]=p;
p=p->left;
}
else
{
p=stack[top];
if(p->right!=NULL&&p->right!=r)
p=p->right;
else
{
top--;
printf("%d ",p->data);
r=p;
p=NULL;
}
}
}
}
uj5u.com熱心網友回復：
這個就看個人的思維能力了，其實思路都挺簡單的，就看你對堆疊的入堆疊出堆疊控制的想象能力了。前序遍歷的思路就是，先遍歷父節點，再遍歷左節點，后遍歷右節點。
所以
if(p!=NULL) 就是判斷左節點是否為空，如果不為空，說明還能向左走，就一直遍歷左節點（先列印父節點是表為先遍歷父節點，然后把父節點壓堆疊后再p=父節點的左節點去遍歷左節點）
else就是如果左節點為空，也就表示沒有左節點了（往左走不通了），就改為遍歷右節點（父節點出堆疊，然后p=父節點的右節點繼續遍歷右節點）
中序遍歷的思路就是，先遍歷左節點，再遍歷父節點，后遍歷右節點
所以
if(p!=NULL) 也是判斷左節點是否為空，如果不為空，說明還能向左走，就一直遍歷左節點（把父節點壓堆疊，然后p=父節點的左節先遍歷左節點）
else就是如果左節點為空，也就是沒有左節點了（往左走不通了），就把父節點出堆疊，然后列印父節點（表示遍歷完左節點以后接著遍歷父節點），然后再p=父節點的右節點繼續遍歷右節點
后序遍歷的思路就是，先遍歷左節點，再遍歷右節點，后遍歷父節點
所以
if(p!=NULL) 也是判斷左節點是否為空，如果不為空，說明還能向左走，就一直遍歷左節點（把父節點壓堆疊，p=父節點的左節點先遍歷左節點）
else就是如果左節點為空，也就是沒有左節點了（往左走不通了），就繼續遍歷右節點，注意，此時父節點并沒出堆疊（因為右節點遍歷完才遍歷父節點，所以父節點一時半會還要待在堆疊里，遍歷完右節點才能出堆疊），同時為了避免重復遍歷右節點（因為父節點還在堆疊頂就會取到相同的父節點，這樣右節點就會相同），所以用個r來記錄右節點是否已經遍歷過，這也就是在else里的if else的意義。如果右節點已經遍歷過了，那么父節點就開始出堆疊，然后列印父節點（表示遍歷父節點）
uj5u.com熱心網友回復：
我懷疑是自己的代碼寫的太少了
uj5u.com熱心網友回復：
所有遞回變成非遞回，都可以使用list<>，自己保存堆疊，然后遍歷list<>，解決轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/14264.html
標籤：C語言
上一篇：大佬們，請問怎么讀取mdb檔案？