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

二叉樹的遍歷演算法

發布時間: 2022-02-06 22:35:10

Ⅰ 二叉樹遍歷的演算法

void PreOrder(BiTree t) { /* 二叉樹的先序遍歷演算法 */
if(t!=NULL) {
putchar (t->data);
PreOrder(t->lchild);
PreOrder(t->rchild);
}
}

void InOrder(BiTree t) { /* 二叉樹的先中序遍歷演算法 */
if(t != NULL) {
InOrder(t->lchild);
putchar(t->data);
InOrder(t->rchild);
}
}

void PostOrder(BiTree t) { /* 二叉樹的後序遍歷演算法 */
if(t != NULL) {
PostOrder(t->lchild);
PostOrder(t->rchild);
putchar(t->data);
}
}

Ⅱ 求二叉樹遍歷演算法C語言實現的

Status
PreOrderTraverse
(
BiTree
T,
Status
(
*Visit
)
(
TElemType
e
)
)
{
//
採用二叉鏈表存儲結構,Visit
是對數據元素操作的應用函數,先序遍歷二叉樹
T
的遞歸演算法。
if
(
T
)
{
//

T
不為空
if
(
Visit
(
T->data
)
)
//
調用函數
Visit
if
(
PreOrderTraverse
(
T->lchild,
Visit
)
)
//
遞歸調用左子樹
if
(
PreOrderTraverse
(
T->rchild,
Visit
)
)
return
OK;
//
遞歸調用右子樹
return
ERROR;
}
else
return
OK;
}
//
PreOrderTraverse

Ⅲ 二叉樹的遍歷演算法

怎麼又來問了,不是回答過你了嗎?很簡單,就是一個遞歸過程。在函數中以先序遍歷的第一個結點在中序遍歷中為界把中序遍歷分為兩半,再分別把左一半和右一半作為這個結點的左子樹和右子樹進行遞歸。完成遞歸之後再列印該結點即可。結束遞歸的條件是左子樹或右子樹沒有結點。下面是簡單的程序示意,可以用任意語言實現。

不過你給出的這個前序遍歷和中序遍歷卻是有問題的,如果改成ABDEGCFH和DBGEAFCH的話其後序遍歷就是:D G E B F H C A

import sys

rflist = list(sys.argv[1])
rmlist = list(sys.argv[2])

def printTreeRootLast(r, rflist, rmlist):
r[0] = rflist.pop(0)

rmLeftNodes = rmlist[:rmlist.index(r[0])]
if len(rmLeftNodes) == 0:
r[1] = None
else:
r[1] = [None, None, None]
printTreeRootLast(r[1], rflist, rmLeftNodes)

rmRightNodes = rmlist[rmlist.index(r[0])+1:]
if len(rmRightNodes) == 0:
r[2] = None
else:
r[2] = [None, None, None]
printTreeRootLast(r[2], rflist, rmRightNodes)

print r[0],

root = [None, None, None]
printTreeRootLast(root, rflist, rmlist)

Ⅳ 什麼是二叉樹數的遍歷

二叉樹遍歷(Traversal)是指沿著某條搜索路線,依次對樹中每個結點均做一次且僅做一次訪問。訪問結點所做的操作依賴於具體的應用問題。遍歷是二叉樹上最重要的運算之一,是二叉樹上進行其它運算之基礎。

遍歷方案
從二叉樹的遞歸定義可知,一棵非空的二叉樹由根結點及左、右子樹這三個基本部分組成。因此,在任一給定結點上,可以按某種次序執行三個操作:訪問結點本身(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.後(根)序遍歷得遞歸演算法定義:
若二叉樹非空,則依次執行如下操作:
⑴遍歷左子樹;
⑵遍歷右子樹;
⑶訪問根結點。

Ⅳ 遍歷二叉樹遞歸演算法

「這個函數的參數visit應該是另一個函數的地址是把,但我怎麼感覺不管怎麼遞歸它只是在訪問根的時候被調用過一次」
首先,你是對的,visit確實是一個指向函數的指針;
然後,它只是在訪問根的時候被調用過一次,這種說法就很片面了。
我覺得應該這么說:(*visit)()函數在BTreePreOrger()函數的一次執行過程中只被調用過一次,但是BTreePreOrger()函數執行了很多次,因此(*visit)()就被調用了n次(假設該樹有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)」,只要樓主稍作修改就可以得到你想要的完美結果~

Ⅶ 關於二叉樹的三種遍歷

先序
preOrder(BiTree T)
{
if(T)
{
visitor(T);
preOrder(T->lchild);
preOrder(T->rchild);
}
}

中序

inOrder(BiTree T)
{
if(T)
{
preOrder(T->lchild);
visitor(T);
preOrder(T->rchild);
}
}

後序
preOrder(BiTree T)
{
if(T)
{

preOrder(T->lchild);
preOrder(T->rchild);
visitor(T);
}
}

數據機構丟下太久了,基本不會了,只記得三種遍歷了,估計也幫不了你咯... 還有,最好翻成中文發出來,因為有的人即便會,看到英文的怕麻煩也不會回答了....

Ⅷ c++二叉樹的幾種遍歷演算法

遍歷二叉樹的所有結點且僅訪問一次。按照根節點位置的不同分為前序遍歷,中序遍歷,後序遍歷(除此之外還有層次遍歷,但不常用,此處不做解釋)。

1.前序遍歷:根節點->左子樹->右子樹(根節點在前面)。

2.中序遍歷:左子樹->根節點->右子樹(根節點在中間)。

3.後序遍歷:左子樹->右子樹->根節點(根節點在後邊)。

例如:求下面樹的三種遍歷:

前序遍歷:abdefgc;

中序遍歷:debgfac;

後序遍歷:edgfbca。

Ⅸ 二叉樹遍歷

把列印語句放到第1句,什麼是2叉樹,我記得我在研究a*巡路演算法時研究的最清楚了,2叉並不是表面上理解的那樣,平均級別的執行,他的順序是在父節點,爺爺節點,子節點,孫子節點之間徘徊的,按你的想法是不是要父節點先執行完,再執行子所有的子節點,再執行所有的孫子節點啊?

Ⅹ 二叉樹遍歷的演算法實現

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

熱點內容
dns伺服器江川區ip地址 發布:2024-03-29 18:47:53 瀏覽:327
sql統計百分比 發布:2024-03-29 18:47:14 瀏覽:691
javatoolsfor 發布:2024-03-29 18:17:55 瀏覽:900
linuxi2c驅動 發布:2024-03-29 18:09:56 瀏覽:672
junit源碼下載 發布:2024-03-29 18:00:10 瀏覽:526
本田雅閣壓縮機不工作 發布:2024-03-29 17:59:13 瀏覽:601
溯源碼可以偽造嗎 發布:2024-03-29 17:54:45 瀏覽:57
北京編程傳 發布:2024-03-29 17:54:44 瀏覽:436
編程畫曲線 發布:2024-03-29 17:48:59 瀏覽:60
簡單存儲服務s3 發布:2024-03-29 17:48:46 瀏覽:337