樹遍歷演算法
㈠ 二叉樹遍歷的演算法
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);
}
}
㈡ 遍歷二叉樹遞歸演算法
「這個函數的參數visit應該是另一個函數的地址是把，但我怎麼感覺不管怎麼遞歸它只是在訪問根的時候被調用過一次」
首先，你是對的，visit確實是一個指向函數的指針；
然後，它只是在訪問根的時候被調用過一次，這種說法就很片面了。
我覺得應該這么說：(*visit)()函數在BTreePreOrger（）函數的一次執行過程中只被調用過一次，但是BTreePreOrger()函數執行了很多次，因此(*visit)()就被調用了n次（假設該樹有n個節點）
㈢ 二叉樹遍歷演算法，就是給定兩種遍歷結果求另一種遍歷順序
假設某二叉樹的先序遍歷序列是abdgcefh，中序遍歷序列是dgbaechf，畫出二叉樹，並給出其後序遍歷序列。
分析過程：
以下面的例題為例進行講解：
已知一棵二叉樹的先序遍歷序列和中序遍歷序列分別是abdgcefh、dgbaechf，求二叉樹及後序遍歷序列。
分析：先序遍歷序列的第一個字元為根結點。對於中序遍歷，根結點在中序遍歷序列的中間，左邊部分是根結點的左子樹的中序遍歷序列，右邊部分是根結點的右子樹的中序遍歷序列。
先序：abdgcefh --> a bdg cefh
中序：dgbaechf --> dgb a echf
得出結論：a是樹根，a有左子樹和右子樹，左子樹有bdg結點，右子樹有cefh結點。
先序：bdg --> b dg
中序：dgb --> dg b
得出結論：b是左子樹的根結點，b無右子樹，有左子樹。
先序：dg --> d g
中序：dg --> d g
得出結論：d是b的左子樹的根結點，d無左子樹，有右子樹。
先序：cefh --> c e fh
中序：echf --> e c hf
得出結論：c是右子樹的根結點，c有左子樹(只有e結點)，有右子樹(有fh結點)。
先序：fh --> f h
中序：hf --> h f
得出結論：f是c的左子樹的根結點，f有左子樹(只有h結點)，無右子樹。
還原二叉樹為：
a
b c
d e f
g h
後序遍歷序列：gdbehfca
㈣ 什麼叫遍歷演算法(最好有例子)
遍歷演算法：所謂遍歷(Traversal)，是指沿著某條搜索路線，依次對樹中每個結點均做一次且僅做一次訪問。訪問結點所做的操作依賴於具體的應用問題。遍歷是二叉樹上最重要的運算之一，是二叉樹上進行其它運算之基礎。當然遍歷的概念也適合於多元素集合的情況，如數組。
遍歷演算法概念延伸：
圖遍歷：圖遍歷又稱圖的遍歷，屬於數據結構中的內容。指的是從圖中的任一頂點出發，對圖中的所有頂點訪問一次且只訪問一次。圖的遍歷操作和樹的遍歷操作功能相似。圖的遍歷是圖的一種基本操作，圖的許多其它操作都是建立在遍歷操作的基礎之上。
舉例：
遍歷二叉樹搜索路線：
從二叉樹的遞歸定義可知，一棵非空的二叉樹由根結點及左、右子樹這三個基本部分組成。因此，在任一給定結點上，可以按某種次序執行三個操作：⑴訪問結點本身（N），⑵遍歷該結點的左子樹（L），⑶遍歷該結點的右子樹（R）。以上三種操作有六種執行次序：NLR、LNR、LRN、NRL、RNL、RLN。前三種次序與後三種次序對稱。
遍歷二叉樹的執行蹤跡三種遞歸遍歷演算法的搜索路線相同（如下圖虛線所示）。具體線路為：從根結點出發，逆時針沿著二叉樹外緣移動，對每個結點均途徑三次，最後回到根結點。
㈤ 實現二叉樹遍歷的遞歸演算法（求二叉樹的節點總數，高度）
#include<stdlib.h>
#include<stdio.h>
#define MAXSIZE 100
typedef char ElemType;
typedef struct bonde
{
ElemType data;
struct bonde *lchild,*rchild;
}BTree;
typedef struct
{
BTree *data[MAXSIZE];
int top;
}Stack;
BTree *CreateBTree();
void porder(BTree *T);
int leafs(BTree *T);
int depth(BTree *T);
void main()//主函數
{
BTree *b;
int m,n;
printf("Create a tree....\n\n");
b=(BTree *)malloc(sizeof(int));
b=CreateBTree();
printf("\n");
porder(b);
m=leafs(b);
printf("\nthe tree's leafs:%d\n",m);
n=depth(b);
printf("\n\nthe tree's heigh:%d\n",n);
}
void StackInit(Stack *s)
{
s->top=-1;
}
int StackEmpty(Stack s)
{
if(s.top==-1)
return 1;
else
return 0;
}
int push(Stack *s,BTree *e)
{
if(s->top==MAXSIZE-1)
return 0;
else
{
(s->top)++;
s->data[s->top]=e;
return 1;
}
}
BTree *pop(Stack *s)
{
BTree *e;
if(s->top==-1)
return NULL;
else
{
e=s->data[(s->top)--];
return e;
}
}
BTree * CreateBTree()//建樹過程
{
char ch;
BTree *b;
ch = getchar();
if(ch == '@')
{
b = NULL;
}
else
{
if(!(b = (BTree *)malloc(sizeof(BTree)))) exit(-1);
b->lchild = CreateBTree();
b->data=ch;
printf("%5c",p->data);
b->rchild = CreateBTree();
}
return b;
}
void porder(BTree *T)//先序遍歷該樹並輸出
{
Stack s;
StackInit(&s);
while (t!=NULL||!StackEmpty(s))
{
if(t!=NULL)
{
printf("%c ",t->data);
push(&s,t);
t=t->lchild;
}
else
{
t=pop(&s);
t=t->rchild;
}
}
}
int leafs(BTree *T)、、求節點總數
{
int num1,num2;
if(T==NULL)
return 0;
else
if(T->lchild==NULL && T->rchild==NULL)
return 1;
else
{
num1=leafs(T->lchild);
num2=leafs(T->rchild);
return(num1+num2);
}
}
int depth(BTree *T)//求高度
{
int dep1,dep2;
if(T==NULL)
return 0;
else
{
dep1=depth(T->lchild);
dep2=depth(T->rchild);
if(dep1>dep2)
return(dep1+1);
else
return(dep2+1);
}
}
㈥ 求二叉樹遍歷演算法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
㈦ 二叉樹遍歷的演算法實現
從二叉樹的遞歸定義可知，一棵非空的二叉樹由根結點及左、右子樹這三個基本部分組成。因此，在任一給定結點上，可以按某種次序執行三個操作：
⑴訪問結點本身（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．遍歷方案 從二叉樹的遞歸定義可知，一棵非空的二叉樹由根結點及左、右子樹這三個基本部分組成。因此，在任一給定結點上，可以按某種次序執行三個操作： （1）訪問結點本身(N)， （2）遍歷該結點的左子樹(L)， （3）遍歷該結點的右子樹(R)。以上三種操作有六種執行次序： NLR、LNR、LRN、NRL、RNL、RLN。 注意： 前三種次序與後三種次序對稱，故只討論先左後右的前三種次序。 2．三種遍歷的命名 根據訪問結點操作發生位置命名： ① NLR：前序遍歷(PreorderTraversal亦稱(先序遍歷)) ——訪問結點的操作發生在遍歷其左右子樹之前。 ② LNR：中序遍歷(InorderTraversal) ——訪問結點的操作發生在遍歷其左右子樹之中(間)。 ③ LRN：後序遍歷(PostorderTraversal) ——訪問結點的操作發生在遍歷其左右子樹之後。 注意： 由於被訪問的結點必是某子樹的根，所以N(Node)、L(Left subtlee)和R(Right subtree)又可解釋為根、根的左子樹和根的右子樹。NLR、LNR和LRN分別又稱為先根遍歷、中根遍歷和後根遍歷。 遍歷演算法 1．中序遍歷的遞歸演算法定義： 若二叉樹非空，則依次執行如下操作： (1)遍歷左子樹； (2)訪問根結點； (3)遍歷右子樹。 2．先序遍歷的遞歸演算法定義： 若二叉樹非空，則依次執行如下操作： (1) 訪問根結點； (2) 遍歷左子樹； (3) 遍歷右子樹。 3．後序遍歷得遞歸演算法定義： 若二叉樹非空，則依次執行如下操作： (1)遍歷左子樹； (2)遍歷右子樹； (3)訪問根結點。 ~
㈨ c++二叉樹的幾種遍歷演算法
遍歷二叉樹的所有結點且僅訪問一次。按照根節點位置的不同分為前序遍歷，中序遍歷，後序遍歷（除此之外還有層次遍歷，但不常用，此處不做解釋）。
1.前序遍歷：根節點->左子樹->右子樹（根節點在前面）。
2.中序遍歷：左子樹->根節點->右子樹（根節點在中間）。
3.後序遍歷：左子樹->右子樹->根節點（根節點在後邊）。
例如：求下面樹的三種遍歷：
前序遍歷：abdefgc；
中序遍歷：debgfac；
後序遍歷：edgfbca。
㈩ 二叉樹的遍歷演算法
怎麼又來問了，不是回答過你了嗎？很簡單，就是一個遞歸過程。在函數中以先序遍歷的第一個結點在中序遍歷中為界把中序遍歷分為兩半，再分別把左一半和右一半作為這個結點的左子樹和右子樹進行遞歸。完成遞歸之後再列印該結點即可。結束遞歸的條件是左子樹或右子樹沒有結點。下面是簡單的程序示意，可以用任意語言實現。
不過你給出的這個前序遍歷和中序遍歷卻是有問題的，如果改成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)