當前位置:首頁 » 操作系統 » 遍歷二叉樹非遞歸演算法

遍歷二叉樹非遞歸演算法

發布時間: 2022-09-27 22:54:35

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

遞歸方式:先訪問根,再訪問左子樹(遞歸),再訪問右子樹(遞歸)

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

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

B. 二叉樹的遍歷演算法

這里有二叉樹先序、中序、後序三種遍歷的非遞歸演算法,此三個演算法可視為標准演算法。
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. 二叉樹中序遍歷的非遞歸演算法

推薦這篇文章,把二叉樹的前序、中序和後續的遞歸和非遞歸演算法都講了。
http://www.cppblog.com/ngaut/archive/2006/01/01/2351.html

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

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存在的那個分支。接下來再取右子樹的左子樹
}
}
//其實,用遞歸也許你更能理解一些。但是,遞歸本質上也是壓棧,只不過是程序壓棧,還不如這個效率高

E. 二叉樹先序非遞歸遍歷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");
}

F. 二叉樹中序遍歷非遞歸演算法(c語言實現)

#include "stdio.h"
#include "stdlib.h"
#include "string.h"
#define null 0

struct node
{
char data;
struct node *lchild;
struct node *rchild;
};

//先序,中序 建樹
struct node *create(char *pre,char *ord,int n)
{
struct node * head;
int ordsit;

head=null;
if(n<=0)
{
return null;
}
else
{
head=(struct node *)malloc(sizeof(struct node));
head->data=*pre;
head->lchild=head->rchild=null;
ordsit=0;
while(ord[ordsit]!=*pre)
{
ordsit++;
}
head->lchild=create(pre+1,ord,ordsit);
head->rchild=create (pre+ordsit+1,ord+ordsit+1,n-ordsit-1);
return head;
}
}

//中序遞歸遍歷
void inorder(struct node *head)
{
if(!head)
return;
else
{
inorder(head->lchild );
printf("%c",head->data );
inorder(head->rchild );
}
}

//中序非遞歸遍歷

void inorder1(struct node *head)
{
struct node *p;
struct node *stack[20];
int top=0;

p=head;
while(p||top!=0)
{
while (p)
{
stack[top++]=p;
p=p->lchild ;
}
p=stack[--top];
printf("%c ",p->data );
p=p->rchild ;
}
}

//主函數
int main()
{
struct node * head;
char pre[30],ord[30];
int n;

gets(pre);
gets(ord);
n=strlen(pre);
head=create(pre,ord,n);
inorder(head);
printf("\n");
inorder1(head);
printf("\n");
}

//測試事例;
/*
-+a*b%cd/ef
a+b*c%d-e/f
*/

幾個月前自己編寫,原版
vc++ 6.0實驗通過

怎麼樣,老闆,第一次上網路知道,好激動
給點面子
給分!給分啊

G. C#的二叉樹中序遍歷非遞歸演算法求詳細解釋!

object e = null; //聲明一個變數存放地址
SqStack S = new SqStack(); //聲明一個棧,用來存放遍歷過程中非末級節點

TreeNode p = t; //聲明一個節點變數p 接收函數傳來的參數 t

while (p != null || !S.SqStackEmpty()) //從跟節點開始遍歷,只要 p!=null (當前該節點還有子節點) 或者 棧 S 沒用清空,循環執行下去。
{
if (p != null)
{
S.SqStackPush(p); 該節點有子節點,先把該節點保存入棧,(棧是後進先出,正好先遍歷完子節點才遍歷父節點的控製作用,棧的最底部存的是根節點,最後才彈出遍歷,遍歷完後,!S.SqStackEmpty() 就不成立了,while循環結束)
p = p.left; // 上一步p變數的節點壓入棧保存後,轉而獲取左邊子節點,繼續循環,如果這是p=null,也就是剛壓入棧的節點沒有子節點,開始執行 else 里的語句
}
else
{
S.SqStackPop(ref e); //彈出剛壓入棧的節點,存放到 e ref e 是指存放該節點的地址
p = (TreeNode)e; 類型強制轉化成 節點類型,因為 e 聲明的是
object類型。付值給p,
Console.Write(p.data + " "); //輸出p的數據。

p = p.right; //轉而讀取該節點右邊的樹,開始新的循環。
}

H. 二叉樹的非遞歸遍歷有什麼優點

  • 遞歸和非遞歸只是解決問題的方法的不同,本質還是一樣的。

  • 2. 遞歸演算法相對於非遞歸演算法來說效率通常都會更低

    2.1 遞歸演算法會有更多的資源需要壓棧和出棧操作(不僅僅是參數,還有函數地址等)

    2.2 由於編譯器對附加的一些棧保護機制會導致遞歸執行的更加低效

    3. 使用循環代替遞歸演算法,通常可以獲得更好的執行效率和空間效率,在二叉樹層次較深的情況下,採用非遞歸方式遍歷能夠有效的提升遍歷的性能。

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

在前面一文,說過二叉樹的遞歸遍歷演算法(二叉樹先根(先序)遍歷的改進),此文主要講二叉樹的非遞歸演算法,採用棧結構
總結先根遍歷得到的非遞歸演算法思想如下:
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;
}

J. 二叉樹後序遍歷(非遞歸)

一,大循環中的第一個循環,當前節點一直往左走一直走到頭,並且把走過的節點壓棧,這個循環遍歷完成後,棧裡面都是左邊走過但是右邊還沒有走過的節點

二,從最左邊那個沒有更左的那個節點,它位於棧頂,因為這時棧頂不是一個右節點,第二個循環跳過,然後把棧頂結點的右節點標記為r並以此作為根節點重復之前的操作

回溯:
因為一直往下層走,總會遇到既沒有左節點有沒有右節點的節點,就是葉子節點,就開始往回退 取他的右節點,取之前會把該節點標記為r,但是他沒有右節點,為null,就會跳過第一個循環,來到第二個,那麼這個葉子就從棧中pop掉,新的棧頂結點是那個葉子的父節點,如果沒有右節點,那他就成了葉子,更簡單,如果有右節點,那麼繼續二

一步一步推就是這樣子,需要考慮所有情況,會把問題想復雜,但是利用遞歸的思想就好想了
參考遞歸演算法
void preOrder2(BinTree *root)
{
preOrder(root->lchild);
preOrder(root->rchild);
}
第一個函數就是第一個小循環,只走左邊,然後把新得到的節點作為根節點,繼續調用第一個函數,得到左節點,然後再作為根節點,直到左節點為空;
第二個函數就是最後一個if,非遞歸演算法中是從棧頂取,就是左邊走過了的節點,相當於遞歸中,第一個函數執行完已經返回,然後取他的右節點作為根節點,繼續遞歸
以上回答你滿意么?

熱點內容
cookie購物車php 發布:2022-12-09 14:10:53 瀏覽:796
高質量c編程指南 發布:2022-12-09 14:10:50 瀏覽:455
java獲取當前項目路徑 發布:2022-12-09 14:10:49 瀏覽:512
緩存的數據如何同步更新 發布:2022-12-09 14:09:06 瀏覽:743
myeclipse反編譯插件下載 發布:2022-12-09 14:07:26 瀏覽:748
C語言A拷貝 發布:2022-12-09 14:06:38 瀏覽:819
dockerfile腳本 發布:2022-12-09 14:01:40 瀏覽:275
linux命令總結 發布:2022-12-09 14:01:33 瀏覽:584
一加存儲顆粒 發布:2022-12-09 14:00:50 瀏覽:97
vivo雲服務在哪個文件夾 發布:2022-12-09 13:59:55 瀏覽:254