二叉樹的前序中序後序遍歷（當然是非遞歸的！），二叉樹遞歸

二叉樹的前序中序後序遍歷（當然是非遞歸的！），二叉樹遞歸

二叉樹的三種遍歷方式一直都是為人津津樂道的面試題，考察一個人對遞歸的理解讓他寫個三種遍歷方式是最簡單的考察方式了，那麼考察一個人對遞歸的理解更加深層次的方式就是讓他用循環模擬遞歸（就是把遞歸代碼轉換成非遞歸），一般想要實現這樣的東西是需要棧的，或許說使用棧的結構更加貼合函數棧的壓入和彈出，更加好理解

• 因為前序遍歷是首先訪問根節點的，所以見到節點就訪問，然後再去訪問左孩子和右孩子。原先使用遞歸的方式，棧幀的模擬可以使用棧來實現，因為是先訪問了左節點，所以左節點應該在右節點之後入棧，b不難寫出下面的代碼
  

   1 void PreOrder_NonR()
   2 
   3                 {
   4 
   5                                  if (_root == NULL )
   6 
   7                                 {
   8 
   9                                                  return;
  10 
  11                                 }
  12 
  13                                  stack<BinaryTreeNode <T>*> s;
  14 
  15                                 s.push(_root);
  16 
  17                                  while (!s.empty())
  18 
  19                                 {
  20 
  21                                                  BinaryTreeNode<T >* top = s.top();
  22 
  23                                                 cout << top->_data << " " ;
  24 
  25                                                 s.pop();
  26 
  27                                                  if (top->_right)
  28 
  29                                                 {
  30 
  31                                                                 s.push(top->_right);
  32 
  33                                                 }
  34 
  35                                                  if (top->_left)
  36 
  37                                                 {
  38 
  39                                                                 s.push(top->_left);
  40 
  41                                                 }
  42 
  43                                 }
  44 
  45                                 cout << endl;
  46 
  47                 }

   

• 中序遍歷可以采用遞歸的思考方式，因為中序遍歷的方式是在訪問完左子樹之後再去訪問根節點，所以在訪問完根節點之後進入右子樹，右子樹又相當於一個新的根節點，所以應該采取訪問完根節點之後將右孩子立刻壓入棧，然後進入循環可以寫出下面的代碼
  

   1 void InOrder_NonR()
   2 
   3                 {
   4 
   5                                  stack<BinaryTreeNode <T>*> s;
   6 
   7                                  BinaryTreeNode<T > *cur = _root;
   8 
   9                                  while (cur || !s.empty())
  10 
  11                                 {
  12 
  13                                                  while (cur)
  14 
  15                                                 {
  16 
  17                                                                 s.push(cur);
  18 
  19                                                                 cur = cur->_left;
  20 
  21                                                 }
  22 
  23                                                  if (!s.empty())
  24 
  25                                                 {
  26 
  27                                                                  BinaryTreeNode<T > *top = s.top();
  28 
  29                                                                 cout << top->_data << " " ;
  30 
  31                                                                 s.pop();
  32 
  33                                                                 cur = top->_right;
  34 
  35                                                 }
  36 
  37                                 }
  38 
  39                                 cout << endl;
  40 
  41                 }

   

• 後序遍歷是先訪問左子樹和右子樹，所以當左孩子出棧的時候，下一個棧內節點（即根節點）不能立刻就訪問，需要考慮幾種情況，如果此時此刻右孩子為空，那麼可以訪問，如果此時有孩子不為空，那麼需要考慮右孩子是否被訪問過了，如果訪問過了，則可以訪問根節點，否則需要先訪問右子樹然後再去訪問根節點，可以利用一個變量來保存之前訪問的是哪一個節點，可以寫出如下代碼

 1  void PostOrder_NonR()
 2 
 3                 {
 4 
 5                                  stack<BinaryTreeNode <T> *> s;
 6 
 7                                  BinaryTreeNode<T >* PreVisited = NULL;
 8 
 9                                  BinaryTreeNode<T >* cur = _root;
10 
11                                  while (cur || !s.empty())
12 
13                                 {
14 
15                                                  while (cur)
16 
17                                                 {
18 
19                                                                 s.push(cur);
20 
21                                                                 cur = cur->_left;
22 
23                                                 }
24 
25                                                  BinaryTreeNode<T > *top = s.top();
26 
27                                                  if (top->_right == NULL || PreVisited == top->_right)
28 
29                                                 {
30 
31                                                                 cout << top->_data << " " ;
32 
33                                                                 s.pop();
34 
35                                                                 PreVisited = top;
36 
37                                                 }
38 
39                                                  else
40 
41                                                 {
42 
43                                                                 cur = top->_right;
44 
45                                                 }
46 
47                                 }
48 
49                                 cout << endl;
50 
51                 }

這是我從我的筆記導出來的，話說縮進怎麼變成這德行了。。。