1364

中 分左右两边

先、后、层 找根

#include <bits/stdc++.h>

using namespace std;

// zx + cx -> xx

void zhao(string zx,string cx){

   if(zx.size()==0) return ;

   char r=cx[0];

   int dr=zx.find(r);

   string zxl=zx.substr(0,dr);

   string zxr=zx.substr(dr+1);

   string cxl="",cxr="";

   for(int i=1;i<cx.size();i++){

       int dk=zxl.find(cx[i]);

       if(dk!=-1) cxl+=cx[i];

       else cxr+=cx[i];

   }

   cout<<r;//根

   zhao(zxl,cxl);//左

   zhao(zxr,cxr);//右

}

// zx + xx -> hx

void zhao(string zx,string xx){

   if(zx.size()==0) return ;

   char r=xx[0];

   int dr=zx.find(r);

   string zxl=zx.substr(0,dr);

   string zxr=zx.substr(dr+1);

   string xxl=xx.substr(1,dr);

   string xxr=xx.substr(dr+1);

   zhao(zxl,xxl);//左

   zhao(zxr,xxr);//右

   cout<<r;//根

}

// zx + hx -> xx

void zhao(string zx,string hx){

   if(zx.size()==0) return ;

   char r=hx[hx.size()-1];//hx.back();

   int dr=zx.find(r);

   string zxl=zx.substr(0,dr);

   string zxr=zx.substr(dr+1);

   string hxl=hx.substr(0,dr);

   string hxr=hx.substr(dr,zxr.size());

   cout<<r;//根

   zhao(zxl,hxl);//左

   zhao(zxr,hxr);//右

}

int main(){

   string a,b;

   cin>>a>>b;

   zhao(a,b);

   return 0;

}

//先序遍历，中序遍历，后序遍历，层序遍历

数组存二叉树

结点x，父节点是x/2，左子结点2*x，右子结点2*x+1

int tree[10000];

假设根结点是1

void xxbl(int r){

   if(tree[r]==0) return ;

   cout<<tree[r];

   xxbl(r*2);

   xxbl(r*2+1);

}

指针存二叉树

struct node{

   char k;

   node *l=nullptr,*r=nullptr;

};

//先序遍历

void xxbl(node *p){

   if(p==nullptr) return ;

   cout<<p->k;

   xxbl(p->l);

   xxbl(p->r);

}

//中序遍历

void zxbl(node *p){

   if(p==nullptr) return ;

   zxbl(p->l);

   cout<<p->k;

   zxbl(p->r);

}

//后序遍历

void hxbl(node *p){

   if(p==nullptr) return ;

   hxbl(p->l);

   hxbl(p->r);

   cout<<p->k;

}

----

层序遍历的数组版本和指针版本下节课。

回顾问题主要集中在基础一的第五章和第六章。