二叉树遍历

循环：利用叶子结点右指针为空的特点，给叶子结点设置其直接后继，输出完孩子结点后，再返回其直接后继；

void midPrint_m(TreeNode *root)  {      TreeNode *cur = root;      TreeNode *pre = NULL;      while(cur != NULL)      {          if(cur->left == NULL)          {//左孩子为空，则直接输出              cout<<cur->var<<" ";              cur = cur->right;          }          else          {              pre = cur->left;              while( pre->right != NULL && pre->right != cur )              {//找到cur的直接前驱                  pre = pre->right;              }              if(pre->right == NULL)              {//设置后继结点                  pre->right = cur;                  cur = cur->left;              }              else              {                  pre->right = NULL;//重新设置为空                  cout<<cur->var<<" ";                  cur = cur->right;              }          }      }  }    void prePrint_m(TreeNode *root)  {//基本同于中遍历      TreeNode *cur = root;      TreeNode *pre = NULL;      while(cur != NULL)      {          if(cur->left == NULL)          {              cout<<cur->var<<" ";              cur = cur->right;          }          else          {              pre = cur->left;              while( pre->right != NULL && pre->right != cur )              {                  pre = pre->right;              }              if(pre->right == NULL)              {                  pre->right = cur;                  cout<<cur->var<<" ";                  cur = cur->left;              }              else              {                  pre->right = NULL;                  cur = cur->right;              }          }      }  }  //this is the most difficult algorithm  void reverse_out(TreeNode *from,TreeNode *to)  {      //first reverse from->to      //reverse      TreeNode *cur = from;      TreeNode *post = cur->right;      while(cur != to)      {          TreeNode *tmp = post->right;          post->right = cur;          cur = post;          post = tmp;      }      //already reverse,output list      TreeNode *traversal = cur;      while( cur != from )      {          cout<<cur->var<<" ";          cur = cur->right;      }      cout<<cur->var<<" ";      //reverse original      cur = to;      post = cur->right;      while(cur != from)      {          TreeNode *tmp = post->right;          post->right = cur;          cur = post;          post = tmp;      }      //restore to's right      to->right = NULL;  }  void postPrint_m(TreeNode *root)  {      TreeNode *newroot = new TreeNode(0);      newroot->left = root;      newroot->right = NULL;      TreeNode *cur = newroot;      TreeNode *pre = NULL;      while(cur != NULL)      {          if(cur->left == NULL)          {              cur = cur->right;          }          else          {              pre = cur->left;              while(pre->right != NULL && pre->right != cur)              {                  pre = pre->right;              }              if(pre->right == NULL)              {                  pre->right = cur;                  cur = cur->left;              }              else              {                  pre->right = NULL;                  reverse_out(cur->left,pre);                  cur = cur->right;              }          }      }  } 

转载于:https://www.cnblogs.com/fchy822/p/8999665.html

相关资源：二叉树遍历的流程图(递归 非递归 前中后序)