前序遍歷遞歸演算法

① 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***(注意*代表空格，因為空格你看不到就不好表示).

② 二叉樹先序遍歷遞歸演算法問題

status preordertraverse(bitree T,status (*visit)(telemtype e))
{
if(T) //判斷跟指針是否為空，若不空，則進入
{
if(visit (T->data)) //若不空，訪問該指針所指向的關鍵字
if(preordertraverse(T->lchild,visit)) //若不空，訪問該指針的左孩子
if(preordertraverse(T->rchild,visit)) //若不空，訪問該指針的右孩子
return OK;
return ERROR;

}else return OK;
}
}else return OK;
}

③ 建立二叉樹，並利用遞歸方法實現先序、中序、後序遍歷。

#include
#include
#include
#include
#include

using namespace std;

struct node;

typedef node *tree;

struct node{
char data;
tree lchild,rchild;
};

tree bt;

void build(tree &bt){
char ch;
ch=getchar();
if(ch!='.'){
bt=new node;
bt->data=ch;
build(bt->lchild);
build(bt->rchild);
}
else
bt=NULL;
}

void prework(){
ios::sync_with_stdio(false);
//freopen("data.in","r",stdin);
build(bt); //建樹
}

void preorder(tree bt){
if(bt){
cout<data;
preorder(bt->lchild);
preorder(bt->rchild);
}
}

void midorder(tree bt){
if(bt){
preorder(bt->lchild);
cout<data;
preorder(bt->rchild);
}
}

void backorder(tree bt){
if(bt){
preorder(bt->lchild);
cout<data;
preorder(bt->rchild);
}
}

void mainwork(){
preorder(bt);
cout<<endl;
midorder(bt);
cout<<endl;
backorder(bt);
}

int main(){
prework();
mainwork();
return 0;
}
//我這里輸入的東西是要求葉子節點的子節點為'.'
但仍無鈴聲，則送維修店維修。三無受話現象：

④ 用遞歸演算法先序中序後序遍歷二叉樹

1、先序

void PreOrderTraversal(BinTree BT)

{

if( BT )

{

printf(「%d 」, BT->Data); //對節點做些訪問比如列印

PreOrderTraversal(BT->Left); //訪問左兒子

PreOrderTraversal(BT->Right); //訪問右兒子

}

}

2、中序

void InOrderTraversal(BinTree BT)

{

if(BT)

{

InOrderTraversal(BT->Left);

printf("%d ", BT->Data);

InOrderTraversal(BT->Right);

}

}

3、後序

void PostOrderTraversal(BinTree BT)

{

if (BT)

{

PostOrderTraversal(BT->Left);

PostOrderTraversal(BT->Right);

printf("%d ", BT->Data);

}

}

(4)前序遍歷遞歸演算法擴展閱讀：

注意事項

1、前序遍歷

從整棵二叉樹的根結點開始，對於任意結點VV，訪問結點VV並將結點VV入棧，並判斷結點VV的左子結點LL是否為空。若LL不為空，則將LL置為當前結點VV；若LL為空，則取出棧頂結點，並將棧頂結點的右子結點置為當前結點VV。

2、中序遍歷

從整棵二叉樹的根結點開始，對於任一結點VV，判斷其左子結點LL是否為空。若LL不為空，則將VV入棧並將L置為當前結點VV；若LL為空，則取出棧頂結點並訪問該棧頂結點，然後將其右子結點置為當前結點VV。重復上述操作，直到當前結點V為空結點且棧為空，遍歷結束。

3、後序遍歷

將整棵二叉樹的根結點入棧，取棧頂結點VV，若VV不存在左子結點和右子結點，或VV存在左子結點或右子結點，但其左子結點和右子結點都被訪問過了，則訪問結點VV，並將VV從棧中彈出。若非上述兩種情況，則將VV的右子結點和左子結點依次入棧。重復上述操作，直到棧為空，遍歷結束。

⑤ 樹的遞歸演算法

答案是正確的啊。
if(root)就是如果root!=0，這里root是一個指針，指向結構體struct node的指針，第一次進入函數它就是指向根節點A的指針
運行步驟：
如果指向A的指針不為空(不為0),列印'A',
遞歸調用函數指向A的左孩子節點
如果指向B的指針不為空(不為0),列印'B',
遞歸調用函數指向B的左孩子節點
如果指向C的指針不為空(不為0),列印'C',
遞歸調用函數指向C的左孩子節點
由於C的左孩子節點為空，所以本次遞歸traversal(root->lchild)結束，回到上一層遞歸中即從C的左孩子節點回到C中，然後執行traversal(root->lchild)這一句下面一句，列印出'C'
然後遞歸調用traversal(root->rchild);指向C的右孩子節點
如果指向E的指針不為空(不為0),列印'E',
然後再遞歸指向E的左孩子節點，為空再返回到E中，再次列印出'E',然後再指向E的右孩子節點，為空，E的遞歸結束返回上一層遞歸即C中，然後C也到達末尾結束返回上一層遞歸B中，然後執行traversal(root->lchild)這一句下面一句，列印出'B'
然後遞歸調用traversal(root->rchild);指向B的右孩子節點
......
如此不斷進入某個節點的子節點操作後再從子節點返回父節點，層層進入再層層向上返回，從而遍歷樹中各個節點，最終得出結果：
A B C C E E B A D F F D G G

⑥ 二叉樹的中序、前序、後序的遞歸、非遞歸遍歷演算法，層次序的非遞歸遍歷演算法的實現，應包含建樹的實現。

二叉樹的遍歷是指按照一定次序訪問二叉樹中的所有節點，且每個節點僅被訪問一次的過程。是最基本的運算，是其他運算的基礎。
二叉樹有兩種存儲結構：順序存儲和鏈式存儲
順序存儲： （對完全二叉樹來說，可以充分利用存儲空間，但對於一般的二叉樹，只有少數的存儲單元被利用）
[cpp] view plain
typedef struct
{
ElemType data[MaxSize];
int n;
}SqBTree;
鏈式存儲：
[csharp] view plain
typedef struct node
{
ElemType data;
struct node *lchild;
struct node *rchild;
} BTNode;

二叉樹三種遞歸的遍歷方法：
先序遍歷 訪問根節點→先序遍歷左子樹→先序遍歷右子樹
中序遍歷 中序遍歷左子樹→訪問根節點→中序遍歷右子樹
後序遍歷 後序遍歷左子樹→後序遍歷右子樹→訪問根節點
二叉樹遍歷的遞歸演算法：
[cpp] view plain
void preOrder(BTNode *b) //先序遍歷遞歸演算法
{
if (b!=NULL)
{
visit(b);
preOrder(b->lchild);
preOrder(b->rchild);
}
}
void InOrder(BTNode *b) //中序遍歷遞歸演算法
{
if(b!=NULL)
{
InOrder(b->lchild);
visit(b);
InOrder(b->rchild);
}
}
void PostOrder(BTNode *b) //後序遍歷遞歸演算法
{
if(b!=NULL){
PostOrder(b->lchild);
PostOrder(b->rchild);
visit(b);
}
}
二叉樹非遞歸遍歷演算法：
有兩種方法：①用棧存儲信息的方法 ②增加指向父節點的指針的方法 暫時只介紹下棧的方法
先序遍歷：
[cpp] view plain
void PreOrder(BTNode *b)
{
Stack s;
while(b!=NULL||!s.empty())
{
if(b!=NULL){
visit(b);
s.push(b);
b=b->left;
}
else{
b=s.pop();
b=b->right;
}
}
}
中序遍歷：
[cpp] view plain
void InOrder(BTNode *b){
Stack s;
while(b!=NULL||!s.empty()){
if (b!=NULL)
{
s.push(b);
s=s->left
}
if(!s.empty()){
b=s.pop();
visit(b);
b=b->right;
}
}
}
後序遍歷：
[cpp] view plain
void PostOrder(BTNode *b){
Stack s;
while(b!=NULL){
s.push(b);
}
while(!s.empty()){
BTNode* node=s.pop();
if(node->bPushed){
visit(node);
}
else{
s.push(node);
if(node->right!=NULL){
node->right->bPushed=false;
s.push(node->right);
}
if(node->left!=NULL){
node->left->bpushed=false;
s.push(node->left);
}
node->bPushed=true; //如果標識位為true,則表示入棧
}
}
}
層次遍歷演算法：（用隊列的方法）
[cpp] view plain
void levelOrder(BTNode *b){
Queue Q;
Q.push(b);
while(!Q.empty()){
node=Q.front();
visit(node);
if(NULL!=node->left){
Q.push(node->left);
}
if(NULL!=right){
Q.push(node->right);
}
}
}<span style=""></span>
已知先序和中序求後序的演算法：（已知後序和中序求先序的演算法類似，但已知先序和後序無法求出中序）
[cpp] view plain
int find(char c,char A[],int s,int e) /* 找出中序中根的位置。 */
{
int i;
for(i=s;i<=e;i++)
if(A[i]==c) return i;
}
/* 其中pre[]表示先序序，pre_s為先序的起始位置，pre_e為先序的終止位置。 */
/* 其中in[]表示中序，in_s為中序的起始位置，in_e為中序的終止位置。 */
/* pronum()求出pre[pre_s～pre_e]、in[in_s～in_e]構成的後序序列。 */
void pronum(char pre[],int pre_s,int pre_e,char in[],int in_s,int in_e)
{
char c;
int k;
if(in_s>in_e) return ; /* 非法子樹，完成。 */
if(in_s==in_e){printf("%c",in[in_s]); /* 子樹子僅為一個節點時直接輸出並完成。 */
return ;
}
c=pre[pre_s]; /* c儲存根節點。 */
k=find(c,in,in_s,in_e); /* 在中序中找出根節點的位置。 */
pronum(pre,pre_s+1,pre_s+k-in_s,in,in_s,k-1); /* 遞歸求解分割的左子樹。 */
pronum(pre,pre_s+k-in_s+1,pre_e,in,k+1,in_e); /* 遞歸求解分割的右子樹。 */
printf("%c",c); /* 根節點輸出。 */
}
main()
{
char pre[]="abdc";
char in[]="bdac";
printf("The result:");
pronum(pre,0,strlen(in)-1,in,0,strlen(pre)-1);
getch();
}

⑦ 建立二叉樹，實現前序遍歷的非遞歸演算法及遞歸演算法<有追加>

找本數據結構書，自己看去。
/////////////////////////////////
地球人都知道遍歷二叉樹不用遞歸就只能用棧了
另：
hope1262你說的那個是堆，數組存儲二叉樹，他的這個明顯不是
////////////////////////////////
遞歸在編譯器實現的時候也是用堆棧實現的。遞歸的時候是從上向下的，而由於堆棧是先進後出，所以壓棧的時候要先壓後面的結點。
一棵樹分為左子樹、根和右子樹，所以先把右子樹壓入棧，輸出根，然後再壓入左子樹，壓左子樹時又重復這一過程了，直左子樹為空；這時開始從棧中把之前壓入的右子樹pop出來，再重復上面的過程，直到棧為空。
代碼：
void PreOrder(BiTNode *BT)
{
push(BT);
while(!IsEmpty)
{
pop(BT);
while(BT)
{
VISIT(BT);
push(BT->rchild);
BT=BT->lchild;
}
}
}
你的代碼自己改吧，記得先把根壓進棧。

⑧ c語言實現二叉樹的先序,中序,後序的遞歸和非遞歸演算法和層次遍歷演算法

#include<malloc.h> // malloc()等
#include<stdio.h> // 標准輸入輸出頭文件，包括EOF(=^Z或F6)，NULL等
#include<stdlib.h> // atoi()，exit()
#include<math.h> // 數學函數頭文件，包括floor()，ceil()，abs()等

#define ClearBiTree DestroyBiTree // 清空二叉樹和銷毀二叉樹的操作一樣

typedef struct BiTNode
{
int data; // 結點的值
BiTNode *lchild,*rchild; // 左右孩子指針
}BiTNode,*BiTree;

int Nil=0; // 設整型以0為空
void visit(int e)
{ printf("%d ",e); // 以整型格式輸出
}
void InitBiTree(BiTree &T)
{ // 操作結果：構造空二叉樹T
T=NULL;
}

void CreateBiTree(BiTree &T)
{ // 演算法6.4：按先序次序輸入二叉樹中結點的值(可為字元型或整型，在主程中定義)，
// 構造二叉鏈表表示的二叉樹T。變數Nil表示空(子)樹。修改
int number;
scanf("%d",&number); // 輸入結點的值
if(number==Nil) // 結點的值為空
T=NULL;
else // 結點的值不為空
{ T=(BiTree)malloc(sizeof(BiTNode)); // 生成根結點
if(!T)
exit(OVERFLOW);
T->data=number; // 將值賦給T所指結點
CreateBiTree(T->lchild); // 遞歸構造左子樹
CreateBiTree(T->rchild); // 遞歸構造右子樹
}
}

void DestroyBiTree(BiTree &T)
{ // 初始條件：二叉樹T存在。操作結果：銷毀二叉樹T
if(T) // 非空樹
{ DestroyBiTree(T->lchild); // 遞歸銷毀左子樹，如無左子樹，則不執行任何操作
DestroyBiTree(T->rchild); // 遞歸銷毀右子樹，如無右子樹，則不執行任何操作
free(T); // 釋放根結點
T=NULL; // 空指針賦0
}
}

void PreOrderTraverse(BiTree T,void(*Visit)(int))
{ // 初始條件：二叉樹T存在，Visit是對結點操作的應用函數。修改演算法6.1
// 操作結果：先序遞歸遍歷T，對每個結點調用函數Visit一次且僅一次
if(T) // T不空
{ Visit(T->data); // 先訪問根結點
PreOrderTraverse(T->lchild,Visit); // 再先序遍歷左子樹
PreOrderTraverse(T->rchild,Visit); // 最後先序遍歷右子樹
}
}

void InOrderTraverse(BiTree T,void(*Visit)(int))
{ // 初始條件：二叉樹T存在，Visit是對結點操作的應用函數
// 操作結果：中序遞歸遍歷T，對每個結點調用函數Visit一次且僅一次
if(T)
{ InOrderTraverse(T->lchild,Visit); // 先中序遍歷左子樹
Visit(T->data); // 再訪問根結點
InOrderTraverse(T->rchild,Visit); // 最後中序遍歷右子樹
}
}

void PostOrderTraverse(BiTree T,void(*Visit)(int))
{ // 初始條件：二叉樹T存在，Visit是對結點操作的應用函數
// 操作結果：後序遞歸遍歷T，對每個結點調用函數Visit一次且僅一次
if(T) // T不空
{ PostOrderTraverse(T->lchild,Visit); // 先後序遍歷左子樹
PostOrderTraverse(T->rchild,Visit); // 再後序遍歷右子樹
Visit(T->data); // 最後訪問根結點
}
}

void main()
{
BiTree T;
InitBiTree(T); // 初始化二叉樹T
printf("按先序次序輸入二叉樹中結點的值,輸入0表示節點為空，輸入範例：1 2 0 0 3 0 0\n");
CreateBiTree(T); // 建立二叉樹T
printf("先序遞歸遍歷二叉樹：\n");
PreOrderTraverse(T,visit); // 先序遞歸遍歷二叉樹T
printf("\n中序遞歸遍歷二叉樹：\n");
InOrderTraverse(T,visit); // 中序遞歸遍歷二叉樹T
printf("\n後序遞歸遍歷二叉樹：\n");
PostOrderTraverse(T,visit); // 後序遞歸遍歷二叉樹T
}

⑨ 關於二叉樹先序遍歷的遞歸演算法問題

你把遞歸理解錯了，遞歸調用我用下面這種方法表示
Preorder->Preorder->Preorder->Preorder->Preorder->Preorder->Preorder
每一個Preoder都是去訪問一個節點的左子樹，當最後的葉子沒有左節點時，是最有一次調用Preorder返回了，繼續倒數第二次調用Preorder的代碼。如下

void Preorder (BiTree T,
void( *visit)(TElemType& e))
{ // 先序遍歷二叉樹
if (T) {
visit(T->data); // 訪問結點
Preorder(T->lchild, visit); // 最後一次沒有左子樹了，返回到這里
Preorder(T->rchild, visit);// 繼續訪問右子樹
}
}

⑩ 先序遍歷二叉樹的遞歸演算法怎樣理解（嚴蔚敏主編）

先序調用的時候，遞歸函數，先序函數會一直遞歸，直到t->next為空，即t為葉節點，需要注意的是當t->next 為空時，函數的實參沒有傳過去，所以t指向葉結點的父節點，更要注意的是，先序調用的遞歸函數還沒執行完，在先序調用的最里層，要執行這個函數的最後一個語句，即先序訪問右子樹。
在了解遞歸函數時，要注意函數是一層一層執行的，把沒有調用的函數看作哦是第一層，第一次調用的時候，，勢必會第二次遇到調用函數，變成第二層，，，，