c二叉樹遍歷演算法

『壹』 二叉樹先序遍歷演算法流程圖怎麼畫，學的是數據結構c語言。

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

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

『貳』 什麼叫遍歷演算法(最好有例子)

遍歷演算法：所謂遍歷(Traversal)，是指沿著某條搜索路線，依次對樹中每個結點均做一次且僅做一次訪問。訪問結點所做的操作依賴於具體的應用問題。遍歷是二叉樹上最重要的運算之一，是二叉樹上進行其它運算之基礎。當然遍歷的概念也適合於多元素集合的情況，如數組。

遍歷演算法概念延伸：

圖遍歷：圖遍歷又稱圖的遍歷，屬於數據結構中的內容。指的是從圖中的任一頂點出發，對圖中的所有頂點訪問一次且只訪問一次。圖的遍歷操作和樹的遍歷操作功能相似。圖的遍歷是圖的一種基本操作，圖的許多其它操作都是建立在遍歷操作的基礎之上。

舉例：

遍歷二叉樹搜索路線：

從二叉樹的遞歸定義可知，一棵非空的二叉樹由根結點及左、右子樹這三個基本部分組成。因此，在任一給定結點上，可以按某種次序執行三個操作：⑴訪問結點本身（N），⑵遍歷該結點的左子樹（L），⑶遍歷該結點的右子樹（R）。以上三種操作有六種執行次序：NLR、LNR、LRN、NRL、RNL、RLN。前三種次序與後三種次序對稱。

遍歷二叉樹的執行蹤跡三種遞歸遍歷演算法的搜索路線相同（如下圖虛線所示）。具體線路為：從根結點出發，逆時針沿著二叉樹外緣移動，對每個結點均途徑三次，最後回到根結點。

『叄』 c語言 關於二叉樹的創建和遍歷(中序遍歷)

這個還是我學《數據結構》時做的有關二叉樹的練習呢，本來是全的，包括樹的初始化，建立，遍歷（中序、前序、後序和層次），還有輸出，復制，刪除節點，求深度，樹的刪除等等，看你只問了有關創建和中序遍歷的，所以選了一部分給你，供你參考吧！
#include <stdio.h>
#include <malloc.h>
#define MaxSize 10
#define Number 30
struct BiTNode{//定義數據結構
char data;
BiTNode *lchild,*rchild;
};
void InitBtree(BiTNode * &BT){//初始化二叉樹
BT=NULL;
}
void CreateBiTree(BiTNode *&BT,char *str){//建立二叉樹
BiTNode *s[MaxSize];//這里定義了一個數組用作堆棧方便檢查輸入和操作
int top=-1;
BT=NULL;
BiTNode *p=NULL;
int k, j=0;
char ch;
ch=str[j];
while(ch!='\0'){
switch(ch){
case '(':
top++;
s[top]=p;
k=1;
break;
case ')':
top--;
break;
case ',':
k=2;
break;
default:
p=(struct BiTNode *) malloc(sizeof(struct BiTNode));
p->data=ch;
p->lchild=p->rchild=NULL;
if(BT==NULL)
BT=p;
else{
if(k==1)
s[top]->lchild=p;
else
s[top]->rchild=p;
}
}
j++;
ch=str[j];
}
}
void inorder(BiTNode *BT){//中序遍歷二叉樹——遞歸形式
if(BT!=NULL){
inorder(BT->lchild );
printf("%c ",BT->data);
inorder(BT->rchild );
}
}

void main(){
BiTNode *BT;
printf("以廣義表形式表示輸入的二叉數 （如A(B(C,D),E(,F))的形式）\n\n");
char string[Number]="A(B(,C),D(E(F),G(,H)))";
//如果想要自己輸入，可以將下邊的注釋去掉，然後自己按照廣義表形式輸入，
//（如上例的形式）此處為了方便查看，用了默認的數值
//這里之所以用此種形式（廣義表形式輸入）是為了保證輸入的數組成的二叉樹完全符合你所定義的樹的形狀
/*char string[Number],ch;
int i=0;
ch=getchar();
while(ch!='\n' && i<Number){
string[i]=ch;
i++;
ch=getchar();
}
string[i]='\0';
*/

InitBtree(BT);//初始化二叉樹
CreateBiTree(BT,string);//創建二叉樹
printf("\n中序遍歷二叉樹順序為： ");
inorder(BT);//中序遍歷二叉樹
printf("\n");
}
程序不復雜，所以只是加了必要和最簡單的注釋，相信你看看應該完全可以理解的，祝你進步！

『肆』 二叉樹的建立與遍歷(C語言)

樓主你好~~~「ф」字元的源代碼我忘記了，我這里有一個自己寫過的遍歷演算法
#include<iostream.h>
typedef struct btnode
{
char data;
struct btnode *Lchild,*Rchild;
}*bitreptr;

void Create(bitreptr &p)
{
char n;
p=new btnode;
cin>>n;
if(n!='#')
{
p->data=n;
Create(p->Lchild);
Create(p->Rchild);

}
else
p=NULL;

}

void preorder(bitreptr &p)
{
if(p)
{
cout<<p->data<<" ";
preorder(p->Lchild);
preorder(p->Rchild);
}
}

void midorder(bitreptr &p)
{
if(p)
{
midorder(p->Lchild);
cout<<p->data<<" ";
midorder(p->Rchild);
}
}

void postorder(bitreptr &p)
{
if(p)
{
postorder(p->Lchild);
postorder(p->Rchild);
cout<<p->data<<" ";
}
}

void change(bitreptr &p)
{
bitreptr t,q;
if(p)
{
t=p->Lchild;
q=p->Rchild;
p->Lchild=q;
p->Rchild=t;
change(p->Lchild);
change(p->Rchild);
}
}

void main()
{
char i;
cout<<"請選擇所需功能（'A'輸出該二叉樹序列，'B'輸出交換後二叉樹序列)"<<endl;
cin>>i;
bitreptr p;
cout<<"輸入數據：";
Create(p);
switch(i)
{
case 'A':
{
cout<<"前序:";
preorder(p);
cout<<endl;
cout<<"中序:";
midorder(p);
cout<<endl;
cout<<"後序:";
postorder(p);
cout<<endl;
}break;
case 'B':
{
change(p);
cout<<"交換二叉樹前序:";
preorder(p);
cout<<endl;
cout<<"交換二叉樹中序:";
midorder(p);
cout<<endl;
cout<<"交換二叉樹後序:";
postorder(p);
cout<<endl;
}break;
}

}

這個演算法輸入時要以「#」代表空節點，及將[測試數據] 「ABCффDEфGффFффф」改成「ABC##DE#G##F###」即可。另外我的演算法包括了二叉樹左右子樹交換的代碼「change(bitreptr &p)」，只要樓主稍作修改就可以得到你想要的完美結果~

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

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

從二叉樹的遞歸定義可知，一棵非空的二叉樹由根結點及左、右子樹這三個基本部分組成。因此，在任一給定結點上，可以按某種次序執行三個操作：
⑴訪問結點本身（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);}}