2 xwinterwinterwinterx 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
XwinterwinterwinterX   2016.04.11 17:39
u011606457
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;
}

        这段带码就是为了还原树结构
Csdn user default icon
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!
其他相关推荐
莫里斯蠕虫
它的编写者是美国康乃尔大学一年级研究生罗特·莫里斯。这个程序只有99行,利用了Unix系统中的缺点,用Finger命令查联机用户名单,然后破译用户口令,用Mail系统复制、传播本身的源程序,再编译生成代码。最初的网络蠕虫设计目的是当网络空闲时,程序就在计算机间“游荡”而不带来任何损害。当有机器负荷过重时,该程序可以从空闲计算机“借取资源”而达到网络的负载平衡。而莫里斯蠕虫不是“借取资源”,而是“耗
蠕虫功能的下载者源代码
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中序遍历的三种实现
题目很简单二叉树的中序遍历,数据结构的教材上都会有这样的示例代码。其实中序遍历有三种解法: 递归解法(recursive solution) 栈迭代解法(iterative way(stack)) 莫里斯解法(morris traversal) 三种解法都是时间复杂度为O(n) 空间复杂度1和2为O(n),3为O(1)。
请教一段查询代码
我想请教一下vf的一段查询代码,当输入楼栋号时能查询出楼栋信息,并且显示在下方的表格中,我运行程序时一直提示不能识别的成员text1,我是在页框中写的程序,求帮助,谢谢!
KMP算法(克努特-莫里斯-普拉特操作)简介
一,串的模式匹配算法 子串的定位操作通常称作串的模式匹配(其中T称为模式串),是各种串处理系统中最重要的操作之一。求子串位置的定位函数Index(S,T,pos)。
JavaScript 实现 DOM树 的遍历
普通二叉树的遍历 function Tree() { var Node = function(key){ this.key = key; this.left = null; this.right = null; } root =null; } 前序遍历
数据结构关于树的一些递归函数代码
typedef struct BinTreeNode                   //树节点定义代码 { ElemType data; BinTreeNode *leftChild; BinTreeNode *rightChild; }BinTreeNode; typedef struct BinTree                           //创建树类
一段宏定义的代码
/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */ 00002 /* */ 00003 /* This fil
JS实现DOM树的遍历
二叉 DOM 树的遍历 [javascript] view plain copy function Tree() {                  var Node = function(key){               this.key = key;               this.left = null;        
C# 测试网络速度 源码
C# 测试网络速度 源码,自己写的一段代码跟大家分享一下