[关闭]
@Archger 2016-07-10T15:06:58.000000Z 字数 6091 阅读 790

二叉树遍历&构建

ACM 二叉树

二叉树的遍历分为三类：前序遍历、中序遍历和后序遍历。

photo

（1）前序遍历

先访问根节点，再遍历左子树，最后遍历右子树；并且在遍历左右子树时，仍需先遍历左子树，然后访问根节点，最后遍历右子树。上图的前序遍历如下。
photo

（2）中序遍历

先遍历左子树、然后访问根节点，最后遍历右子树；并且在遍历左右子树的时候。仍然是先遍历左子树，然后访问根节点，最后遍历右子树。前图的中序遍历如下。

photo

（3）后序遍历

先遍历左子树，然后遍历右子树，最后访问根节点；同样，在遍历左右子树的时候同样要先遍历左子树，然后遍历右子树，最后访问根节点。前图后序遍历结果如下。

photo

（4）层序遍历

用BFS每一层的向下遍历。

代码实现

二叉树的构建、查找、删除

  1. #include<iostream>
  2. #include<string>
  3. #include<string.h>
  4. #include<algorithm>
  5. #include<iomanip>
  6. #include<cstdio>
  7. #include<queue>
  8. #include<stack> 
  9. using namespace std;
  11. struct node {
  12.     int val;
  13.     node *lch, *rch;
  14. };
  16. //插入数值
  17. node *insert(node *p, int x)
  18. {
  19.     if (p == NULL)
  20.     {
  21.         node *q = new node;
  22.         q->val = x;
  23.         q->lch = q->rch = NULL;
  24.         return q;
  25.     }
  26.     else
  27.     {
  28.         if (x < p->val) p->lch = insert(p->lch, x);
  29.         else p->rch = insert(p->rch, x);
  30.         return p;
  31.     }
  32. }
  34. //查找数值
  35. bool find(node *p, int x)
  36. {
  37.     if (p == NULL) return false;
  38.     else if (x == p->val) return true;
  39.     else if (x < p->val) return find(p->lch, x);
  40.     else return find(p->rch, x);
  41. }
  43. //删除数值
  44. node *remove(node *p, int x)
  45. {
  46.     if (p == NULL) return NULL;
  47.     else if (x < p->val) p->lch = remove(p->lch, x);
  48.     else if (x > p->val) p->rch = remove(p->rch, x);
  49.     else if (p->lch == NULL)
  50.     {
  51.         node *q = p->rch;
  52.         delete p;
  53.         return q;
  54.     }
  55.     else if (p->lch->rch == NULL)
  56.     {
  57.         node *q = p->lch;
  58.         q->rch = p->rch;
  59.         delete p;
  60.         return q;
  61.     }
  62.     else
  63.     {
  64.         node *q;
  65.         for (q = p->rch; q->rch->rch != NULL; q = q->rch);
  66.         node *r = q->rch;
  67.         q->rch = r->lch;
  68.         r->lch = p->lch;
  69.         r->rch = p->rch;
  70.         delete p;
  71.         return r;
  72.     }
  73.     return p;    //没有找到p点
  74. }
  76. int main()
  77. {
  78.     node *head = NULL;
  79.     int n;
  80.     cout << "1:  insert     2:  find     3:  remove\n";
  81.     while (cin >> n)
  82.     {
  83.         int x;
  84.         if (n == 1)
  85.         {
  86.             cin >> x;
  87.             head = insert(head, x);
  88.         }
  89.         else if (n == 2)
  90.         {
  91.             cin >> x;
  92.             if (find(head, x))
  93.             {
  94.                 cout << "Find it!\n";
  95.             }
  96.             else
  97.             {
  98.                 cout << "Not find!\n";
  99.             }
  100.         }
  101.         else
  102.         {
  103.             cin >> x;
  104.             head = remove(head, x);
  105.         }
  106.     }
  107. }

非递归遍历

先序遍历

  1. void PreOrder2(node *p)
  2. {
  3.     stack<node*> stack;
  4.     while (p || stack.size())
  5.     {
  6.         if (p)
  7.         {
  8.             stack.push(p);
  9.             cout << p->val<<" ";
  10.             p = p->lch;
  11.         }
  12.         else
  13.         {
  14.             p = stack.top();
  15.             stack.pop();
  16.             p = p->rch;
  17.         }
  18.     }
  19. }

中序遍历

  1. void InOrder2(node *p)
  2. {
  3.     stack<node*> stack;
  4.     while (p || stack.size())
  5.     {
  6.         if (p)
  7.         {
  8.             stack.push(p);
  9.             p = p->lch;
  10.         }
  11.         else
  12.         {
  13.             p = stack.top();
  14.             stack.pop();
  15.             cout << p->val << " ";
  16.             p = p->rch;
  17.         }
  18.     }
  19. }

后序遍历

  1. void PostOrder2(node *p)
  2. {
  3.     stack<node*> stack;
  4.     while (p || stack.size())
  5.     {
  6.         while (p)
  7.         {
  8.             p->left = 1;
  9.             p = p->lch;
  10.             stack.push(p);
  11.         }
  12.         while ((stack.top()->left) && (stack.top()->right) && stack.size())
  13.         {
  14.             p = stack.top();
  15.             stack.pop();
  16.             cout << p->val << " ";
  17.         }
  18.         if (stack.size())
  19.         {
  20.             p->right = 1;
  21.             p = p->rch;
  22.         }
  23.     }
  24. }

递归遍历

  1. void view(node *p)
  2. {
  3.     if (p)
  4.     {
  5.         cout << p->val << " ";
  6.     }
  7. }

先序遍历

  1. void PreOrder(node *p)
  2. {
  3.     if (p)
  4.     {
  5.         view(p);
  6.         PreOrder(p->lch);
  7.         PreOrder(p->rch);
  8.     }
  9. }

中序遍历

  1. void InOrder(node *p)
  2. {
  3.     if (p)
  4.     {
  5.         InOrder(p->lch);
  6.         view(p);
  7.         InOrder(p->rch);
  8.     }
  9. }

后序遍历

  1. void PostOrder(node *p)
  2. {
  3.     if (p)
  4.     {
  5.         PostOrder(p->lch);
  6.         PostOrder(p->rch);
  7.         view(p);
  8.     }
  9. }

层序遍历

  1. void LevelOrder(node *p)
  2. {
  3.     queue<node*> queue;
  4.     queue.push(p);
  5.     while (queue.size())
  6.     {
  7.         p = queue.front();
  8.         queue.pop();
  9.         cout << p->val << " ";
  10.         if (p->lch) queue.push(p->lch);
  11.         if (p->rch) queue.push(p->rch);
  12.     }
  13. }

整体代码测试

  1. #include<iostream>
  2. #include<string>
  3. #include<string.h>
  4. #include<algorithm>
  5. #include<iomanip>
  6. #include<cstdio>
  7. #include<queue>
  8. #include<stack> 
  9. using namespace std;
  11. struct node {
  12.     int val;
  13.     node *lch, *rch;
  14.     bool left, right;
  15. };
  17. //插入数值
  18. node *insert(node *p, int x)
  19. {
  20.     if (p == NULL)
  21.     {
  22.         node *q = new node;
  23.         q->val = x;
  24.         q->lch = q->rch = NULL;
  25.         return q;
  26.     }
  27.     else
  28.     {
  29.         if (x < p->val) p->lch = insert(p->lch, x);
  30.         else p->rch = insert(p->rch, x);
  31.         return p;
  32.     }
  33. }
  35. //查找数值
  36. bool find(node *p, int x)
  37. {
  38.     if (p == NULL) return false;
  39.     else if (x == p->val) return true;
  40.     else if (x < p->val) return find(p->lch, x);
  41.     else return find(p->rch, x);
  42. }
  44. //删除数值
  45. node *remove(node *p, int x)
  46. {
  47.     if (p == NULL) return NULL;
  48.     else if (x < p->val) p->lch = remove(p->lch, x);
  49.     else if (x > p->val) p->rch = remove(p->rch, x);
  50.     else if (p->lch == NULL)
  51.     {
  52.         node *q = p->rch;
  53.         delete p;
  54.         return q;
  55.     }
  56.     else if (p->lch->rch == NULL)
  57.     {
  58.         node *q = p->lch;
  59.         q->rch = p->rch;
  60.         delete p;
  61.         return q;
  62.     }
  63.     else
  64.     {
  65.         node *q;
  66.         for (q = p->rch; q->rch->rch != NULL; q = q->rch);
  67.         node *r = q->rch;
  68.         q->rch = r->lch;
  69.         r->lch = p->lch;
  70.         r->rch = p->rch;
  71.         delete p;
  72.         return r;
  73.     }
  74.     return p;    //没有找到p点
  75. }
  77. void view(node *p)
  78. {
  79.     if (p)
  80.     {
  81.         cout << p->val << " ";
  82.     }
  83. }
  85. void PreOrder(node *p)
  86. {
  87.     if (p)
  88.     {
  89.         view(p);
  90.         PreOrder(p->lch);
  91.         PreOrder(p->rch);
  92.     }
  93. }
  95. void InOrder(node *p)
  96. {
  97.     if (p)
  98.     {
  99.         InOrder(p->lch);
  100.         view(p);
  101.         InOrder(p->rch);
  102.     }
  103. }
  105. void PostOrder(node *p)
  106. {
  107.     if (p)
  108.     {
  109.         PostOrder(p->lch);
  110.         PostOrder(p->rch);
  111.         view(p);
  112.     }
  113. }
  115. void PreOrder2(node *p)
  116. {
  117.     stack<node*> stack;
  118.     while (p || stack.size())
  119.     {
  120.         if (p)
  121.         {
  122.             stack.push(p);
  123.             cout << p->val<<" ";
  124.             p = p->lch;
  125.         }
  126.         else
  127.         {
  128.             p = stack.top();
  129.             stack.pop();
  130.             p = p->rch;
  131.         }
  132.     }
  133. }
  135. void InOrder2(node *p)
  136. {
  137.     stack<node*> stack;
  138.     while (p || stack.size())
  139.     {
  140.         if (p)
  141.         {
  142.             stack.push(p);
  143.             p = p->lch;
  144.         }
  145.         else
  146.         {
  147.             p = stack.top();
  148.             stack.pop();
  149.             cout << p->val << " ";
  150.             p = p->rch;
  151.         }
  152.     }
  153. }
  155. void PostOrder2(node *p)
  156. {
  157.     stack<node*> stack;
  158.     while (p || stack.size())
  159.     {
  160.         while (p)
  161.         {
  162.             p->left = 1;
  163.             p = p->lch;
  164.             stack.push(p);
  165.         }
  166.         while ((stack.top()->left) && (stack.top()->right) && stack.size())
  167.         {
  168.             p = stack.top();
  169.             stack.pop();
  170.             cout << p->val << " ";
  171.         }
  172.         if (stack.size())
  173.         {
  174.             p->right = 1;
  175.             p = p->rch;
  176.         }
  177.     }
  178. }
  180. void LevelOrder(node *p)
  181. {
  182.     queue<node*> queue;
  183.     queue.push(p);
  184.     while (queue.size())
  185.     {
  186.         p = queue.front();
  187.         queue.pop();
  188.         cout << p->val << " ";
  189.         if (p->lch) queue.push(p->lch);
  190.         if (p->rch) queue.push(p->rch);
  191.     }
  192. }
  194. int main()
  195. {
  196.     node *head = NULL;
  197.     int n;
  198.     cout << "1:  insert     2:  find     3:  remove\n";
  199.     cout << "4:  PreOrder   5:  InOrder  6:  PostOrder\n";
  200.     cout << "7:  PreOrder2  8:  InOrder2 9:  PostOrder2\n";
  201.     cout << "10: LevelOrder\n";
  202.     while (cin >> n)
  203.     {
  204.         int x;
  205.         if (n == 1)
  206.         {
  207.             cin >> x;
  208.             head = insert(head, x);
  209.         }
  210.         else if (n == 2)
  211.         {
  212.             cin >> x;
  213.             if (find(head, x))
  214.             {
  215.                 cout << "Find it!\n";
  216.             }
  217.             else
  218.             {
  219.                 cout << "Not find!\n";
  220.             }
  221.         }
  222.         else if (n == 3)
  223.         {
  224.             cin >> x;
  225.             head = remove(head, x);
  226.         }
  227.         else if (n == 4)
  228.         {
  229.             PreOrder(head);
  230.             cout << endl;
  231.         }
  232.         else if (n == 5)
  233.         {
  234.             InOrder(head);
  235.             cout << endl;
  236.         }
  237.         else if (n == 6)
  238.         {
  239.             PostOrder(head);
  240.             cout << endl;
  241.         }
  242.         else if (n == 7)
  243.         {
  244.             PreOrder2(head);
  245.             cout << endl;
  246.         }
  247.         else if (n == 8)
  248.         {
  249.             InOrder2(head);
  250.             cout << endl;
  251.         }
  252.         else if (n == 9)
  253.         {
  254.             PostOrder(head);
  255.             cout << endl;
  256.         }
  257.         else if (n == 10)
  258.         {
  259.             LevelOrder(head);
  260.             cout << endl;
  261.         }
  262.     }
  263. }

其他详解

CSDN中关于二叉树遍历详解

练习

PAT 1020. Tree Traversals (25)
题解：

  1. #include<iostream>
  2. #include<string>
  3. #include<string.h>
  4. #include<algorithm>
  5. #include<iomanip>
  6. #include<cstdio>
  7. #include<queue>
  8. #include<stack> 
  9. using namespace std;
  11. struct node
  12. {
  13.     long long val;
  14.     node *lch, *rch;
  15. };
  17. node *head = NULL;
  18. long long n, post[31], in[31], num;
  19. bool book[31];
  21. node* solve(int x, int y, node* p)
  22. {
  23.     if (x > y||x==0||y==0) return NULL;
  24.     p = new node;
  25.     p->val = post[y];
  26.     p->lch = NULL;
  27.     p->rch = NULL;
  28.     int left = 0, right = 0, s = 0, t = 0, cur = 0;
  29.     for (int i = 1; i <= n; i++)
  30.     {
  31.         if (in[i] == post[y])
  32.         {
  33.             book[i] = 1;
  34.             s = i;
  35.             cur = i;
  36.             t = i;
  37.             break;
  38.         }
  39.     }
  40.     while (t - 1 >= 1 && !book[t - 1]) t--;
  41.     while (s + 1 <= n && !book[s + 1]) s++;
  42.     left = cur - t;
  43.     right = s - cur;
  44.     p->lch = solve(x, x + left - 1, p->lch);
  45.     p->rch = solve(y - right, y - 1, p->rch);
  46.     return p;
  47. }
  49. void LevelOrder(node *p)
  50. {
  51.     queue<node*> queue;
  52.     queue.push(p);
  53.     while (queue.size())
  54.     {
  55.         p = queue.front();
  56.         queue.pop();
  57.         cout << p->val;
  58.         num++;
  59.         if (num != n) cout << " ";
  60.         if (p->lch) queue.push(p->lch);
  61.         if (p->rch) queue.push(p->rch);
  62.     }
  63. }
  65. int main()
  66. {
  67.     while (cin >> n)
  68.     {
  69.         num = 0;
  70.         memset(book, 0, sizeof(book));
  71.         if (n <= 0) return 0;
  72.         for (int i = 1; i <= n; i++)
  73.         {
  74.             cin >> post[i];
  75.         }
  76.         for (int i = 1; i <= n; i++)
  77.         {
  78.             cin >> in[i];
  79.         }
  80.         head = solve(1, n, head);
  81.         LevelOrder(head);
  82.         cout << endl;
  83.     }
  84. }
添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注