二叉樹的先序遍歷非遞歸演算法

⑴ 二叉樹非遞歸遍歷的演算法

以下為先序，中序，後序三種遞歸演算法

#include
#define MAX 30
typedef struct TreeNode
{
char a;
TreeNode *left;
TreeNode *right;
}TreeNode,*BinTree;
typedef struct
{
TreeNode* data[MAX];
int top;
}SeqStack;
void InitStack(SeqStack &S)
{
S.top=0;
}
int StackEmpty(SeqStack S)
{
if(S.top==0)
return 1;
else return 0;
}
int StackFull(SeqStack S)
{
if(S.top==MAX) return 1;
else return 0;
}
void Push(SeqStack &S,TreeNode *node)
{
if(!StackFull(S))
{
S.data[S.top]=node;
S.top++;
}
else cout<<"Stack is full!\n";
}
void Pop(SeqStack &S,TreeNode* &e)
{
if(!StackEmpty(S))
{
S.top--;
e=S.data[S.top];
}
else cout<<"Stack is empty!";
}
TreeNode* GetTop(SeqStack S)
{
if(!StackEmpty(S))
{
TreeNode *node;
node=S.data[S.top-1];
return node;
}
else cout<<"Stack is empty!";
}

void CreateBinTree(BinTree &T)
{
char b;
cin>>b;
if(b=='0')T=NULL;
else
{
T=new TreeNode;
T->a=b;
CreateBinTree(T->left);
CreateBinTree(T->right);
}
}
void Inorder(BinTree T)
{
TreeNode * p;
SeqStack S;
p=T;
InitStack(S);
while(!StackEmpty(S)||p)
{
while(p)
{
Push(S,p);
p=p->left;
}
if(!StackEmpty(S))
{
Pop(S,p);
cout cout<<"\nA----------二叉樹的建立\n";
cout<<"\nB----------非遞歸先序遍歷\n";
cout<<"\nC----------非遞歸中序遍歷\n";
cout<<"\nD----------非遞歸後序遍歷\n";
cout<<"\nX----------退出\n";
}
void main()
{
BinTree T;
char ch='\0';
bool flag=true;
while(flag)
{
info();
cin>>ch;
switch(ch)
{
case'a':
case'A':
cout<<"請按先序次序輸入結點，空結點用'0'表示:\n";
CreateBinTree(T);
cout<<"二叉樹建立成功!\n";
break;
case'b':
case'B':
cout<<"先序遍歷的結果為:\n";
Preorder(T);
break;
case'c':
case'C':
cout<<"中序遍歷的結果為:\n";
Inorder(T);
break;
case'd':
case'D':
cout<<"後序遍歷的結果為:\n";
Postorder(T);
break;
case'x':
case'X':
flag=false;
break;
default:
cout<<"輸入無效,請重新輸入!\n";
}
}
}

⑵ 二叉樹先序遍歷遞歸演算法和非遞歸演算法本質區別

在前面一文，說過二叉樹的遞歸遍歷演算法（二叉樹先根（先序）遍歷的改進），此文主要講二叉樹的非遞歸演算法，採用棧結構
總結先根遍歷得到的非遞歸演算法思想如下：
1）入棧，主要是先頭結點入棧，然後visit此結點
2）while，循環遍歷當前結點，直至左孩子沒有結點
3）if結點的右孩子為真，轉入1）繼續遍歷，否則退出當前結點轉入父母結點遍歷轉入1）
先看符合此思想的演算法：

[cpp] view plain print?
int (const BiTree &T, int (*VisitNode)(TElemType data))
{
if (T == NULL)
{
return -1;
}

BiTNode *pBiNode = T;
SqStack S;
InitStack(&S);
Push(&S, (SElemType)T);

while (!IsStackEmpty(S))
{
while (pBiNode)
{
VisitNode(pBiNode->data);
if (pBiNode != T)
{
Push(&S, (SElemType)pBiNode);
}
pBiNode = pBiNode->lchild;
}
if(pBiNode == NULL)
{
Pop(&S, (SElemType*)&pBiNode);
}
if ( pBiNode->rchild == NULL)
{
Pop(&S, (SElemType*)&pBiNode); //如果此時棧已空，就有問題
}
pBiNode = pBiNode->rchild;
}

return 0;
}

⑶ 求二叉樹的前序遍歷和後序遍歷的演算法（非遞歸）

網路一下就可以知道答案了。直接搜」二叉樹的前序遍歷和後序遍歷的演算法「

第一條就是：

http://blog.csdn.net/sky04/article/details/4510266

我只解釋一下先序遍歷非遞歸演算法，其他的自學一下吧！：

//先序遍歷非遞歸演算法

voidPreOrderUnrec(Bitree*t)
{
Stacks;
StackInit(s);//初始化
Bitree*p=t;//二叉樹根節點

while(p!=NULL||!StackEmpty(s))
{
while(p!=NULL)//遍歷左子樹
{
visite(p->data);
push(s,p);
p=p->lchild;//lchild左子樹
}

if(!StackEmpty(s))//通過下一次循環中的內嵌while實現右子樹遍歷
{
p=pop(s);
p=p->rchild;//rchild右子樹
}//endif

}//endwhile
}

/*Stacks；創建堆棧。這也是堆棧的一個應用。既然你已經學到了二叉樹，就應該知道堆棧，可以把以前編寫的堆棧程序拿來用。
POP，PUSH堆棧的彈出，壓棧。
按照該程序步驟，來演示s和指針p的內容：（完全二叉樹為例）
前序遍歷次序為：ABCDEFG
1.第一次執行while語句後
棧s[底部，ABC]p=NULL訪問了：ABC節點
2.第一次執行if
棧s[底部，AB]p=NULL訪問了：ABC節點由於c的右子樹為空，所以p=NULL
3.第二次跳過了while
4.第二次執行if
棧s[底部，A]p指向了D訪問了：ABC節點
5.第三次執行while語句後
棧s[底部，AD]p=NULL訪問了：ABCD節點，本次while循環，只訪問了D
。
。
。
剩下步驟的自己來吧!
實際上，遞歸也是在操作堆棧。
一般的書上應該有這么類似的話：
「利用一個輔助堆棧，可以將遞歸演算法轉化為等價的分遞歸演算法」

*/

⑷ 二叉樹非遞歸先序遍歷

題目是
1）問題描述：在主程序中提供下列菜單：
1…建立樹
2…前序遍歷樹
3…中序(非遞歸)遍歷樹
4…後序遍歷樹
0…結束
2）實驗要求：定義下列過程：
CreateTree(): 按從鍵盤輸入的前序序列，創建樹
PreOrderTree()：前序遍歷樹（遞歸）
InOrderTree()：中序(非遞歸)遍歷樹
LaOrderTree(): 後序遍歷樹（遞歸）
我做得是：
求幫忙改錯 或者給我一個程序 求啊啊啊 要下課了 啊啊啊啊
及時的話有追加啊啊啊啊
#include <iostream.h>
#include <stdio.h>
#include <malloc.h>
#define MaxNode 100
typedef int ElemType;
typedef struct node
{
ElemType data;
struct node *lchild;
struct node *rchild;
}BTNode;

void CreateTree(BTNode *&b,char *str)//建立一個二叉樹
{
BTNode *St[100];
BTNode *p=NULL;
int top=-1,k,j=0;
char ch;
b=NULL;
ch=str[j];
while(ch!='\0')
{
switch(ch)
{
case '(':top++;St[top]=p;k=1;break;
case ')':top--;break;
case ',':k=2;break;
default:p=(BTNode *)malloc(sizeof(BTNode));
p->data=ch;
p->lchild=p->rchild=NULL;
if(b==NULL)
b=p;
else
{
switch(k)
{
case 1:St[top]->lchild=p;break;
case 2:St[top]->rchild=p;break;
}
}
}
j++;
ch=str[j];
}
}

void PreOrder(BTNode *b)//前序遍歷
{
if(b!=NULL)
{
printf("%c ",b->data);
PreOrder(b->lchild);
PreOrder(b->rchild);
}
}

void InOrder(BTNode *b)//中序遍歷
{

BTNode *p,*stack[MaxNode];
int top=0;
if(b==NULL) return;
p=b;
while(!(p == NULL && top == 0))
{
while(p!=NULL)
{

if(top<MaxNode-1){stack[top]=p;top++;}
else{printf("棧溢出");return;}
p=p->lchild;
}
if(top<=0)return;
else{top--;p=stack[top];printf("%c",p->data);p=p->rchild;}
}
}

void LaOrder(BTNode *b)//後序遍歷
{
if(b!=NULL)
{
LaOrder(b->lchild);
LaOrder(b->rchild);
printf("%c ",b->data);
}
}
void main()
{
int number;
BTNode *b=NULL;
cout<<" 【1】創建樹"<<endl<<endl;
cout<<" 【2】先序遍歷樹"<<endl<<endl;
cout<<" 【3】中序遍歷樹"<<endl<<endl;
cout<<" 【4】後序遍歷樹"<<endl<<endl;
cout<<" 【5】結束"<<endl<<endl<<endl;
cout<<"請輸入您的選擇"<<endl;
cin>>number;
while(number!=5)
{

if(number==1)
{
char str[100];
printf("請輸入：");
scanf("%s",&str);
CreateTree(b,str);
printf("樹創建成功!\n");
}
else if(number==2)
{
if(b==NULL)
{
printf("對不起，您還沒有創建樹!\n");
}
else
{
PreOrder(b);
printf("\n");
}
}
else if(number==3)
{
if(b==NULL)
{
printf("對不起，您還沒有創建樹!\n");
}
else
{
InOrder(b);
printf("\n");
}
}
else if(number==4)
{
if(b==NULL)
{
printf("對不起，您還沒有創建樹!\n");
}
else
{
LaOrder(b);
printf("\n");
}
}
printf("請輸入您的選擇:\n");
scanf("%d",&number);
}

}

//以上內容來源於網路知道。http://..com/question/259268815.html
希望對你有幫助

⑸ 先序遍歷二叉樹的非遞歸演算法

InitStack(S);//初始化棧
p=T;//取棧頂
while(P||!StackEmpty(S)){
//P存在或者棧非空
if(p)
{
//p非空，即左子樹或者右子樹存在
Push(S,p);
//將左子樹入棧
p=p->lchild;
//取下一個左子樹
}
else{
Pop(S,p);
//出棧，相當於先序遍歷了，因為左子樹都TMD入棧了，現在反向輸出
p=p->rchild;
//彈出一個左子樹，就同時取其右子樹右子樹，然後又跳到這個if的最開頭那裡，p存在的那個分支。接下來再取右子樹的左子樹
}
}
//其實，用遞歸也許你更能理解一些。但是，遞歸本質上也是壓棧，只不過是程序壓棧，還不如這個效率高

⑹ 先序便利二叉樹非遞歸演算法如何理解

遞歸方式：先訪問根，再訪問左子樹（遞歸），再訪問右子樹（遞歸）

非遞歸：
當前節點=ROOT;
循環（當前節點不為空）
訪問當前節點。--先根，而且處理完後不在需要
如果有右子樹，push (右子樹）-- 表明在左子樹全部處理完後再處理
如果有左子樹，當前節點為左子樹，continue - 表明優先處理左子樹
如果沒有子樹，當前節點=pop()，continue - 表明一顆子樹已經處理完了，需要從堆棧裡面把以前記得需要處理的再拿出來。

總的來說，非遞歸演算法是利用堆棧，將不是馬上要處理的東西放到堆棧裡面，當需要處理的東西不能直接索引的時候。從堆棧中一個再挖出來處理。

⑺ 二叉樹先序非遞歸遍歷C語言演算法

#include "stdio.h"
#include "stdlib.h"
#define STACK_INIT_SIZE 10 //棧的初始長度
#define STACKINCREMENT 5 //棧的追加長度

typedef struct bitree{
char data;
struct bitree *lchild,*rchild;
}bitree; //二叉樹結點定義

typedef struct {
bitree **base;
bitree **top;
int stacksize;
}sqstack; // 鏈棧結點定義top棧頂 base棧底 且棧元素是指向二叉樹結點的二級指針
//建立一個空棧
int initstack(sqstack *s)
{s->base=(bitree *)malloc(STACK_INIT_SIZE*sizeof(bitree)); //棧底指向開辟空間
if(!s->base) exit(1); //拋出異常
s->top=s->base; //棧頂=棧尾 表示棧空
s->stacksize=STACK_INIT_SIZE; //棧長度為開辟空間大小
return 1;
}
//進棧
int push(sqstack *s,bitree *e)
{if(s->top-s->base>=s->stacksize) //如果棧滿 追加開辟空間
{s->base=(bitree *)realloc (s->base,(s->stacksize+STACKINCREMENT)* sizeof(bitree));
if(!s->base) exit(1); //拋出異常
s->top=s->base+s->stacksize; //感覺這一句沒用
s->stacksize+=STACKINCREMENT;}
*(s->top)=e;s->top++; //進棧 棧頂後移
return 1;
}
//出棧
int pop(sqstack *s,bitree **e)
{if(s->top==s->base) return 0; //棧空 返回0
--s->top;*e=*(s->top); //棧頂前移 取出棧頂元素給e
return 1;}
//取棧頂
int gettop(sqstack *s,bitree **e) //去棧頂元素 注意top指向的是棧頂的後一個
{if(s->top==s->base) return 0; //所以 s->top-1
*e=*(s->top-1);
return 1;
}
/*------------------------非遞歸-----先序建立二叉樹----------------------------------*/
bitree *createprebitree()
{char ch;bitree *ht,*p,*q;
sqstack *s;
s=malloc(sizeof(bitree)); //加上這一句為s 初始化開辟空間
ch=getchar();
if(ch!='#'&&ch!='\n') /* 輸入二叉樹先序順序 是以完全二叉樹的先序順序
不是完全二叉樹的把沒有的結點以#表示 */
{ht=(bitree *)malloc(sizeof(bitree));
ht->data=ch;
ht->lchild=ht->rchild=NULL;
p=ht;
initstack(s);
push(s,ht); //根節點進棧
while((ch=getchar())!='\n') // 算
{if(ch!='#') {q=(bitree *)malloc(sizeof(bitree)); // 法
q->data=ch; //
if(p==*(s->top-1)) p->lchild=q; // 核
else p->rchild=q; //
push(s,q);p=q; // 心
} //
else {if(p==*(s->top-1)) p->lchild=NULL; // 的
else p->rchild=NULL; //
pop(s,&p);} // 步
//
} // 驟
return ht;
}
else return NULL;
}
/*--------------------------遞歸---------先序建立二叉樹-------------------------------*/
void CreateBiTree(bitree **T) {
//按先序次序輸入二叉樹中的結點的值（一個字元），空格字元表示空樹，
//構造二叉鏈表表示二叉樹
char ch;
scanf("%c",&ch);
if(ch=='#') *T=NULL;
else{
*T=(bitree * )malloc(sizeof(bitree));
if(!*T) exit(1);
(*T)->data=ch; //生成根結點
CreateBiTree(&(*T)->lchild); //構造左子樹
CreateBiTree(&(*T)->rchild); //構造右子樹
}
}
/*--------------------------非遞歸-------中序建立二叉樹-------------------------------*/
/*--------------------------遞歸---------中序建立二叉樹-------------------------------*/
/*--------------------------非遞歸-------後序建立二叉樹-------------------------------*/
/*--------------------------遞歸---------後序建立二叉樹-------------------------------*/

/*-----------------------非遞歸------先序輸出二叉樹------------------------------*/
void preordertraverse(bitree *h)
{sqstack m;
initstack(&m);
while(h||m.base!=m.top)
{if(h) {push(&m,h);printf("%c",h->data);h=h->lchild;}
else{pop(&m,&h);
h=h->rchild;}
}
}
/*------------------------非遞歸-----中序輸出二叉樹----------------------------*/
void inordertraverse(bitree *h)
{sqstack m;
initstack(&m);
while(h||m.base!=m.top)
{if(h) {push(&m,h);h=h->lchild;}
else {
pop(&m,&h);
printf("%c",h->data);
h=h->rchild;
}
}
}
/*---------------------非遞歸----後序遍歷二叉樹----------------------------------*/
void postordertraverse(bitree *h)
{
sqstack m;
initstack(&m);
while(h||m.base!=m.top)
{if(h) {
push(&m,h);
h=h->lchild;}
else {
bitree *r; //使用r結點表示訪問了右子樹 代替標志域
gettop(&m,&h);
if(h->rchild&&h->rchild!=r)
{h=h->rchild;
push(&m,h);
h=h->lchild;}
else{pop(&m,&h);
printf("%c",h->data);
r=h;h=NULL;}
}
}
}
//層次遍歷二叉樹 用隊列 哈哈以後做
/*-------------------------------主過程-------------------------------*/
int main()
{bitree *ht;
printf("先序非遞歸建立一個二叉樹:");
if((ht=createprebitree())!=NULL) //非遞歸建立
//CreateBiTree(&ht);
//if(ht!=NULL) //遞歸建立
{
printf("先序遍歷輸出二叉樹:");
preordertraverse(ht);
putchar('\n');
printf("中序遍歷輸出二叉樹:");
inordertraverse(ht);
putchar('\n');
printf("後序遍歷輸出二叉樹:");
postordertraverse(ht);
putchar('\n');
}
else printf("空二叉樹\n");
}

⑻ 二叉樹的遍歷演算法

這里有二叉樹先序、中序、後序三種遍歷的非遞歸演算法，此三個演算法可視為標准演算法。
1.先序遍歷非遞歸演算法
#define
maxsize
100
typedef
struct
{

Bitree
Elem[maxsize];

int
top;
}SqStack;
void
PreOrderUnrec(Bitree
t)
{
SqStack
s;
StackInit(s);
p=t;
while
(p!=null
||
!StackEmpty(s))
{
while
(p!=null)
//遍歷左子樹
{
visite(p->data);
push(s,p);
p=p->lchild;
}//endwhile
if
(!StackEmpty(s))
//通過下一次循環中的內嵌while實現右子樹遍歷
{
p=pop(s);
p=p->rchild;
}//endif
}//endwhile
}//PreOrderUnrec
2.中序遍歷非遞歸演算法
#define
maxsize
100
typedef
struct
{
Bitree
Elem[maxsize];
int
top;
}SqStack;
void
InOrderUnrec(Bitree
t)
{
SqStack
s;
StackInit(s);
p=t;
while
(p!=null
||
!StackEmpty(s))
{
while
(p!=null)
//遍歷左子樹
{
push(s,p);
p=p->lchild;
}//endwhile
if
(!StackEmpty(s))
{
p=pop(s);
visite(p->data);
//訪問根結點
p=p->rchild;
//通過下一次循環實現右子樹遍歷
}//endif
}//endwhile
}//InOrderUnrec
3.後序遍歷非遞歸演算法
#define
maxsize
100
typedef
enum{L,R}
tagtype;
typedef
struct
{
Bitree
ptr;
tagtype
tag;
}stacknode;
typedef
struct
{
stacknode
Elem[maxsize];
int
top;
}SqStack;
void
PostOrderUnrec(Bitree
t)
{
SqStack
s;
stacknode
x;
StackInit(s);
p=t;
do
{
while
(p!=null)
//遍歷左子樹
{
x.ptr
=
p;
x.tag
=
L;
//標記為左子樹
push(s,x);
p=p->lchild;
}
while
(!StackEmpty(s)
&&
s.Elem[s.top].tag==R)
{
x
=
pop(s);
p
=
x.ptr;
visite(p->data);
//tag為R，表示右子樹訪問完畢，故訪問根結點
}
if
(!StackEmpty(s))
{
s.Elem[s.top].tag
=R;
//遍歷右子樹
p=s.Elem[s.top].ptr->rchild;
}
}while
(!StackEmpty(s));
}//PostOrderUnrec

⑼ 二叉樹的先序遍歷C++非遞歸演算法

template<class ElemType>//聲明類模板 void NonRecurPreOrderHelp(BinTreeNode<ElemType>*r, void(*Visit)(ElemType&))//傳遞一個模板類型二叉樹節點的指針作為參數 { BinTreeNode<ElemType>*cur=r;//接收傳遞進來的節點指針（作為遍歷起始點） Linkstack<BinTreeNode<ElemType>*>s;//鏈表棧，用於控制將遍歷的數據出入棧 while(cur!=NULL) { (*Vitis)(cur->data);//首先將當前節點處的數據轉換為*Vitis類型 s.Push(cur);將當前節點壓入棧中 if(cur->leftChild!=NULL)//若當前節點的左邊的子節點不為空 { cur=cur->leftChild;//將當前遍歷節點指向其左子節點 } else if(!s.Empty())//若當前節點的左邊的子節點為空，但棧不為空（即棧內還有元素） { while(!s.Empty())//當但棧不為空時 {s.Pop(cur);//將棧內元素出棧 cur=cur->rightChild;//將當前遍歷節點設為其右子節點 if(cur!=NULL)break;//若當前的節點不為空，直接退出循環 } } else//若當前節點的左邊的子節點為空，但棧為空（即棧內無元素） {cur=NULL;}//將當前遍歷節點設為空 }

麻煩採納，謝謝!

⑽ 怎樣實現二叉樹的前序遍歷的非遞歸演算法

在前面一文，說過二叉樹的遞歸遍歷演算法（二叉樹先根（先序）遍歷的改進），此文主要講二叉樹的非遞歸演算法，採用棧結構
總結先根遍歷得到的非遞歸演算法思想如下：
1）入棧，主要是先頭結點入棧，然後visit此結點
2）while，循環遍歷當前結點，直至左孩子沒有結點
3）if結點的右孩子為真，轉入1）繼續遍歷，否則退出當前結點轉入父母結點遍歷轉入1）
先看符合此思想的演算法：
[cpp]
view
plain

print?
int
(const
BiTree
&T,
int
(*VisitNode)(TElemType
data))
{
if
(T
==
NULL)
{
return
-1;
}
BiTNode
*pBiNode
=
T;
SqStack
S;
InitStack(&S);
Push(&S,
(SElemType)T);
while
(!IsStackEmpty(S))
{
while
(pBiNode)
{
VisitNode(pBiNode->data);
if
(pBiNode
!=
T)
{
Push(&S,
(SElemType)pBiNode);
}
pBiNode
=
pBiNode->lchild;
}
if(pBiNode
==
NULL)
{
Pop(&S,
(SElemType*)&pBiNode);
}
if
(
pBiNode->rchild
==
NULL)
{
Pop(&S,
(SElemType*)&pBiNode);
//如果此時棧已空，就有問題
}
pBiNode
=
pBiNode->rchild;
}
return
0;
}