Chinaunix首页 | 论坛 | 博客
  • 博客访问: 135359
  • 博文数量: 25
  • 博客积分: 588
  • 博客等级: 中士
  • 技术积分: 292
  • 用 户 组: 普通用户
  • 注册时间: 2011-01-10 18:18
文章分类

全部博文(25)

文章存档

2012年(7)

2011年(18)

我的朋友

分类: C/C++

2011-06-02 16:33:22

  1. #include <iostream>
  2. #include <stack>
  3. #include <deque>

  4. using namespace std;


  5. int my_2_power(int b)
  6. {
  7.     int ret = 2;
  8.     for (int i=1; i<b; i++) {
  9.         ret <<= 2;
  10.     }
  11.     return ret;
  12. }

  13. typedef struct tree_
  14. {
  15.     int data;
  16.     struct tree_ *left;
  17.     struct tree_ *right;
  18. }tree;

  19. void visitNode(tree *node)
  20. {
  21.     if (node != NULL ) {
  22.         cout<<node->data<<" " ;
  23.     }
  24. }
  25. tree *insert(tree *root, int data)
  26. {
  27.     tree *p = new tree;
  28.     p->data = data;
  29.     p->left = p->right = NULL;
  30.     tree *tmp = root;
  31.     if (tmp == NULL) {
  32.         root = p;
  33.     } else {
  34.         tree *q;
  35.         while (tmp != NULL) {
  36.             q = tmp;
  37.             if (data > tmp->data) {
  38.                 tmp = tmp->right;
  39.             } else {
  40.                 tmp = tmp->left;
  41.             }
  42.         }
  43.         if ( data > q->data) {
  44.             q->right = p;
  45.         } else {
  46.             q->left = p;
  47.         }
  48.     }
  49.     return root;
  50. }

  51. void preorder(tree *root)
  52. {
  53.     stack<tree *> s;
  54.     while ( root || !s.empty() ) {
  55.         if (root) {
  56.             visitNode(root);
  57.             s.push(root);
  58.             root = root->left;
  59.         } else {
  60.             root = s.top();
  61.             s.pop();
  62.             root = root->right;
  63.         }
  64.     }
  65. }

  66. void inorder(tree *root)
  67. {
  68.     stack<tree *> s;
  69.     while (root || !s.empty()) {
  70.         if (root) {
  71.             s.push(root);
  72.             root = root->left;
  73.         } else {
  74.             root = s.top();
  75.             s.pop();
  76.             visitNode(root);
  77.             root = root->right;
  78.         }
  79.     }
  80. }

  81. void postorder(tree *root)
  82. {
  83.     stack<tree *> s;
  84.     tree *pre = NULL;
  85.     while (root || !s.empty()) {
  86.         if (root) {
  87.             s.push(root);
  88.             root = root->left;
  89.         } else {
  90.             root = s.top();
  91.             if (root->right && root->right != pre) {
  92.                 root = root->right;
  93.             } else {
  94.                 visitNode(root);
  95.                 pre = root;
  96.                 s.pop();
  97.                 root = NULL;
  98.             }
  99.         }
  100.     }
  101. }

  102. void levelorder(tree *root)
  103. {
  104.     deque<tree*> now;
  105.     now.push_back(root);
  106.     while (!now.empty()) {
  107.         root = now.front();
  108.         visitNode(root);
  109.         now.pop_front();
  110.         if (root->left) now.push_back(root->left);
  111.         if (root->right) now.push_back(root->right);
  112.     }
  113. }

  114. void serialize(int *a, tree *root)
  115. {
  116.     stack< pair<tree*,int> > s;
  117.     int i = 0;
  118.     while (root || !s.empty() ) {
  119.         if (root) {
  120.             a[i] = root->data;
  121.             s.push(make_pair<tree*,int>(root,i));
  122.             root = root->left;
  123.             i = 2*i + 1;
  124.         } else {
  125.             root = s.top().first;
  126.             i = s.top().second;
  127.             s.pop();
  128.             root = root->right;
  129.             i = 2*i+2;
  130.         }
  131.     }
  132. }
  133. tree *unserialize(int *a, int n)
  134. {
  135.     tree *root = NULL;
  136.     tree *ret = NULL;
  137.     tree *tmp;
  138.     int i=0;
  139.     stack< pair<tree*, int> > s;
  140.     
  141.     ret = root = new tree;
  142.     ret->data = root->data = a[i];
  143.     s.push(make_pair(root,i));

  144.     while ( (root && i<n && a[i] > 0) || !s.empty()) {
  145.          if (root && i < n && a[i] > 0 ) {
  146.              i = 2*i + 1;
  147.              if (i >=n || a[i] <=0 ) {
  148.                  continue;
  149.              }
  150.              tmp = new tree;
  151.              tmp->data = a[i];
  152.              tmp->left = tmp->right = NULL;
  153.              s.push(make_pair(tmp,i));
  154.              root->left = tmp;
  155.              root = tmp;
  156.          } else {
  157.              root = s.top().first;
  158.              i = s.top().second;
  159.              s.pop();
  160.              i = 2*i+2;
  161.              if (i<n && a[i] > 0) {
  162.                  tmp = new tree;
  163.                  tmp->left= tmp->right = NULL;
  164.                  tmp->data = a[i];
  165.                  root->right = tmp;
  166.                  root = tmp;
  167.                  s.push(make_pair(tmp,i));
  168.              }
  169.              else {
  170.                  root = NULL;
  171.              }
  172.          }
  173.     }
  174.     return ret;
  175. }

  176. int main(int argc, char **argv)
  177. {

  178.     tree *root = NULL;
  179.     int n;
  180.     cout<<"input tree's nodes: ";
  181.     cin>>n;
  182.     cout<<"input nodes data value: ";
  183.     int tmp;
  184.     for (int i=0; i<n; i++) {
  185.         cin>>tmp;
  186.         cout<<tmp<<" ";
  187.         root = insert(root, tmp);
  188.     }
  189.     cout<<endl;
  190.     cout<<"preorder: ";
  191.     preorder(root);
  192.     cout<<endl<<"inorder: ";
  193.     inorder(root);
  194.     cout<<endl<<"postorder: ";
  195.     postorder(root);
  196.     cout<<endl<<"levelorder: ";
  197.     levelorder(root);


  198.     cout<<endl<<"================== serialize =====================\n";
  199.     int size = my_2_power(n);
  200.     int *a = new int[size];
  201.     memset(a, 0, sizeof(int)*size);
  202.     serialize(a,root);
  203.     /*
  204.     for (int i=0; i<size; i++) {
  205.         cout<<a[i]<<" ";
  206.     }
  207.     */
  208.     root = unserialize(a, size);
  209.     cout<<endl;
  210.     cout<<"preorder: ";
  211.     preorder(root);
  212.     cout<<endl<<"inorder: ";
  213.     inorder(root);
  214.     cout<<endl<<"postorder: ";
  215.     postorder(root);
  216.     cout<<endl<<"levelorder: ";
  217.     levelorder(root);
  218.     cout<<endl;
  219.     return 0;
  220. }
阅读(5368) | 评论(2) | 转发(0) |
0

上一篇:堆排序

下一篇:背包问题动态规划

给主人留下些什么吧!~~

hnney2011-11-23 09:45:27

liqingfang: serialize函数中的 root = s.top().first;
            i = s.top().second;
first和second是啥意思?.....
你先理解一下这个(pair<tree*,int>)吧!

liqingfang2011-07-07 12:33:18

serialize函数中的 root = s.top().first;
            i = s.top().second;
first和second是啥意思?