遍歷樹演算法
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
Ⅱ 用遞歸的方式中序遍歷二叉樹演算法描述
voidtravser(Node*node)
{
if(node==NULL)
return;
travser(node->left);
cout<<node->data;
travser(node->right);
}
Ⅲ 二叉樹的層次遍歷演算法
二叉樹的層次遍歷演算法有如下三種方法：
給定一棵二叉樹，要求進行分層遍歷，每層的節點值單獨列印一行，下圖給出事例結構：
之後大家就可以自己畫圖了，下面給出程序代碼：
[cpp] view plain
void print_by_level_3(Tree T) {
vector<tree_node_t*> vec;
vec.push_back(T);
int cur = 0;
int end = 1;
while (cur < vec.size()) {
end = vec.size();
while (cur < end) {
cout << vec[cur]->data << " ";
if (vec[cur]->lchild)
vec.push_back(vec[cur]->lchild);
if (vec[cur]->rchild)
vec.push_back(vec[cur]->rchild);
cur++;
}
cout << endl;
}
}
最後給出完成代碼的測試用例：124##57##8##3#6##
[cpp] view plain
#include<iostream>
#include<vector>
#include<deque>
using namespace std;
typedef struct tree_node_s {
char data;
struct tree_node_s *lchild;
struct tree_node_s *rchild;
}tree_node_t, *Tree;
void create_tree(Tree *T) {
char c = getchar();
if (c == '#') {
*T = NULL;
} else {
*T = (tree_node_t*)malloc(sizeof(tree_node_t));
(*T)->data = c;
create_tree(&(*T)->lchild);
create_tree(&(*T)->rchild);
}
}
void print_tree(Tree T) {
if (T) {
cout << T->data << " ";
print_tree(T->lchild);
print_tree(T->rchild);
}
}
int print_at_level(Tree T, int level) {
if (!T || level < 0)
return 0;
if (0 == level) {
cout << T->data << " ";
return 1;
}
return print_at_level(T->lchild, level - 1) + print_at_level(T->rchild, level - 1);
}
void print_by_level_1(Tree T) {
int i = 0;
for (i = 0; ; i++) {
if (!print_at_level(T, i))
break;
}
cout << endl;
}
void print_by_level_2(Tree T) {
deque<tree_node_t*> q_first, q_second;
q_first.push_back(T);
while(!q_first.empty()) {
while (!q_first.empty()) {
tree_node_t *temp = q_first.front();
q_first.pop_front();
cout << temp->data << " ";
if (temp->lchild)
q_second.push_back(temp->lchild);
if (temp->rchild)
q_second.push_back(temp->rchild);
}
cout << endl;
q_first.swap(q_second);
}
}
void print_by_level_3(Tree T) {
vector<tree_node_t*> vec;
vec.push_back(T);
int cur = 0;
int end = 1;
while (cur < vec.size()) {
end = vec.size();
while (cur < end) {
cout << vec[cur]->data << " ";
if (vec[cur]->lchild)
vec.push_back(vec[cur]->lchild);
if (vec[cur]->rchild)
vec.push_back(vec[cur]->rchild);
cur++;
}
cout << endl;
}
}
int main(int argc, char *argv[]) {
Tree T = NULL;
create_tree(&T);
print_tree(T);
cout << endl;
print_by_level_3(T);
cin.get();
cin.get();
return 0;
}
Ⅳ 遍歷二叉樹遞歸演算法
「這個函數的參數visit應該是另一個函數的地址是把，但我怎麼感覺不管怎麼遞歸它只是在訪問根的時候被調用過一次」
首先，你是對的，visit確實是一個指向函數的指針；
然後，它只是在訪問根的時候被調用過一次，這種說法就很片面了。
我覺得應該這么說：(*visit)()函數在BTreePreOrger（）函數的一次執行過程中只被調用過一次，但是BTreePreOrger()函數執行了很多次，因此(*visit)()就被調用了n次（假設該樹有n個節點）
Ⅳ 深度優先遍歷樹的演算法怎麼編程
程序的頭已經有了只要一個深度優先遍歷的演算法的程序。程序開始如下： #include "stdafx.h" #include "iostream.h" typedf int adjmatrix; const int max value=32767; conts int maxlength=30; int visited[10]; adjmatrix ga[10][10]; void create(int n,int e){int i,j,k,w; for(i=0;i<n;i++) for(j=0;j<n;j++){if(i==j)ga[i][j]=0; else ga[i][j]=max value;}cout<<"請輸入"<<e<<"條邊的權值："<<endl; for(k=1;k<=e;k++){cout<<"第"<<k<<"條邊的起始頂點,結束頂點及權值,如1 2 8:"; cin>>i>>j>>w; ga[i][j]=w;}}void dfs(int i,int n) //深度優先遍歷演算法{//請完成函數的編程}void main(){int i,j,n,e; cout<<"請輸入頂點個數:";cin>>n;cout<<"請輸入邊數:";cin>>e;create(n,e); cout<<endl<<"深度優先遍歷表:"<<endl; for(i=0;i<n;i++)visited[i]=0; if(!visited[i])dfs(i,n);}只要在請完成函數的編程這部分把程序編完就可以了。
Ⅵ 求一個c語言遍歷二叉樹的演算法
#include <stdio.h>
#include <stdlib.h>
//1 根據二叉樹的性質5，結點按完全二叉樹來編號，則根據結點編號，
// 就可算出其雙親結點的編號，以及該結點是左孩子還是右孩子，
// 這樣一來，就可把該結點的指針賦予雙親結點的相應指針域。
// 怎樣找到雙親結點呢？，在輸入雙親結點的同時要把結點的指針
// 保存起來。也就是說，要設計一個指針數組，來保存每個結點指針。
// 這樣，當輸入下層結點時，才能找到它的雙親。
//2 回想單鏈表的建立過程，單鏈表建立過程中，只需把當前結點，
// 當成前驅結點,故只需設計一個指針變數即可。
typedef char ElementType;
typedef struct node //二叉樹鏈表結點
{
ElementType data;
struct node *lchild,*rchild;//左、右孩子指針
}BinNode,*BinTree; //結點和結點指針的標識符
BinNode * creat(void) //建二叉樹鏈表(返回根結點的指針)
{
int i,j;
ElementType x;
BinNode *q,*s[20];//結點指針、輔助數組(存放結點的指針,該結點有可能是雙親結點)
BinNode *t=NULL; //根結點指針(目前是空樹,生成樹後要返回根結點指針)
printf("\n 請輸入結點編號i和結點值x");
printf("\n 如：1A 2B 3C 4D 5E 7F 00(全為0，輸入結束)");
printf("\n 或：1A 2B 3C 4D 6F 7G 00(全為0，輸入結束)");
printf("\n 或：1A 2B 3C 5E 7G 15M 00(全為0，輸入結束)\n");
scanf("%d%c",&i,&x); //輸入結點編號及結點值
while((i!=0)&&(x!=0))
{
q=(BinNode *)malloc(sizeof(BinNode));//申請結點內存
q->data=x; //保存數據
q->lchild=NULL;
q->rchild=NULL;
s[i]=q; //s[i]存放第i號結點的指針
if(i==1) //1號結點是根結點
t=q; //保存根結點指針,以備返回
else
{
j=i/2; //由該結點號求雙親結點號
if((i%2)==0)
s[j]->lchild=q; //i為偶數是左孩子,該結點指針存入雙親結點的左孩子指針
else
s[j]->rchild=q; //i為奇數是右孩子,該結點指針存入雙親結點的右孩子指針
}
scanf("%d%c",&i,&x);//繼續輸入結點編號和結點值
}
return t; //返回根結點的指針(二叉鏈表的指針)
}
void DisplayBinTree(BinTree T)//用縮進表示二叉樹
{
BinTree stack[100],p; //棧(結點指針數組)、當前結點指針
int level[100]; //棧(每層根結點對應的空格 數 )
int flag[100]; //棧（flag[]=0,1,2分別表示是根結點、左子樹、右子樹 ）
int top,n,i; //棧頂指針，空格個數，循環變數
if(T!=NULL) //若有根結點
{
top=1; //1號結點(根結點 )
stack[top]=T; //入棧(保存根結點指針)
level[top]=1; //顯示空格的個數
flag[top]=0; //根結點
while(top>0) //有根結點
{
p=stack[top]; //取根結點指針
n=level[top]; //取顯示空格的個數
for(i=1;i<=n;i++)//顯示空格(縮進)
printf(" ");
if(flag[top]==0) //若是根結點
printf("T:%c\n",p->data); //顯示根結點
else //不是根結點
{
if(flag[top]==2) //是右子樹根結點
printf("R:%c\n",p->data); //顯示右子樹根結點
if(flag[top]==1) //是左子樹根結點
printf("L:%c\n",p->data,top); //顯示左子樹根結點
}
top--; //顯示一個(出棧一個)結點，top-1
if(p->rchild!=NULL)//若有右孩子
{
top++; //保存一個根結點,top+1
stack[top]=p->rchild;//保存右子樹根結點
level[top]=n+3;
flag[top]=2;
}
if(p->lchild!=NULL)//若有左孩子
{
top++;
stack[top]=p->lchild;//保存左子樹根結點
level[top]=n+3;
flag[top]=1;
}
// printf("level[top]=%d\n",level[top]);
}
}
}
main()
{
BinNode *T; //根結點的指針
T=creat(); //建二叉樹
printf("\n用縮進表示二叉樹的層次(如ppt62所示):\n");
DisplayBinTree(T);
getch();
}
Ⅶ 二叉樹遍歷的演算法實現
從二叉樹的遞歸定義可知，一棵非空的二叉樹由根結點及左、右子樹這三個基本部分組成。因此，在任一給定結點上，可以按某種次序執行三個操作：
⑴訪問結點本身（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);}}
Ⅷ 什麼叫遍歷演算法(最好有例子)
遍歷演算法：所謂遍歷(Traversal)，是指沿著某條搜索路線，依次對樹中每個結點均做一次且僅做一次訪問。訪問結點所做的操作依賴於具體的應用問題。遍歷是二叉樹上最重要的運算之一，是二叉樹上進行其它運算之基礎。當然遍歷的概念也適合於多元素集合的情況，如數組。
遍歷演算法概念延伸：
圖遍歷：圖遍歷又稱圖的遍歷，屬於數據結構中的內容。指的是從圖中的任一頂點出發，對圖中的所有頂點訪問一次且只訪問一次。圖的遍歷操作和樹的遍歷操作功能相似。圖的遍歷是圖的一種基本操作，圖的許多其它操作都是建立在遍歷操作的基礎之上。
舉例：
遍歷二叉樹搜索路線：
從二叉樹的遞歸定義可知，一棵非空的二叉樹由根結點及左、右子樹這三個基本部分組成。因此，在任一給定結點上，可以按某種次序執行三個操作：⑴訪問結點本身（N），⑵遍歷該結點的左子樹（L），⑶遍歷該結點的右子樹（R）。以上三種操作有六種執行次序：NLR、LNR、LRN、NRL、RNL、RLN。前三種次序與後三種次序對稱。
遍歷二叉樹的執行蹤跡三種遞歸遍歷演算法的搜索路線相同（如下圖虛線所示）。具體線路為：從根結點出發，逆時針沿著二叉樹外緣移動，對每個結點均途徑三次，最後回到根結點。
Ⅸ 求高手賜教：層次遍歷一棵樹的演算法思想
利用隊列 首先將根節點入隊，再循環里出隊，並將其子節點入隊，循環直到對列為空就行
回復1樓 就是因為對列是先進先出的才用隊列 如果先進後出就變成倒序甚至亂序了
Ⅹ 二叉樹的遍歷演算法
這里有二叉樹先序、中序、後序三種遍歷的非遞歸演算法，此三個演算法可視為標准演算法。
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