二叉樹的先序遍歷演算法

『壹』 二叉樹前序遍歷法舉例!急急急！！！

二叉樹的三種金典遍歷法

1.前序遍歷法：

前序遍歷（DLR）

前序遍歷（DLR）

前序遍歷首先訪問根結點然後遍歷左子樹，最後遍歷右子樹。在遍歷左、右子樹時，仍然先訪問根結點，然後遍歷左子樹，最後遍歷右子樹。

若二叉樹為空則結束返回，否則：

（1）訪問根結點

（2）前序遍歷左子樹

（3）前序遍歷右子樹

注意的是：遍歷左右子樹時仍然採用前序遍歷方法。

如上圖所示二叉樹

前序遍歷，也叫先根遍歷，遍歷的順序是，根，左子樹，右子樹

遍歷結果：ABDECF

中序遍歷，也叫中根遍歷，順序是左子樹，根，右子樹

遍歷結果：DBEAFC

後序遍歷，也叫後根遍歷，遍歷順序，左子樹，右子樹，根

遍歷結果：DEBFCA

2.中序遍歷法：

中序遍歷

中序遍歷（LDR）

中序遍歷首先遍歷左子樹，然後訪問根結點，最後遍歷右子樹。在遍歷左、右子樹時，仍然先遍歷左子樹，再訪問根結點，最後遍歷右子樹。即：

若二叉樹為空則結束返回，否則：

（1）中序遍歷左子樹

（2）訪問根結點

（3）中序遍歷右子樹。

注意的是：遍歷左右子樹時仍然採用中序遍歷方法。

3.後序遍歷法：

後序遍歷

簡介

後序遍歷是二叉樹遍歷的一種。後序遍歷指在訪問根結點、遍歷左子樹與遍歷右子樹三者中，首先遍歷左子樹，然後遍歷右子樹，最後遍歷訪問根結點，在遍歷左、右子樹時，仍然先遍歷左子樹，然後遍歷右子樹，最後遍歷根結點。後序遍歷有遞歸演算法和非遞歸演算法兩種。

遞歸演算法

演算法描述：

（1）若二叉樹為空，結束

（2）後序遍歷左子樹

（3）後序遍歷右子樹

（4）訪問根結點

偽代碼

PROCEDUREPOSTRAV(BT)

IFBT<>0THEN

{

POSTRAV(L(BT))

POSTRAV(R(BT))

OUTPUTV(BT)

}

RETURN

c語言描述

structbtnode

{

intd;

structbtnode*lchild;

structbtnode*rchild;

};

voidpostrav(structbtnode*bt)

{

if(bt!=NULL)

{

postrav(bt->lchild);

postrav(bt->rchild);

printf("%d",bt->d);

}

}

非遞歸演算法

演算法1（c語言描述）：

voidpostrav1(structbtnode*bt)

{

structbtnode*p;

struct

{

structbtnode*pt;

inttag;

}st[MaxSize];

}

inttop=-1;

top++;

st[top].pt=bt;

st[top].tag=1;

while(top>-1)/*棧不為空*/

{

if(st[top].tag==1)/*不能直接訪問的情況*/

{

p=st[top].pt;

top--;

if(p!=NULL)

{

top++;/*根結點*/

st[top].pt=p;

st[top].tag=0;

top++;/*右孩子結點*/

st[top].pt=p->p->rchild;

st[top].tag=1;

top++;/*左孩子結點*/

st[top].pt=p->lchild;

st[top].tag=1;

}

}

if(st[top].tag==0)/*直接訪問的情況*/

{

printf("%d",st[top].pt->d);

top--;

}

}

}

演算法2：

voidpostrav2(structbtnode*bt)

{

structbtnode*st[MaxSize],*p;

intflag,top=-1;

if(bt!=NULL)

{

do

{

while(bt!=NULL)

{

top++;

st[top]=bt;

bt=bt->lchild;

}

p=NULL;

flag=1;

while(top!=-1&&flag)

{

bt=st[top];

if(bt->rchild==p)

{

printf("%d",bt->d);

top--;

p=bt;

}

else

{

bt=bt->rchild;

flag=0;

}

}

}while(top!=-1)

printf(" ");

}

}

老曹回答必屬佳作記得給分謝謝合作！

『貳』 二叉樹先序遍歷演算法

#include<stdio.h>
struct node//定義節點
{
int num;
node *left;
node *right;
};
void fscan(node *root)//先序遍歷函數，root為根節點
{
if(root==NULL);
else
{
fscan(root->left);
printf("%d\n",root->num);
fscan(root->right);
}
}
void main()
{
//1，生成一個二叉樹，並得到它的根節點
//2,調用fscan遍歷二叉樹
}

『叄』 二叉鏈表存儲二叉樹的先序遍歷演算法

二叉鏈表存儲二叉樹的先序遍歷演算法，通常採用遞歸的演算法實現。首先訪問二叉樹的根節點，然後遞歸遍歷它的左子樹，最後，遞歸遍歷他的右子樹。

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

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

『伍』 二叉樹遍歷的演算法實現

從二叉樹的遞歸定義可知，一棵非空的二叉樹由根結點及左、右子樹這三個基本部分組成。因此，在任一給定結點上，可以按某種次序執行三個操作：
⑴訪問結點本身（N），
⑵遍歷該結點的左子樹（L），
⑶遍歷該結點的右子樹（R）。
以上三種操作有六種執行次序：
NLR、LNR、LRN、NRL、RNL、RLN。
注意：
前三種次序與後三種次序對稱，故只討論先左後右的前三種次序。 根據訪問結點操作發生位置命名：
① NLR：前序遍歷(PreorderTraversal亦稱（先序遍歷））
——訪問根結點的操作發生在遍歷其左右子樹之前。
② LNR：中序遍歷(InorderTraversal)
——訪問根結點的操作發生在遍歷其左右子樹之中（間）。
③ LRN：後序遍歷(PostorderTraversal)
——訪問根結點的操作發生在遍歷其左右子樹之後。
注意：
由於被訪問的結點必是某子樹的根，所以N(Node）、L(Left subtree）和R(Right subtree）又可解釋為根、根的左子樹和根的右子樹。NLR、LNR和LRN分別又稱為先根遍歷、中根遍歷和後根遍歷。 1．先（根）序遍歷的遞歸演算法定義：
若二叉樹非空，則依次執行如下操作：
⑴ 訪問根結點；
⑵ 遍歷左子樹；
⑶ 遍歷右子樹。
2．中（根）序遍歷的遞歸演算法定義：
若二叉樹非空，則依次執行如下操作：
⑴遍歷左子樹；
⑵訪問根結點；
⑶遍歷右子樹。
3．後（根）序遍歷得遞歸演算法定義：
若二叉樹非空，則依次執行如下操作：
⑴遍歷左子樹；
⑵遍歷右子樹；
⑶訪問根結點。 用二叉鏈表做為存儲結構，中序遍歷演算法可描述為：
void InOrder(BinTree T)
{ //演算法里①~⑥是為了說明執行過程加入的標號
① if(T) { // 如果二叉樹非空
② InOrder(T->lchild）；
③ printf(%c，T->data）； // 訪問結點
④ InOrder(T->rchild);
⑤ }
⑥ } // InOrder 計算中序遍歷擁有比較簡單直觀的投影法，如圖
⑴在搜索路線中，若訪問結點均是第一次經過結點時進行的，則是前序遍歷；若訪問結點均是在第二次（或第三次）經過結點時進行的，則是中序遍歷（或後序遍歷）。只要將搜索路線上所有在第一次、第二次和第三次經過的結點分別列表，即可分別得到該二叉樹的前序序列、中序序列和後序序列。
⑵上述三種序列都是線性序列，有且僅有一個開始結點和一個終端結點，其餘結點都有且僅有一個前驅結點和一個後繼結點。為了區別於樹形結構中前驅（即雙親）結點和後繼（即孩子）結點的概念，對上述三種線性序列，要在某結點的前驅和後繼之前冠以其遍歷次序名稱。
【例】上圖所示的二叉樹中結點C，其前序前驅結點是D，前序後繼結點是E；中序前驅結點是E，中序後繼結點是F；後序前驅結點是F，後序後繼結點是A。但是就該樹的邏輯結構而言，C的前驅結點是A，後繼結點是E和F。
二叉鏈表基本思想
基於先序遍歷的構造，即以二叉樹的先序序列為輸入構造。
注意：
先序序列中必須加入虛結點以示空指針的位置。
【例】
建立上圖所示二叉樹，其輸入的先序序列是：ABD∮∮∮CE∮∮F∮∮。
構造演算法
假設虛結點輸入時以空格字元表示，相應的構造演算法為：
void CreateBinTree (BinTree **T){ //構造二叉鏈表。T是指向根指針的指針，故修改*T就修改了實參（根指針）本身 char ch； if((ch=getchar())=='') *T=NULL； //讀入空格，將相應指針置空 else{ //讀人非空格 *T=(BinTNode *)malloc(sizeof(BinTNode））； //生成結點 （*T)->data=ch； CreateBinTree(&(*T)->lchild）； //構造左子樹 CreateBinTree(&(*T)->rchild）； //構造右子樹 }}
注意：
調用該演算法時，應將待建立的二叉鏈表的根指針的地址作為實參。
示例
設root是一根指針（即它的類型是BinTree），則調用CreateBinTree(&root）後root就指向了已構造好的二叉鏈表的根結點。
二叉樹建立過程見
下面是關於二叉樹的遍歷、查找、刪除、更新數據的代碼（遞歸演算法）： #include<iostream>#include<cstdio>#include<cmath>#include<iomanip>#include<cstdlib>#include<ctime>#include<algorithm>#include<cstring>#include<string>#include<vector>#include<list>#include<stack>#include<queue>#include<map>#include<set>usingnamespacestd;typedefintT;classbst{structNode{Tdata;Node*L;Node*R;Node(constT&d,Node*lp=NULL,Node*rp=NULL):data(d),L(lp),R(rp){}};Node*root;intnum;public:bst():root(NULL),num(0){}voidclear(Node*t){if(t==NULL)return;clear(t->L);clear(t->R);deletet;}~bst(){clear(root);}voidclear(){clear(root);num=0;root=NULL;}boolempty(){returnroot==NULL;}intsize(){returnnum;}TgetRoot(){if(empty())throwemptytree;returnroot->data;}voidtravel(Node*tree){if(tree==NULL)return;travel(tree->L);cout<<tree->data<<'';travel(tree->R);}voidtravel(){travel(root);cout<<endl;}intheight(Node*tree){if(tree==NULL)return0;intlh=height(tree->L);intrh=height(tree->R);return1+(lh>rh?lh:rh);}intheight(){returnheight(root);}voidinsert(Node*&tree,constT&d){if(tree==NULL)tree=newNode(d);elseif(ddata)insert(tree->L,d);elseinsert(tree->R,d);}voidinsert(constT&d){insert(root,d);num++;}Node*&find(Node*&tree,constT&d){if(tree==NULL)returntree;if(tree->data==d)returntree;if(ddata)returnfind(tree->L,d);elsereturnfind(tree->R,d);}boolfind(constT&d){returnfind(root,d)!=NULL;}boolerase(constT&d){Node*&pt=find(root,d);if(pt==NULL)returnfalse;combine(pt->L,pt->R);Node*p=pt;pt=pt->R;deletep;num--;returntrue;}voidcombine(Node*lc,Node*&rc){if(lc==NULL)return;if(rc==NULL)rc=lc;elsecombine(lc,rc->L);}boolupdate(constT&od,constT&nd){Node*p=find(root,od);if(p==NULL)returnfalse;erase(od);insert(nd);returntrue;}};intmain(){bstb;cout<<inputsomeintegers:;for(;;){intn;cin>>n;b.insert(n);if(cin.peek()==' ')break;}for(;;){cout<<inputdatapair:;intod,nd;cin>>od>>nd;if(od==-1&&nd==-1）break;b.update(od,nd);}}

『陸』 怎麼先序遍歷二叉樹

要想先序遍歷二叉樹，採用遞歸的方法來解說是很方便的。
首先訪問根結點，然後先序遍歷根節點的左子樹，最後先序遍歷根結點的右子樹。
要注意的是，這里的先序遍歷左子樹和右子樹都是遞歸的概念，再次使用上面的遞歸演算法。

『柒』 二叉樹的遍歷演算法

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

在計算機軟體專業中，數據結構、以及 C 語言這兩門課程是非常重要的兩門課程。最為重要的是：如果將來想做計算機軟體開發工作的話，那麼對 C 語言中的指針編程、以及遞歸的概念是必須要熟練精通掌握的，因為它和數據結構課程中的鏈表、二叉樹等內容的關系實在是太緊密了。但是這個編程技能必須要依靠自己多上機實踐才能夠真正徹底掌握的。
首先要搞明白二叉樹的幾種遍歷方法：（1）、先序遍歷法：根左右；（2）、中序遍歷法：左根右；（3）、後序遍歷法：左右根。其中根：表示根節點；左：表示左子樹；右：表示右子樹。
至於談到如何畫先序遍歷的流程圖，可以這樣考慮：按照遞歸的演算法進行遍歷一棵二叉樹。

程序首先訪問根節點，如果根節點的值為空（NULL），則停止訪問；如果根節點的值非空，則遞歸訪問二叉樹的左子樹（left），然後是依然判斷二叉樹下面的左子樹下面的根節點是否為空（NULL），如果根節點的值為空（NULL），則返回上一層，再訪問二叉樹的右子樹（right）。依此類推。

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

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

『拾』 二叉樹的先序遍歷演算法

#include
struct
node//定義節點
{
int
num;
node
*left;
node
*right;
};
void
fscan(node
*root)//先序遍歷函數，root為根節點
{
if(root==null);
else
{
fscan(root->left);
printf("%d\n",root->num);
fscan(root->right);
}
}
void
main()
{
//1，生成一個二叉樹，並得到它的根節點
//2,調用fscan遍歷二叉樹
}