Chinaunix首页 | 论坛 | 博客
  • 博客访问: 498025
  • 博文数量: 80
  • 博客积分: 0
  • 博客等级: 民兵
  • 技术积分: 1916
  • 用 户 组: 普通用户
  • 注册时间: 2013-07-11 22:01
个人简介

从事实时计算多年,熟悉jstorm/spark/flink/kafka/rocketMq, 热衷于开源,希望在这里和前辈们一起学习与分享,得到长足的进步!邮箱:hustfxj@gmail.com 我的githup地址是:https://github.com/hustfxj。欢迎和大家一起交流探讨问题。

文章分类

全部博文(80)

文章存档

2017年(11)

2015年(3)

2014年(33)

2013年(33)

分类: C/C++

2014-03-17 16:55:22

给出一个非递归的中序树遍历算法。(提示:有两种方法,在较容易的方法中,可以采用栈作为辅助数据结构;在较为复杂的方法中,不采用栈结构,但假设可以测试两个指针是否相等。)

算法思想:

1.采用栈的话,先寻找最左边的节点,把经过的节点都存入栈中,第一个被弹出来的为最左节点,那么访问其右子树,对右子树也像前面一样遍历,整个流程跟递归一样。

2.不采用栈的话,先是访问最左节点,然后访问其右子树,然后回溯到最左节点的父节点,不断重复这个过程,思路还是一样。这里参考了重剑无锋的http://blog.csdn.net/kofsky/archive/2008/09/05/2886453.aspx

构造的树的树如下:


点击(此处)折叠或打开

  1. #include <iostream>
  2. #include <time.h>
  3. usingnamespace std;
  4. class Node
  5. {
  6. public:
  7.       int data;
  8.   Node* left;
  9.   Node* right;
  10.   Node* parent;
  11.       bool visited;
  12.       //Node(){}
  13.   Node(int d);
  14.   Node(int d, Node* l, Node* r);
  15. };
  16. class BinaryTree
  17. {
  18. public:
  19.   Node* root;
  20.   BinaryTree(Node* r);
  21.       //递归实现中序遍历
  22.   void recurse_in_order_visit(Node* root);
  23.       //非递归用栈实现中序遍历
  24.   void non_recurse_using_stack_in_order_visit(Node* root);
  25.       //非递归且不用栈实现中序遍历
  26.   void non_recurse_non_stack_in_order_visit(Node* root);
  27.       enum TRAVESAL_STATE
  28.   {
  29.     LEFT_NOT_TRAVERS,//左子树未遍历
  30.     LEFT_TRAVERSED,//左子树已遍历(包括左子树为空)
  31.     RIGHT_TRAVERSED//右子树已遍历(右子树为空)
  32.   };
  33. };
  34. int main()
  35. {
  36.   Node* node1 =new Node(1, NULL, NULL);
  37.   Node* node2 =new Node(2, node1, NULL);
  38.   Node* node3 =new Node(4, NULL, NULL);
  39.   Node* node4 =new Node(3, node2, node3);
  40.   Node* node5 =new Node(7, NULL, NULL);
  41.   Node* node6 =new Node(6, NULL, node5);
  42.   Node* node7 =new Node(9, NULL, NULL);
  43.   Node* node8 =new Node(8, node6, node7);
  44.   Node* root =new Node(5, node4, node8);
  45.   BinaryTree* binary_tree =new BinaryTree(root);
  46.   cout<<"递归中序遍历的结果:"<<endl;
  47.   binary_tree->recurse_in_order_visit(binary_tree->root);
  48.   cout<<endl;
  49.   cout<<"非递归用栈中序遍历的结果:"<<endl;
  50.   binary_tree->non_recurse_using_stack_in_order_visit(binary_tree->root);
  51.   cout<<endl;
  52.       //若使用非递归且不用栈来进行中序遍历,则需要parent指针作为辅助
  53.   node1->parent = node2;
  54.   node2->parent = node4;
  55.   node3->parent = node4;
  56.   node5->parent = node6;
  57.   node6->parent = node8;
  58.   node7->parent = node8;
  59.   node4->parent = root;
  60.   node8->parent = root;
  61.   cout<<"非递归且不用栈中序遍历的结果:"<<endl;
  62.   binary_tree->non_recurse_non_stack_in_order_visit(binary_tree->root);
  63.   cout<<endl;
  64.       return0;
  65. }

  66. Node::Node(int d)
  67. {
  68.   data = d;
  69.   parent = left = right = NULL;
  70.   visited =false;
  71. }

  72. Node::Node(int d, Node* l, Node* r)
  73. {
  74.   data = d;
  75.   left = l;
  76.   right = r;
  77.   parent = NULL;
  78.   visited =false;
  79. }

  80. BinaryTree::BinaryTree(Node* r)
  81. {
  82.   root = r;
  83. }

  84. //递归实现中序遍历
  85. void BinaryTree::recurse_in_order_visit(Node* root)
  86. {
  87.       if(root != NULL)
  88.   {
  89.     recurse_in_order_visit(root->left);
  90.     printf("%d\t", root->data);
  91.     recurse_in_order_visit(root->right);
  92.   }
  93. }

  94. //非递归用栈实现中序遍历
  95. void BinaryTree::non_recurse_using_stack_in_order_visit(Node* root)
  96. {
  97.   Node* stack[9];
  98.       int top =-1;
  99.       while(root != NULL || top >-1)
  100.   {
  101.             while(root != NULL)
  102.     {
  103.       stack[++top] = root;
  104.       root = root->left;
  105.     }
  106.             if(top >-1)
  107.     {
  108.       root = stack[top--];
  109.       printf("%d\t", root->data);
  110.       root = root->right;
  111.     }
  112.   }
  113. }

  114. //非递归且不用栈实现中序遍历
  115. void BinaryTree::non_recurse_non_stack_in_order_visit(Node* root)
  116. {
  117.       while ( root != NULL )
  118.   {
  119.             while ( root->left != NULL &&!root->left->visited )
  120.     {
  121.                   //一路向左
  122.       root = root->left;
  123.     }
  124.             if ( !root->visited )
  125.     {
  126.       cout<<root->data<<"\t";
  127.       root->visited=true;
  128.     }
  129.             if ( root->right != NULL &&!root->right->visited )
  130.     {
  131.                   //右子树
  132.       root = root->right;
  133.     }
  134.             else
  135.     {
  136.                   //回溯至parent节点
  137.       root = root->parent;
  138.     }
  139.   }
  140. }

阅读(1217) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~