二叉樹遞歸與非遞歸遍歷演算法
㈠ c語言實現二叉樹的先序,中序,後序的遞歸和非遞歸演算法和層次遍歷演算法
#include<malloc.h> // malloc()等
#include<stdio.h> // 標准輸入輸出頭文件，包括EOF(=^Z或F6)，NULL等
#include<stdlib.h> // atoi()，exit()
#include<math.h> // 數學函數頭文件，包括floor()，ceil()，abs()等
#define ClearBiTree DestroyBiTree // 清空二叉樹和銷毀二叉樹的操作一樣
typedef struct BiTNode
{
int data; // 結點的值
BiTNode *lchild,*rchild; // 左右孩子指針
}BiTNode,*BiTree;
int Nil=0; // 設整型以0為空
void visit(int e)
{ printf("%d ",e); // 以整型格式輸出
}
void InitBiTree(BiTree &T)
{ // 操作結果：構造空二叉樹T
T=NULL;
}
void CreateBiTree(BiTree &T)
{ // 演算法6.4：按先序次序輸入二叉樹中結點的值(可為字元型或整型，在主程中定義)，
// 構造二叉鏈表表示的二叉樹T。變數Nil表示空(子)樹。修改
int number;
scanf("%d",&number); // 輸入結點的值
if(number==Nil) // 結點的值為空
T=NULL;
else // 結點的值不為空
{ T=(BiTree)malloc(sizeof(BiTNode)); // 生成根結點
if(!T)
exit(OVERFLOW);
T->data=number; // 將值賦給T所指結點
CreateBiTree(T->lchild); // 遞歸構造左子樹
CreateBiTree(T->rchild); // 遞歸構造右子樹
}
}
void DestroyBiTree(BiTree &T)
{ // 初始條件：二叉樹T存在。操作結果：銷毀二叉樹T
if(T) // 非空樹
{ DestroyBiTree(T->lchild); // 遞歸銷毀左子樹，如無左子樹，則不執行任何操作
DestroyBiTree(T->rchild); // 遞歸銷毀右子樹，如無右子樹，則不執行任何操作
free(T); // 釋放根結點
T=NULL; // 空指針賦0
}
}
void PreOrderTraverse(BiTree T,void(*Visit)(int))
{ // 初始條件：二叉樹T存在，Visit是對結點操作的應用函數。修改演算法6.1
// 操作結果：先序遞歸遍歷T，對每個結點調用函數Visit一次且僅一次
if(T) // T不空
{ Visit(T->data); // 先訪問根結點
PreOrderTraverse(T->lchild,Visit); // 再先序遍歷左子樹
PreOrderTraverse(T->rchild,Visit); // 最後先序遍歷右子樹
}
}
void InOrderTraverse(BiTree T,void(*Visit)(int))
{ // 初始條件：二叉樹T存在，Visit是對結點操作的應用函數
// 操作結果：中序遞歸遍歷T，對每個結點調用函數Visit一次且僅一次
if(T)
{ InOrderTraverse(T->lchild,Visit); // 先中序遍歷左子樹
Visit(T->data); // 再訪問根結點
InOrderTraverse(T->rchild,Visit); // 最後中序遍歷右子樹
}
}
void PostOrderTraverse(BiTree T,void(*Visit)(int))
{ // 初始條件：二叉樹T存在，Visit是對結點操作的應用函數
// 操作結果：後序遞歸遍歷T，對每個結點調用函數Visit一次且僅一次
if(T) // T不空
{ PostOrderTraverse(T->lchild,Visit); // 先後序遍歷左子樹
PostOrderTraverse(T->rchild,Visit); // 再後序遍歷右子樹
Visit(T->data); // 最後訪問根結點
}
}
void main()
{
BiTree T;
InitBiTree(T); // 初始化二叉樹T
printf("按先序次序輸入二叉樹中結點的值,輸入0表示節點為空，輸入範例：1 2 0 0 3 0 0\n");
CreateBiTree(T); // 建立二叉樹T
printf("先序遞歸遍歷二叉樹：\n");
PreOrderTraverse(T,visit); // 先序遞歸遍歷二叉樹T
printf("\n中序遞歸遍歷二叉樹：\n");
InOrderTraverse(T,visit); // 中序遞歸遍歷二叉樹T
printf("\n後序遞歸遍歷二叉樹：\n");
PostOrderTraverse(T,visit); // 後序遞歸遍歷二叉樹T
}
㈡ 二叉樹先序遍歷遞歸演算法和非遞歸演算法本質區別
在前面一文，說過二叉樹的遞歸遍歷演算法（二叉樹先根（先序）遍歷的改進），此文主要講二叉樹的非遞歸演算法，採用棧結構
總結先根遍歷得到的非遞歸演算法思想如下：
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;
}
㈢ 二叉樹的深度演算法怎麼算啊
二叉樹的深度演算法：
一、遞歸實現基本思想：
為了求得樹的深度，可以先求左右子樹的深度，取二者較大者加1即是樹的深度，遞歸返回的條件是若節點為空，返回0
演算法：
1
int
FindTreeDeep(BinTree
BT){
2
int
deep=0;
3
if(BT){
4
int
lchilddeep=FindTreeDeep(BT->lchild);
5
int
rchilddeep=FindTreeDeep(BT->rchild);
6
deep=lchilddeep>=rchilddeep?lchilddeep+1:rchilddeep+1;
7
}
8
return
deep;
9
}
二、非遞歸實現基本思想：
受後續遍歷二叉樹思想的啟發，想到可以利用後續遍歷的方法來求二叉樹的深度，在每一次輸出的地方替換成算棧S的大小，遍歷結束後最大的棧S長度即是棧的深度。
演算法的執行步驟如下：
（1）當樹非空時，將指針p指向根節點，p為當前節點指針。
（2）將p壓入棧S中，0壓入棧tag中，並令p執行其左孩子。
（3）重復步驟（2），直到p為空。
（4）如果tag棧中的棧頂元素為1，跳至步驟（6）。從右子樹返回
（5）如果tag棧中的棧頂元素為0，跳至步驟（7）。從左子樹返回
（6）比較treedeep與棧的深度，取較大的賦給treedeep，對棧S和棧tag出棧操作，p指向NULL，並跳至步驟（8）。
（7）將p指向棧S棧頂元素的右孩子，彈出棧tag，並把1壓入棧tag。（另外一種方法，直接修改棧tag棧頂的值為1也可以）
（8）循環（2）~（7），直到棧為空並且p為空
（9）返回treedeep，結束遍歷
1
int
TreeDeep(BinTree
BT
){
2
int
treedeep=0;
3
stack
S;
4
stack
tag;
5
BinTree
p=BT;
6
while(p!=NULL||!isEmpty(S)){
7
while(p!=NULL){
8
push(S,p);
9
push(tag,0);
10
p=p->lchild;
11
}
12
if(Top(tag)==1){
13
deeptree=deeptree>S.length?deeptree:S.length;
14
pop(S);
15
pop(tag);
16
p=NULL;
17
}else{
18
p=Top(S);
19
p=p->rchild;
20
pop(tag);
21
push(tag,1);
22
}
23
}
24
return
deeptree;
25
}
㈣ 浜屽弶鏍戠殑涓搴忋佸墠搴忋佸悗搴忕殑閫掑綊銆侀潪閫掑綊閬嶅巻綆楁硶錛屽眰嬈″簭鐨勯潪閫掑綊閬嶅巻綆楁硶鐨勫疄鐜幫紝搴斿寘鍚寤烘爲鐨勫疄鐜般
浜屽弶鏍戠殑閬嶅巻鏄鎸囨寜鐓т竴瀹氭″簭璁塊棶浜屽弶鏍戜腑鐨勬墍鏈夎妭鐐癸紝涓旀瘡涓鑺傜偣浠呰璁塊棶涓嬈＄殑榪囩▼銆傛槸鏈鍩烘湰鐨勮繍綆楋紝鏄鍏朵粬榪愮畻鐨勫熀紜銆
浜屽弶鏍戞湁涓ょ嶅瓨鍌ㄧ粨鏋勶細欏哄簭瀛樺偍鍜岄摼寮忓瓨鍌
欏哄簭瀛樺偍錛 錛堝瑰畬鍏ㄤ簩鍙夋爲鏉ヨ達紝鍙浠ュ厖鍒嗗埄鐢ㄥ瓨鍌ㄧ┖闂達紝浣嗗逛簬涓鑸鐨勪簩鍙夋爲錛屽彧鏈夊皯鏁扮殑瀛樺偍鍗曞厓琚鍒╃敤錛
[cpp] view plain
typedef struct
{
ElemType data[MaxSize];
int n;
}SqBTree;
閾懼紡瀛樺偍錛
[csharp] view plain
typedef struct node
{
ElemType data;
struct node *lchild;
struct node *rchild;
} BTNode;
浜屽弶鏍戜笁縐嶉掑綊鐨勯亶鍘嗘柟娉曪細
鍏堝簭閬嶅巻 璁塊棶鏍硅妭鐐光啋鍏堝簭閬嶅巻宸﹀瓙鏍戔啋鍏堝簭閬嶅巻鍙沖瓙鏍
涓搴忛亶鍘 涓搴忛亶鍘嗗乏瀛愭爲鈫掕塊棶鏍硅妭鐐光啋涓搴忛亶鍘嗗彸瀛愭爲
鍚庡簭閬嶅巻 鍚庡簭閬嶅巻宸﹀瓙鏍戔啋鍚庡簭閬嶅巻鍙沖瓙鏍戔啋璁塊棶鏍硅妭鐐
浜屽弶鏍戦亶鍘嗙殑閫掑綊綆楁硶錛
[cpp] view plain
void preOrder(BTNode *b) //鍏堝簭閬嶅巻閫掑綊綆楁硶
{
if (b!=NULL)
{
visit(b);
preOrder(b->lchild);
preOrder(b->rchild);
}
}
void InOrder(BTNode *b) //涓搴忛亶鍘嗛掑綊綆楁硶
{
if(b!=NULL)
{
InOrder(b->lchild);
visit(b);
InOrder(b->rchild);
}
}
void PostOrder(BTNode *b) //鍚庡簭閬嶅巻閫掑綊綆楁硶
{
if(b!=NULL){
PostOrder(b->lchild);
PostOrder(b->rchild);
visit(b);
}
}
浜屽弶鏍戦潪閫掑綊閬嶅巻綆楁硶錛
鏈変袱縐嶆柟娉曪細鈶犵敤鏍堝瓨鍌ㄤ俊鎮鐨勬柟娉 鈶″炲姞鎸囧悜鐖惰妭鐐圭殑鎸囬拡鐨勬柟娉 鏆傛椂鍙浠嬬粛涓嬫爤鐨勬柟娉
鍏堝簭閬嶅巻錛
[cpp] view plain
void PreOrder(BTNode *b)
{
Stack s;
while(b!=NULL||!s.empty())
{
if(b!=NULL){
visit(b);
s.push(b);
b=b->left;
}
else{
b=s.pop();
b=b->right;
}
}
}
涓搴忛亶鍘嗭細
[cpp] view plain
void InOrder(BTNode *b){
Stack s;
while(b!=NULL||!s.empty()){
if (b!=NULL)
{
s.push(b);
s=s->left
}
if(!s.empty()){
b=s.pop();
visit(b);
b=b->right;
}
}
}
鍚庡簭閬嶅巻錛
[cpp] view plain
void PostOrder(BTNode *b){
Stack s;
while(b!=NULL){
s.push(b);
}
while(!s.empty()){
BTNode* node=s.pop();
if(node->bPushed){
visit(node);
}
else{
s.push(node);
if(node->right!=NULL){
node->right->bPushed=false;
s.push(node->right);
}
if(node->left!=NULL){
node->left->bpushed=false;
s.push(node->left);
}
node->bPushed=true; //濡傛灉鏍囪瘑浣嶄負true,鍒欒〃紺哄叆鏍
}
}
}
灞傛￠亶鍘嗙畻娉曪細錛堢敤闃熷垪鐨勬柟娉曪級
[cpp] view plain
void levelOrder(BTNode *b){
Queue Q;
Q.push(b);
while(!Q.empty()){
node=Q.front();
visit(node);
if(NULL!=node->left){
Q.push(node->left);
}
if(NULL!=right){
Q.push(node->right);
}
}
}<span style=""></span>
宸茬煡鍏堝簭鍜屼腑搴忔眰鍚庡簭鐨勭畻娉曪細錛堝凡鐭ュ悗搴忓拰涓搴忔眰鍏堝簭鐨勭畻娉曠被浼礆紝浣嗗凡鐭ュ厛搴忓拰鍚庡簭鏃犳硶奼傚嚭涓搴忥級
[cpp] view plain
int find(char c,char A[],int s,int e) /* 鎵懼嚭涓搴忎腑鏍圭殑浣嶇疆銆 */
{
int i;
for(i=s;i<=e;i++)
if(A[i]==c) return i;
}
/* 鍏朵腑pre[]琛ㄧず鍏堝簭搴忥紝pre_s涓哄厛搴忕殑璧峰嬩綅緗錛宲re_e涓哄厛搴忕殑緇堟浣嶇疆銆 */
/* 鍏朵腑in[]琛ㄧず涓搴忥紝in_s涓轟腑搴忕殑璧峰嬩綅緗錛宨n_e涓轟腑搴忕殑緇堟浣嶇疆銆 */
/* pronum()奼傚嚭pre[pre_s鍀瀙re_e]銆乮n[in_s鍀瀒n_e]鏋勬垚鐨勫悗搴忓簭鍒椼 */
void pronum(char pre[],int pre_s,int pre_e,char in[],int in_s,int in_e)
{
char c;
int k;
if(in_s>in_e) return ; /* 闈炴硶瀛愭爲錛屽畬鎴愩 */
if(in_s==in_e){printf("%c",in[in_s]); /* 瀛愭爲瀛愪粎涓轟竴涓鑺傜偣鏃剁洿鎺ヨ緭鍑哄苟瀹屾垚銆 */
return ;
}
c=pre[pre_s]; /* c鍌ㄥ瓨鏍硅妭鐐廣 */
k=find(c,in,in_s,in_e); /* 鍦ㄤ腑搴忎腑鎵懼嚭鏍硅妭鐐圭殑浣嶇疆銆 */
pronum(pre,pre_s+1,pre_s+k-in_s,in,in_s,k-1); /* 閫掑綊奼傝В鍒嗗壊鐨勫乏瀛愭爲銆 */
pronum(pre,pre_s+k-in_s+1,pre_e,in,k+1,in_e); /* 閫掑綊奼傝В鍒嗗壊鐨勫彸瀛愭爲銆 */
printf("%c",c); /* 鏍硅妭鐐硅緭鍑恆 */
}
main()
{
char pre[]="abdc";
char in[]="bdac";
printf("The result:");
pronum(pre,0,strlen(in)-1,in,0,strlen(pre)-1);
getch();
}