二叉樹三種非遞歸遍歷的區別

1 #include <iostream>
  2
  3 #define MAXN  100
  4 using namespace stbd;
  5
  6
  7 struct BTNode
  8 {
  9     char tag;
10     BTNode *left;
11     BTNode *right;
12 };
13
14 class BTree
15 {
16 private:
17     BTNode **root;
18     void BuildBTree(BTNode **root);
19
20 public:
21     /*遞歸版本*/
22     void PreVisit(BTNode *root);
23     void InVisit(BTNode *root);
24     void PostVisit(BTNode *root);
25
26     /*非遞歸版本*/
27     void NR_PreVisit(BTNode *root);
28     void NR_InVisit(BTNode *root);
29     void NR_PostVisit(BTNode *root);
30
31     BTree(BTNode **r);
32     BTree();
33 };
34
35 BTree::BTree()
36 {
37
38 }
39
40 BTree::BTree(BTNode **r)
41 {
42     root = r;
43     /*
44 *root = new BTNode; 45     (*root)->left = NULL;
46 (*root)->right = NULL; 47     */
48     BuildBTree(root);
49 }
50
51 /*先序方式插入結點*/
52 void BTree::BuildBTree(BTNode **root)
53 {
54     char c;
55    
56     c = getchar();
57     if(c == '#')
58         *root=NULL;
59     else{
60         *root = new BTNode;
61         (*root)->tag = c;
62         BuildBTree(&(*root)->left);
63         BuildBTree(&(*root)->right);
64     }
65 }
66
67 void BTree::PreVisit(BTNode *root)
68 {
69     if(root!=NULL)
70     {
71         printf("%c ", root->tag );
72         PreVisit(root->left);
73         PreVisit(root->right);
74     }
75 }
76
77 void BTree::InVisit(BTNode *root)
78 {
79     if(root!=NULL)
80     {
81         InVisit(root->left);
82         printf("%c ", root->tag );
83         InVisit(root->right);
84     }
85 }
86
87 void BTree::PostVisit(BTNode *root)
88 {
89     if(root!=NULL)
90     {
91         PostVisit(root->left);
92         PostVisit(root->right);
93         printf("%c ", root->tag );
94     }
95 }
96
97 void BTree::NR_PreVisit(BTNode *root)
98 {
99     BTNode *s[MAXN];
100     int top=0;
101
102     while(top!=0 || root!=NULL)
103     {
104         while(root!=NULL)
105         {
106             s[top] = root;
107             printf("%c ", s[top++]->tag);
108             root = root->left;
109         }
110         if(top>0)
111         {
112             root = s[–top];
113             root = root->right;
114         }
115     }
116 }
117
118 void BTree::NR_InVisit(BTNode *root)
119 {
120     BTNode *s[MAXN];
121     int top=0;
122    
123     while(top!=0 || root!=NULL)
124     {
125         while(root!=NULL)
126         {
127             s[top++]=root;
128             root = root->left;
129         }
130         if(top>0)
131         {
132             root = s[–top];
133             printf("%c ", root->tag);
134             root = root->right;
135         }
136     }
137 }
138
139 void BTree::NR_PostVisit(BTNode *root)
140 {
141     BTNode *s[MAXN], *tmp=NULL;
142     int top=0;
143
144     while(top!=0 || root!=NULL)
145     {
146         while(root!=NULL)
147         {
148             s[top++]=root;
149             root=root->left;
150         }
151         if(top>0)
152         {
153             root = s[–top];
154
155             /*右孩子不存在或者已經訪問過,root出棧並訪問*/
156             if( (root->right == NULL) || (root->right == tmp) ) 
157             {
158                 printf("%c ", root->tag);
159                 tmp = root;        //保存root指針
160                 root=NULL;         //當前指針置空,防止再次入棧
161             }
162
163             /*不出棧,繼續訪問右孩子*/
164             else
165             {
166                 top++;             //與root=s[–top]保持平衡
167                 root = root->right;
168             }
169         }
170     }
171 }
172
173 int main()
174 {
175     BTNode *root=NULL;
176     BTree bt(&root);  //頭指針的地址
177    
178     bt.NR_PreVisit(root);
179     printf("\n");
180     bt.NR_InVisit(root);
181     printf("\n");
182     bt.NR_PostVisit(root);
183     printf("\n");
184     return 0;
185 }

先上代碼,tb帶NR(Non-recursive)的表示非遞歸遍歷。

 

測試數據:

124#8##5##369###7##

 

表示的二叉樹:

 

用windows自帶的畫圖畫的,的確是粗糙瞭點。。。

 

測試結果:

1 2 4 8 5 3 6 9 7
4 8 2 5 1 9 6 3 7
8 4 5 2 9 6 7 3 1

 

 

一、關於二叉樹的建立

 

  首先要註意二叉樹的創建過程,這裡用的是先序方式遞歸插入結點,所以輸入數據的時候,必須按照先序方式輸入,

左結點或右結點為空的,用#表示。否則,輸入不會有響應,因為遞歸過程還未結束,按CTRL+Z也沒用。當然可以用其

他方式插入(如中序遞歸插入,後序遞歸插入等)。

 

二、三種非遞歸遍歷的區別

 

  前序、中序和後序的遞歸遍歷方式比較簡單,這裡就不講瞭。而非遞歸的遍歷方式,隻需要用數組存儲結點指針,模擬系統棧的工作機制就可以瞭。

先說先序非遞歸遍歷,按照根-左-右的方式訪問的話,需要將當前結點壓棧(同時打印當前結點信息),直到左子樹為空(內層while);然後出棧,訪問

右結點;後面的操作就跟前面的一樣瞭(外層while)。

  對於中序非遞歸遍歷,可以看到代碼結構幾乎一模一樣,隻是打印結點信息的位置不同而已。這是因為中序遍歷是左-根-右,這樣前序和中序非

遞歸遍歷(根-左和左-根都是壓棧動作,且出棧動作的對象都是父節點)是一致的。

 

  對於後序非遞歸遍歷,因為後序遍歷是左-右-根,根的訪問是在右孩子之後,而這意味著兩種情況:

  1、右孩子不為空(繼續訪問右孩子);

  2、右孩子為空,從左孩子返回,則需要訪問根結點。

  為瞭區分這兩種情況(物理形式上從左孩子返回,還是從右孩子返回來訪問根節點),對於右孩子的訪問又需要判斷根結點的右孩子是否為空或者已

訪問過(右子樹已遍歷過)。除這兩種情況外,都不應該訪問根節點,而是要繼續進入右子樹。

  

三、補充說明

 

  在後序非遞歸遍歷的else語句中top++純粹是為瞭使棧保持平衡,因為對於2)繼續訪問右孩子這種情況,不需要出棧,而前面的root[–top]包含

瞭出棧操作,以此保證棧的正確性(當然可以有其他的處理,這裡也是考慮到三種非遞歸遍歷方式的統一性)。

  兩個while不會提高程序的時間復雜度,因為二叉樹的結點個數是固定的,內層while是為瞭提高算法的邏輯性。

 

四、遞歸->非遞歸

 

  另外,今天實習看到一個老師寫的非遞歸代碼,非常棒,贊一個!他僅僅是將程序的返回地址和函數的形參、局部變量都保存起來,然後在退出時

還原現場;同樣是非遞歸,但是這種方式更接近編譯器的處理方式,同操作系統的任務切換也比較一致;所以這種處理方法為遞歸自動轉換為非遞歸奠

定瞭基礎。

  分享一下他當場編寫的非遞歸的漢諾塔:

 

  1 #include <stdio.h>
  2 #include <iostream>
  3
  4 using namespace std ;
  5
  6 #define  MAXSIZE  1000
  7
  8 struct SNode
  9 {
 10     int  n;
 11     char from ;
 12     char to;
 13     char aux ;
 14     int  label ;
 15 } ;
 16
 17 struct STK
 18 {
 19    
 20     SNode  stack[MAXSIZE] ;
 21     int sp  ;
 22     STK()
 23     {
 24         sp = 0 ;
 25     };
 26     void push (int n,char from,char to,char aux, int label )
 27     {
 28         if ( sp>= MAXSIZE )
 29         {
 30             printf ( "STK is full!\n" ) ;
 31         }
 32         stack[sp].n = n ;
 33         stack[sp].from = from ;
 34         stack[sp].to = to ;
 35         stack[sp].aux = aux ;
 36         stack[sp++].label = label ;
 37     };
 38     SNode POP()
 39     {
 40         if ( sp <=0 )
 41         {
 42             printf ( "STK is empty!\n" ) ;
 43         }
 44         return stack[–sp] ;
 45     };
 46 } ;
 47
 48 void move(int n,char from,char to,char aux)
 49 {
 50     if(n==1)
 51     {
 52         cout<<"將#1盤從"<<from<<"移到"<<to<<endl;
 53 }
 54     else
 55     {
 56          move(n-1,from,aux,to);
 57          cout<<"將#"<<n<<"盤從"<<from<<"移到"<<to<<endl;
 58          move(n-1,aux,to,from);
 59 }
 60 }
 61
 62
 63 void move_stk(int n,char from,char to,char aux)
 64 {
 65     STK stk ;
 66     char tmp;
 67 S1:
 68     if(n==1)
 69     {
 70         cout<<"將#1盤從"<<from<<"移到"<<to<<endl;
 71     }
 72     else
 73    {
 74     stk.push (n,from,to,aux,2 ) ;
 75     n = n-1 ;
 76     tmp = to ;
 77     to = aux ; 
 78     aux = tmp ;
 79     goto S1;
 80          // move(n-1,from,aux,to);
 81 S2:
 82          cout<<"將#"<<n<<"盤從"<<from<<"移到"<<to<<endl;
 83
 84     stk.push (n,from,to,aux,3 ) ;
 85     n = n-1 ;
 86     tmp = from ;
 87     from = aux ; 
 88     aux = tmp ;
 89     goto S1;
 90          // move(n-1,aux,to,from);
 91 }
 92 S3:
 93     if ( stk.sp > 0 )
 94     {
 95         SNode sn = stk.POP() ;
 96         n = sn.n ;
 97         from = sn.from;
 98         to = sn.to ;
 99         aux = sn.aux ;
100         if  ( 1 == sn.label  )
101             goto S1;
102         else if ( 2 == sn.label )
103             goto S2;
104         else
105             goto S3;       
106     }
107 }
108
109
110
111 int main(int argc, char * argv[])
112 {
113     move ( 3,'A','B', 'C' );
114     printf ( "================================\n" ) ;
115     move_stk ( 3,'A','B', 'C' );
116
117     return 0;
118 }

作者:tbwshc

發佈留言

發佈留言必須填寫的電子郵件地址不會公開。