递归和非递归的进行二叉树的遍历从某种意义上来讲都是需要辅助空间的。那么进行非递归的和不需要辅助空间的遍历会有这种可能吗？答案是肯定的，应用线索二叉树，这样就能把左子树或者右子树为空的节点利用起来，二叉树线索之后就可能找到某个节点的前区或者后继。一个含有n个节点的二叉树，可定会有n+1个指针是空的。所有利用这n+1一个指针就能将二叉树线索化而不遗漏任何一个节点。
下面给出利用这种线索化来遍历二叉树的中序遍历，现在只研究到中序遍历：
1，设置变量current = root
2，如果current的左子树是空的，打印这个节点的value，然后将current设置为current->rchild.
3，如果current的左子树不为空，那么找到左子树中序遍历最后一个节点，既然是最后的一个了，那么这个节点的右子树是空的，让它指向current，然后让current指向其左子树。
下面的代码并没有破坏原来树的结构，在线索化遍历之后又重新还原树原来的样子，下面是代码：
[cpp]
#include
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
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;
}