思考

如何根据递归函数写出相应的迭代函数？

遍历类型

  1. struct node {
  2.     int value;
  3.   Node *left;
  4.   Node *right;
  5. };

前序遍历

递归实现

  1. void preorder_rec(BinaryTree *root) {
  2.     if (!root) {
  3.         return;
  4.     }
  6.     printf("%d\t", root->value);
  7.     // handler(root->value);
  9.     preorder_rec(root->left);
  10.     preorder_rec(root->right);
  11. }

非递归

  1. void preorder(BinaryTree *root) {
  2.     if (!root) {
  3.         return;
  4.     }
  6.     stack<int> st;
  7.     st.push(root);
  9.     while(!st.empty()) {
  10.         Node *temp = st.top();
  11.         st.pop();
  13.         printf("%d\t", temp->value);
  15.         if (temp->right) {
  16.             st.push(temp->right);
  17.         }
  19.         if (temp->left) {
  20.             st.push(temp->left);
  21.         }
  22.     }
  23. }

中序遍历

递归实现

  1. void inorder_rec(BinaryTree *root) {
  2.     if (!root) {
  3.         return;
  4.     }
  6.     printf("%d\t", root->value);
  7.     // handler(root->value);
  9.     inorder_rec(root->left);
  10.     inorder_rec(root->right);
  11. }

非递归

后序遍历

递归实现

非递归

层序遍历

递归实现

非递归

总结

递归模板

核心：处理节点函数放在何处

  1. void order_rec(BinaryTree *root) {
  2.     if (!root) {
  3.         return;
  4.     }
  6.     order_rec(root->left);
  7.     order_rec(root->right);
  9.     printf("%d\t", root->value);
  10.     // handler(root->value);
  11. }

非递归模板

合理利用栈或队列实现