算法9---二叉樹的遍歷不用棧和遞歸

二叉樹的遍歷不用棧和遞歸

轉自：ACM之家?http://www.acmerblog.com/inorder-tree-traversal-without-recursion-and-without-stack-5988.html

我們知道，在深度搜索遍歷的過程中，之所以要用遞歸或者是用非遞歸的棧方式，參考二叉樹非遞歸中序遍歷，都是因為其他的方式沒法記錄當前節點的parent,而如果在每個節點的結構里面加個parent 分量顯然是不現實的，那么Morris是怎么解決這一問題的呢？好吧，他用得很巧妙，實際上是用葉子節點的空指針來記錄當前節點的位置，然后一旦遍歷到了葉子節點，發現葉子節點的右指針指向的是當前節點，那么就認為以當前節點的左子樹已經遍歷完成。Morris 遍歷正是利用了線索二叉樹?的思想。

以inorder為例，初始化當前節點為root，它的遍歷規則如下：

- 如果當前節點為空，程序退出。

- 如果當前節點非空，

- 如果當前節點的左兒子為空，那么輸出當前節點，當前節點重置為當前節點的右兒子。

- 如果當前節點的左兒子非空，找到當前節點左子樹的最右葉子節點（此時最右節點的右兒子有兩種情況，一種是指向當前節點，一種是為空,你也許感到奇怪，右節點的右兒子怎么可能非空，注意，這里的最右葉子節點只帶的是原樹中的最右葉子節點。），若其最右葉子節點為空，令其指向當前節點，將當前節點重置為其左兒子，若其最右節點指向當前節點，輸出當前節點，將當前節點重置為當前節點的右兒子,并恢復樹結構，即將最右節點的右節點再次設置為NULL

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

struct tNode
{
   int data;
   struct tNode* left;
   struct tNode* right;
};

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
    {
      /* 找到current的前驅節點 */
      pre = current->left;
      while(pre->right != NULL && pre->right != current)
        pre = pre->right;

      /* 將current節點作為其前驅節點的右孩子 */
      if(pre->right == NULL)
      {
        pre->right = current;
        current = current->left;
      }

      /* 恢復樹的原有結構，更改right 指針 */   
      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 */
}

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);
}

/* 測試*/
int main()
{

  /* 構建樹結構如下：
            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);
   return 0;
}

?