二叉树的遍历，除了上篇文章中的传统递归和使用的栈结构的非递归方式，还有如下这种Morris遍历方式，该算法的构思非常巧妙：利用前驱空闲的rightChild指针指向当前节点，形成一个环。时间复杂度和前面两种一样，还是O(n)，但是空间复杂度由O(n)直接下降到了O(1)。代码如下：
/*************************************************************************
> File Name: MorrisTraversal.c
> Description: 线索二叉树的实现
> Author: Yves
> E-mail:
> Created Time: 2015-5-23. 22:51:16
************************************************************************/ #include <stdio.h>
#include <stdlib.h> typedef char ElemType;
typedef struct tagBiTreeNode
{
ElemType data;
struct tagBiTreeNode* leftChild;
struct tagBiTreeNode* rightChild;
}BiTreeNode, *pBiTreeNode;//指向BiTNode的指针 static void CreatBiTree(pBiTreeNode *root);//创建二叉树
static void PreOrderMorrisTraversal(pBiTreeNode root);//前序Morris遍历
static void InOrderMorrisTraversal(pBiTreeNode root);//中序Morris遍历
static void PostOrderMorrisTraversal(pBiTreeNode root);//后序Morris遍历 pBiTNode pre; int main(void)
{
pBiTreeNode root;
printf("Please input the node of the tree(preorder sequence): ");
CreatBiTree(&root);
printf("Traverse the tree in PreOrderMorrisTraversal\n");
PreOrderMorrisTraversal(root);
printf("Traverse the tree in InOrderMorrisTraversal\n");
InOrderMorrisTraversal(root);
printf("Traverse the tree in PostOrderMorrisTraversal\n");
PostOrderMorrisTraversal(root) return ;
} static void CreatBiTree(pBiTreeNode *root)
{
ElemType c;
scanf("%c",&c);
if(c == '#')
{
*root = NULL;
}else
{
*root = (pBiTreeNode)malloc(sizeof(BiTreeNode));
(*root)->data = c;
CreatBiTree(&(*root)->leftChild);
CreatBiTree(&(*root)->rightChild);
}
} static void PreOrderMorrisTraversal(pBiTreeNode root)
{
if(root == NULL)
{
return;
}
pBiTreeNode cur,pre,temp;
cur = root;
while(cur != NULL)
{
if(!cur->leftChild)
{
printf("%c ", cur->data);
pre = cur;
cur = cur->rightChild;
}else
{
for(temp = cur->leftChild; temp->rightChild != NULL && temp->rightChild != cur; temp = temp->rightChild);
if(temp->rightChild == NULL)
{
temp->rightChild = cur;
printf("%c ", cur->data);
pre = cur;
cur = cur->leftChild;
}else
{ temp->rightChild = NULL;
cur = cur->rightChild;
}
}
}
} static void InOrderMorrisTraversal(pBiTreeNode root)
{
if(root == NULL)
{
return;
}
pBiTreeNode cur,pre,temp;
cur = root;
while(cur != NULL)
{
if(!cur->leftChild)
{
printf("%c ", cur->data);
pre = cur;
cur = cur->rightChild;
}else
{
for(temp = cur->leftChild; temp->rightChild != NULL && temp->rightChild != cur; temp = temp->rightChild);
if(temp->rightChild == NULL)
{
temp->rightChild = cur;
cur = cur->leftChild;
}else /*Meaning the left tree has been accessed completely.*/
{
printf("%c ", cur->data);
temp->rightChild = NULL;
pre = cur;
cur = cur->rightChild;
}
}
}
} static void PostOrderMorrisTraversal(pBiTreeNode root)
{
//coding
}