不用遞歸和輔助空間對二叉樹進行遍歷

遞歸和非遞歸的進行二叉樹的遍歷從某種意義上來講都是需要輔助空間的。那麼進行非遞歸的和不需要輔助空間的遍歷會有這種可能嗎？答案是肯定的，應用線索二叉樹，這樣就能把左子樹或者右子樹為空的節點利用起來，二叉樹線索之後就可能找到某個節點的前區或者後繼。一個含有n個節點的二叉樹，可定會有n+1個指針是空的。所有利用這n+1一個指針就能將二叉樹線索化而不遺漏任何一個節點。

下面給出利用這種線索化來遍歷二叉樹的中序遍歷，現在只研究到中序遍歷：

1，設置變量current = root

2，如果current的左子樹是空的，打印這個節點的value，然後將current設置為current->rchild.

3，如果current的左子樹不為空，那麼找到左子樹中序遍歷最後一個節點，既然是最後的一個了，那麼這個節點的右子樹是空的，讓它指向current，然後讓current指向其左子樹。

下面的代碼並沒有破壞原來樹的結構，在線索化遍歷之後又重新還原樹原來的樣子，下面是代碼：

[cpp]
#include<iostream>  
using namespace std; 
 
typedef struct tree_node_s { 
    int value; 
    struct tree_node_s* lchild; 
    struct tree_node_s* rchild; 
}tree_node_t; 
 
 
tree_node_t* createNode(int value) { 
    tree_node_t* node = (tree_node_t*)malloc(sizeof(tree_node_t)); 
    node->value = value; 
    node->lchild = NULL; 
    node->rchild = NULL; 
    return node; 
} 
 
void inorderTraverse(tree_node_t* root) { 
    if (root) { 
        inorderTraverse(root->lchild); 
        cout << root->value << " "; 
        inorderTraverse(root->rchild); 
    } 
} 
 
void iterativeTraverse(tree_node_t* root) { 
    tree_node_t* current = root; 
    tree_node_t* prev = NULL; 
    while (NULL != current) { 
        if (NULL == current->lchild) { 
            cout << current->value << " "; 
            current = current->rchild; 
        } else { 
            prev = current->lchild; 
            while (prev->rchild && prev->rchild != current) 
                prev = prev->rchild; 
            if (NULL == prev->rchild) { 
                prev->rchild = current; 
                current = current->lchild; 
            } else { 
                prev->rchild = NULL; 
                cout << current->value << " "; 
                current = current->rchild; 
            } 
        } 
    } 
} 
 
 
int main(int argc, char* argv[]) { 
    tree_node_t* root = createNode(1); 
    root->lchild = createNode(2); 
    root->rchild = createNode(3); 
    root->lchild->lchild = createNode(4); 
    root->lchild->rchild = createNode(5); 
    iterativeTraverse(root); 
    cout << endl; 
    inorderTraverse(root); 
    cin.get(); 
    return 0; 
} 

#include<iostream>
using namespace std;

typedef struct tree_node_s {
 int value;
 struct tree_node_s* lchild;
 struct tree_node_s* rchild;
}tree_node_t;

tree_node_t* createNode(int value) {
 tree_node_t* node = (tree_node_t*)malloc(sizeof(tree_node_t));
 node->value = value;
 node->lchild = NULL;
 node->rchild = NULL;
 return node;
}

void inorderTraverse(tree_node_t* root) {
 if (root) {
  inorderTraverse(root->lchild);
  cout << root->value << " ";
  inorderTraverse(root->rchild);
 }
}

void iterativeTraverse(tree_node_t* root) {
 tree_node_t* current = root;
 tree_node_t* prev = NULL;
 while (NULL != current) {
  if (NULL == current->lchild) {
   cout << current->value << " ";
   current = current->rchild;
  } else {
   prev = current->lchild;
   while (prev->rchild && prev->rchild != current)
    prev = prev->rchild;
   if (NULL == prev->rchild) {
    prev->rchild = current;
    current = current->lchild;
   } else {
    prev->rchild = NULL;
    cout << current->value << " ";
    current = current->rchild;
   }
  }
 }
}

int main(int argc, char* argv[]) {
 tree_node_t* root = createNode(1);
 root->lchild = createNode(2);
 root->rchild = createNode(3);
 root->lchild->lchild = createNode(4);
 root->lchild->rchild = createNode(5);
 iterativeTraverse(root);
 cout << endl;
 inorderTraverse(root);
 cin.get();
 return 0;
}