c語言中前序遍歷,先序遍歷c語言

本文目錄一覽：

• 1、C語言二叉樹前，中，後遍厲序列有什麼規律，就是已知倆個，如何推出第三個，謝謝
• 2、求解釋！！！！中序遍歷怎麼找到前序結點？？？？（c語言）
• 3、C語言中，遞歸先序遍歷和非遞歸先序遍歷的有何區別?各自優缺點?
• 4、C語言中，到底先序遍歷、中序遍歷、後續遍歷怎麼看的…真的快瘋掉了！求高人指點指點…淚目
• 5、如何用C語言實現層次遍歷二叉樹?

C語言二叉樹前，中，後遍厲序列有什麼規律，就是已知倆個，如何推出第三個，謝謝

概念弄懂了，這個就懂了！

假設有棵樹，長下面這個樣子，它的前序遍歷，中序遍歷，後續遍歷都很容易知道。

前序:         GDAFEMHZ

中序:            ADEFGHMZ

後續:       AEFDHZMG

現在，假設僅僅知道前序和中序遍歷，如何求後序遍歷呢？比如，已知一棵樹的前序遍歷是」GDAFEMHZ」，而中序遍歷是」ADEFGHMZ」應該如何求後續遍歷?

第一步，root最簡單，前序遍歷的第一節點G就是root。

第二步，繼續觀察前序遍歷GDAFEMHZ，除了知道G是root，剩下的節點必然是root的左右子樹之外，沒法找到更多信息了。

第三步，那就觀察中序遍歷ADEFGHMZ。其中root節點G左側的ADEF必然是root的左子樹，G右側的HMZ必然是root的右子樹。

第四步，觀察左子樹ADEF，左子樹的中的根節點必然是大樹的root的leftchild。在前序遍歷中，大樹的root的leftchild位於root之後，所以左子樹的根節點為D。

第五步，同樣的道理，root的右子樹節點HMZ中的根節點也可以通過前序遍歷求得。在前序遍歷中，一定是先把root和root的所有左子樹節點遍歷完之後才會遍歷右子樹，並且遍歷的右子樹的第一個節點就是右子樹的根節點。

如何知道哪裡是前序遍歷中的左子樹和右子樹的分界線呢？通過中序遍歷去數節點的個數。

在上一次中序遍歷中，root左側是A、D、E、F，所以有4個節點位於root左側。那麼在前序遍歷中，必然是第1個是G，第2到第5個由A、D、E、F過程，第6個就是root的右子樹的根節點了，是M。

第六步，觀察發現，上面的過程是遞歸的。先找到當前樹的根節點，然後劃分為左子樹，右子樹，然後進入左子樹重複上面的過程，然後進入右子樹重複上面的過程。最後就可以還原一棵樹了。

第七步，其實，如果僅僅要求寫後續遍歷，甚至不要專門佔用空間保存還原後的樹。只需要稍微改動第六步，就能實現要求。

時間問題：只能炒一些來答你： 

求解釋！！！！中序遍歷怎麼找到前序結點？？？？（c語言）

中序遍歷可記作為：左根右。即：首先遍歷左子樹，然後訪問根結點，最後遍歷右子樹。在遍歷左、右子樹時，仍然先遍歷左子樹，再訪問根結點，最後遍歷右子樹。應多畫圖，我以前學數據結構時也是多畫圖，畫圖的話就容易理解。謝謝。

C語言中，遞歸先序遍歷和非遞歸先序遍歷的有何區別?各自優缺點?

1、遞歸就是函數調用函數本身，運行起來就是函數嵌套函數，層層嵌套，所以函數調用、參數堆棧都是不小的開銷，但是程序簡單。

2、非遞歸就是不斷地對參數入棧、出棧，省去了函數層層展開、層層調用的開銷。雖然參數出入棧次數多了，但是一般都開闢固定的足夠大的內存來一次性開闢、重複使用。

3、非遞歸是從堆棧的角度來編寫程序，速度快，但代碼複雜。

遞歸是從問題本身的邏輯角度來編寫，雖然速度相對慢，但代碼容易理解。

如果對速度要求不高，建議用遞歸方式。

4、摘錄例子如下：

#include stdio.h

#include stdlib.h

typedef struct BiTNode

{

char data;

struct BiTNode *lchild,*rchild;

} BiTNode,*BiTree;//二叉樹的節點類型

typedef struct QNode

{

BiTNode data;

struct QNode *next;

} QNode,*QueuePtr;//隊列節點類型

typedef struct

{

QueuePtr front;

QueuePtr rear;

}LinkQueue;//隊列的頭尾指針

void InitQueue(LinkQueue *Q)//創建隊列

{

Q-front=Q-rear=(QueuePtr)malloc(sizeof(QNode));

Q-rear-next=NULL;

}

void EnQueue(LinkQueue *Q,BiTNode e)//入隊操作

{

QueuePtr p;

p=(QueuePtr)malloc(sizeof(QNode));

p-data=e;

p-next=NULL;

Q-rear-next=p;

Q-rear=p;

}

BiTNode DeQueue(LinkQueue *Q)//出對操作

{

BiTNode e;QueuePtr p;

p=Q-front-next;

e=p-data;

Q-front-next=p-next;

if(Q-rear==p)

Q-rear=Q-front;

free(p);

return (e);

}

int QueueEmpty(LinkQueue *Q)//判斷隊列是否為空

{

if(Q-front==Q-rear )

return 1;

else

return 0;

}

BiTree CreateBiTree()//創建二叉樹

{

char p;BiTree T;

scanf(“%c”,p);

if(p==’ ‘)

T=NULL;

else

{

T=(BiTNode *)malloc(sizeof(BiTNode));

T-data=p;

T-lchild=CreateBiTree(T-lchild);

T-rchild=CreateBiTree(T-rchild);

}

return (T);

}

void PreOrder(BiTree T)//先序

{

if(T!=NULL)

{

printf(“%c”,T-data);

PreOrder(T-lchild);

PreOrder(T-rchild);

}

}

void LevelOrder(BiTree T)//層次遍歷

{

LinkQueue Q; BiTNode p;

InitQueue(Q);

EnQueue(Q,*T);

while(!QueueEmpty(Q))

{

p = DeQueue(Q);

printf(“%c”,p.data);

if(p.lchild!=NULL)

EnQueue(Q,*(p.lchild));

if(p.rchild!=NULL)

EnQueue(Q,*(p.rchild));

}

}

void main()

{

BiTree Ta;

Ta=CreateBiTree();

printf(“層次遍歷:”);

printf(“\n”);

LevelOrder(Ta);

printf(“\n”);

printf(“先序遍歷:”);

printf(“\n”);

PreOrder(Ta);

}

層次使用非遞歸的，用到隊列

先序是用遞歸的

創建樹使用先序遞歸建樹

輸入個例子：

abc**de*f**g***(注意*代表空格，因為空格你看不到就不好表示).

C語言中，到底先序遍歷、中序遍歷、後續遍歷怎麼看的…真的快瘋掉了！求高人指點指點…淚目

先序遍歷就是「根左右」，不管你現在在哪個節點，都是按這種規則。上面的題目：根是A，左是B，右是C，所以是A-》B，在當前根節點B，還是按上述規則，那麼接下來到D，D之後沒有子節點，返回B，遍歷E-》X，X之後沒有子節點，返回E，E的子節點都遍歷完了，返回B，B的子節點都遍歷完了，返回A，接下來遍歷右子樹，規則同上。

中序遍歷就是「左根右」，對於A來說，先遍歷B，對於B來說，先遍歷D，對於D來說，已經沒有左子樹，所以遍歷D，D沒有右子樹,返回B，遍歷B，B有右子樹E，對於E來說，先遍歷X，完了返回E，E完了返回B，B完了返回A，遍歷A，遍歷右子樹，規則同上。

後序遍歷就是跟先序遍歷相反的，先遍歷右子樹，再左子樹，最後才是根。

好好思考一下。

如何用C語言實現層次遍歷二叉樹?

下面是c語言的前序遍歷二叉樹的算法，在這裡假設的節點元素值假設的為字符型，

說明：算法中用到了結構體，也用到了遞歸的方法，你看看怎麼樣，祝你好運！

#include”stdio.h”

typedef

char

elemtype;

typedef

struct

node

//定義鏈表結構

{

elemtype

data;

//定義節點值

struct

note

*lchild;

//定義左子節點值

struct

note

*rchild;

//定義右節點值

}btree;

preorder(btree

*root)

//前序遍歷

{

if(roof!=null)

//如果不是空節點

{

printf(“%c\n”,root-data);

//輸出當前節點

preorder(root-lchild);

//遞歸前序遍歷左子節點

preorder(root-rchild);

//遞歸前序遍歷右子節點

}

return;

//結束

}