[数据结构与算法]数据结构与算法-二叉树建立，前序，中序，后序（迭代+递归），层次遍历

• 条件：二叉树

• 题目：无

• 原理：无

• 代码：

  /**
  * mootable
   */
  #include <iostream>
  #include <iomanip>
  #include <algorithm>  //sort
  #include <map>
  #include <queue>
  #include <deque>  //双端队列，头可插，尾可插
  #include <string>
  #include <cstring>
  #include <stack>
  #include <cmath>
  #include <fstream>
  #include <ctime>
  #include <climits> //数值的限制范围
  //(double)clock() / CLOCKS_PER_SEC <= 0.95 限制0.95s跑完
  using namespace std;
  
  class Solver {
      //通用属性
  public:
      Solver() {
          //取消和c输出输入的同步，加快读取
          ios::sync_with_stdio(false);
          cin.tie(nullptr);
          cout.tie(nullptr);
      }
  
      //通用方法
  public:
      void SaveCpp(string name) const {
  
          fstream input;
          fstream output;
  
          input.open("moota.cpp", ios::in);
          const string file = name + ".cpp";
          output.open(file.c_str(), ios::out);
  
          char c = 'O';
          while (!input.eof()) {
              input.get(c);
              output << c;
          }
  
          input.close();
          output.close();
  
      }
  
  protected:
      //待实现方法
      virtual void BeginPlay() {
      };
  
      virtual void Playing() {
      };
  
      virtual void EndPlay() {
      };
  public:
      //外观模式
      void Play() {
          BeginPlay();
          Playing();
          EndPlay();
      }
  };
  
  class SpecialSolver : public Solver {
  public:
      typedef long long lld;
      static const lld MAX = static_cast<lld>(1e4);
      static const lld INF = static_cast<lld>(1e18);
  private: //实例属性
      struct Node {
          char value;
          Node* l;
          Node* r;
      } * head;
  
      void CreateBinaryTree(Node* & node) {
          char c;
          cin >> c;
          if (c != '#') {
              node = new Node;
              node->value = c;
              CreateBinaryTree(node->l);
              CreateBinaryTree(node->r);
          }
          else {
              node = nullptr;
          }
      }
  
      //先序递归版
      void PreOrderG(Node* head) {
          if (head != nullptr) {
              cout << head->value << " ";
              PreOrderG(head->l);
              PreOrderG(head->r);
          }
      }
  
      //中序递归版
      void InOrderG(Node* head) {
          if (head != nullptr) {
              InOrderG(head->l);
              cout << head->value << " ";
              InOrderG(head->r);
          }
      }
  
      //后序递归版
      void PostOrderG(Node* head) {
          if (head != nullptr) {
              PostOrderG(head->l);
              PostOrderG(head->r);
              cout << head->value << " ";
          }
      }
  
      //先序迭代版
      void PreOrderD(Node* node) {
          stack<Node*> s;
          while (!s.empty() || node != nullptr) {
              //当node!=nullptr时，一直push根节点和左节点，并输出值。
              //当node==nullptr时，路径上根节点和所有的左节点已经入栈。
              //然后node=stack[top]->r，得到左节点的右节点。
              //若node==nullptr，继续取堆栈的值。得到次左节点的右节点。
              //若node!=nullptr，输出右节点的值，把右节点当作根节点，回到一开始的操作，完成先序遍历。
              if (node != nullptr) {
                  //处理根节点
                  cout << node->value << " ";
                  s.push(node);
                  //处理左子树
                  node = node->l;
              }
              else {
              	//取出根节点
                  node = s.top();
                  s.pop();
                  //处理右子树
                  node = node->r;
              }
          }
      }
  
      //中序迭代版
      void InOrderD(Node* node) {
          stack<Node*> s;
          while (!s.empty() || node != nullptr) {
       
              if (node != nullptr) {
                  //处理根节点
                  s.push(node);
                  node = node->l;
              }
              else {
                  //取出根节点
                  node = s.top();
                  s.pop();
                  cout << node->value << " ";
                  //处理右子树
                  node = node->r;
              }
          }
      }
  
      //后序迭代版。
      //后序遍历的非递归算法是三种顺序中最复杂的，
      //原因在于，后序遍历是先访问左、右子树,再访问根节点，
      //而在非递归算法中，利用栈回退到根节点时，并不知道是从左子树回退到根节点，还是从右子树回退到根节点，
      //如果从左子树回退到根节点，此时就应该去访问右子树，
      //如果从右子树回退到根节点，此时就应该访问根节点。
      //所以相比前序和中序，必须得在压栈时添加信息，
      //以便在退栈时可以知道是从左子树返回，还是从右子树返回进而决定下一步的操作。
      void PostOrderD(Node* node) {
          struct NodeWithTag {
              Node* node;
              bool tag; //true-右节点被访问 false-右节点未被访问
  
          };
          stack<NodeWithTag> s;
          s.push(NodeWithTag{node, false});
          while (!s.empty()) {
              //根节点
              NodeWithTag nodeWithTag = s.top();
              s.pop();
              //退回时访问右子树
              if (nodeWithTag.tag == false) {
                  if (nodeWithTag.node != nullptr) {
                      s.push(NodeWithTag{nodeWithTag.node, true});
                      s.push(NodeWithTag{nodeWithTag.node->r, false});
                      s.push(NodeWithTag{nodeWithTag.node->l, false});
                  }
              }
                  //退回时访问根节点
              else {
                  cout << nodeWithTag.node->value << " ";
              }
          }
      }
  
      //层次遍历
      void CellOrder(Node* node) {
          queue<Node*> q;
          q.push(node);
          while (!q.empty()) {
              Node* node = q.front();
              q.pop();
              cout << node->value << " ";
              if (node->l != nullptr)q.push(node->l);
              if (node->r != nullptr)q.push(node->r);
          }
      }
  
  private: //实例方法
  
  protected:
      virtual void BeginPlay() override {
          Solver::BeginPlay();
          CreateBinaryTree(head);
      };
  
      virtual void Playing() override {
          Solver::Playing();
          //ABC##DE#G##F###
          cout << "\n先序递归：";
          PreOrderG(head);
          cout << "\n先序迭代：";
          PreOrderD(head);
          cout << "\n中序递归：";
          InOrderG(head);
          cout << "\n中序迭代：";
          InOrderD(head);
          cout << "\n后序递归：";
          PostOrderG(head);
          cout << "\n后序迭代：";
          PostOrderD(head);
          cout << "\n层次遍历：";
          CellOrder(head);
      };
  
      virtual void EndPlay() override {
          Solver::EndPlay();
      };
  };
  
  SpecialSolver specialSolver;
  
  int main() {
      //注意改名字
      //specialSolver.SaveCpp("二叉树");
      specialSolver.Play();
  }