题解 | #二叉树遍历#

• 先序建立和先序遍历是类似的
• 空指针可以用nullptr

#include<iostream>
#include<string>
using namespace std;

struct node{//结点
  char data;
  node* leftchild;
  node* rightchild;
  node(char c):data(c),leftchild(nullptr),rightchild(nullptr){}
};


node* build(string s,int& pos){//根据先序序列建立二叉树（序列，当前字符位置）
  char c=s[pos++];//每调用一次，pos都要++
  if(c=='#'){
    return nullptr;
  }
  node* root=new node(c);
  root->leftchild=build(s,pos);
  root->rightchild=build(s,pos);
  return root;
}

void LNR(node* root){//中序访问
  if(root==nullptr)return;
  LNR(root->leftchild);
  printf("%c ",root->data);
  LNR(root->rightchild);
}

int main(){
  string s;
  while(cin>>s){
    int pos=0;
    node* root=build(s,pos);
    LNR(root);
    printf("\n");

  }
  
  return 0;
}