首页 > 数据结构 > 树形结构 > 不使用递归和栈中序遍历二叉树
2014
07-20

不使用递归和栈中序遍历二叉树

我们知道,在深度搜索遍历的过程中,之所以要用递归或者是用非递归的栈方式,参考二叉树非递归中序遍历,都是因为其他的方式没法记录当前节点的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;
}

参考:http://www.geeksforgeeks.org/inorder-tree-traversal-without-recursion-and-without-stack/

http://www.cnblogs.com/obama/p/3262054.html


  1. #include <cstdio>

    int main() {
    //answer must be odd
    int n, u, d;
    while(scanf("%d%d%d",&n,&u,&d)==3 && n>0) {
    if(n<=u) { puts("1"); continue; }
    n-=u; u-=d; n+=u-1; n/=u;
    n<<=1, ++n;
    printf("%dn",n);
    }
    return 0;
    }

  2. Excellent Web-site! I required to ask if I might webpages and use a component of the net web website and use a number of factors for just about any faculty process. Please notify me through email regardless of whether that would be excellent. Many thanks