XwinterwinterwinterX 于 2016.04.11 17:38 提问

`````` #include<stdio.h>
#include<stdlib.h>

/* A binary tree tNode has data, pointer to left child
and a pointer to right child */
struct tNode
{
int data;
struct tNode* left;
struct tNode* right;
};

/* Function to traverse binary tree without recursion and
without stack */
void MorrisTraversal(struct tNode *root)
{
struct tNode *current,*pre;

if(root == NULL)
return;

current = root;
while(current != NULL)
{
if(current->left == NULL)
{
printf(" %d ", current->data);
current = current->right;
}
else
{
/* Find the inorder predecessor of current */
pre = current->left;
while(pre->right != NULL && pre->right != current)
pre = pre->right;

/* Make current as right child of its inorder predecessor */
if(pre->right == NULL)
{
pre->right = current;
current = current->left;
}

/* Revert the changes made in if part to restore the original
tree i.e., fix the right child of predecssor */
else
{
pre->right = NULL;
printf(" %d ",current->data);
current = current->right;
} /* End of if condition pre->right == NULL */
} /* End of if condition current->left == NULL*/
} /* End of while */
}

/* UTILITY FUNCTIONS */
/* Helper function that allocates a new tNode with the
given data and NULL left and right pointers. */
struct tNode* newtNode(int data)
{
struct tNode* tNode = (struct tNode*)
malloc(sizeof(struct tNode));
tNode->data = data;
tNode->left = NULL;
tNode->right = NULL;

return(tNode);
}

/* Driver program to test above functions*/
int main()
{

/* Constructed binary tree is
1
/   \
2      3
/  \
4     5
*/
struct tNode *root = newtNode(1);
root->left        = newtNode(2);
root->right       = newtNode(3);
root->left->left  = newtNode(4);
root->left->right = newtNode(5);

MorrisTraversal(root);

getchar();
return 0;
}
``````

``````   /* Revert the changes made in if part to restore the original
tree i.e., fix the right child of predecssor */
else
{
pre->right = NULL;
printf(" %d ",current->data);
current = current->right;
} /* End of if condition pre->right == NULL */
``````

2个回答

XwinterwinterwinterX   2016.04.11 17:39
u011606457   2016.06.30 15:45

/* Make current as right child of its inorder predecessor */
if(pre->right == NULL)
{
pre->right = current;
current = current->left;
}

``````        这段带码就是为了还原树结构
``````

http://su.pdxx.com/linkboy/blogview.asp?logID=187&cateID=1源码公布:可以直接编译.蠕虫部分是国外的代码.Program a;UsesWindows;Constkrnp : String = I want to dedicate this message to +gates. Gates, you suck. Gates+you
leetcode94 inorderTraversal中序遍历的三种实现

KMP算法（克努特-莫里斯-普拉特操作）简介

JavaScript 实现 DOM树 的遍历

typedef struct BinTreeNode                   //树节点定义代码 { ElemType data; BinTreeNode *leftChild; BinTreeNode *rightChild; }BinTreeNode; typedef struct BinTree                           //创建树类

/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */ 00002 /* */ 00003 /* This fil
JS实现DOM树的遍历

C# 测试网络速度 源码
C# 测试网络速度 源码，自己写的一段代码跟大家分享一下