|
数据类型，运算符，三大结构 数组，函数，递归，结构体 栈，队列，树 ---------树代码 数组存树：下标代表结点，值代表父节点 一本通：1336 数组存树：利用完全二叉树父子节点规律存树，如果不是完全二叉树，先补全或递归结构存树 指针存树：指针结构体：struct node{char c;node *l=nullptr,*r=nullptr;}; --------- 先序遍历，中序遍历，后序遍历，层序遍历 char tree[100000];//假设已经存好树了，1下标是根结点，空字符为不存在的节点 void xxbl(int i){ if(tree[i]==0) return ; cout<<tree[i]; xxbl(i*2); xxbl(i*2+1); } void zxbl(int i){ if(tree[i]==0) return ; zxbl(i*2); cout<<tree[i]; zxbl(i*2+1); } void hxbl(int i){ if(tree[i]==0) return ; hxbl(i*2); hxbl(i*2+1); cout<<tree[i]; } void cxbl(int i){ queue<int> q;//信息队列 q.push(i); while(!q.empty()){ int u=q.front(); if(tree[u*2]!=0) q.push(u*2); if(tree[u*2+1]!=0) q.push(u*2+1); cout<<tree[u]; q.pop(); } } struct node{ char c; node *l=nullptr,*r=nullptr; } *root=nullptr;//假设已经存好数据了 void xxbl(node *p){ if(p==nullptr) return ; cout<<p->c;//cout<<(*p).c; xxbl(p->l); xxbl(p->r); } void zxbl(node *p){} void hxbl(node *p){} void cxbl(node *p){ queue<node*> q; q.push(p); while(!q.empty()){ node *u=q.front(); if(u->l!=nullptr) q.push(u->l); if(u->r!=nullptr) q.push(u->r); cout<<u->c; q.pop(); } } --- 序列推导：中序负责分左右，先后层序负责找根 zx+xx->hx void zxgethx(string zx,string xx){ if(zx.size()==0) return ; char r=xx[0]; int d=zx.find(r); string zxl=zx.substr(0,d);//0起点，d代表长度 string zxr=zx.substr(d+1);//d+1起点，截取到最后 string xxl=xx.substr(1,d); string xxr=xx.substr(d+1); zxgethx(zxl,xxl);//左 zxgethx(zxr,xxr);//右 cout<<r;//根 } zx+hx->xx zx+cx->xx void zcgetxx(string zx,string cx){ if(zx.size()==0) return ; char r=cx[0];//找根 int d=zx.find(r); string zxl=zx.substr(0,d);//0起点，d代表长度 string zxr=zx.substr(d+1);//d+1起点，截取到最后 string cxl="",cxr=""; for(int i=1;i<cx.size();i++){ int k=zxl.find(cx[i]); if(k!=-1) cxl+=cx[i]; else cxr+=cx[i]; } cout<<r;//根 zcgetxx(zxl,cxl);//左 zcgetxx(zxr,cxr);//右 } 二叉搜索树 输入一行数据，构成二叉搜索树 int tree[10000];//根默认下标1 void insert1(int i,int num){//i下标，num值 if(tree[i]==0) tree[i]=num; else{ if(num<tree[i]) insert1(i*2,num); else insert1(i*2+1,num); } } struct node{ int c; node *l=nullptr,*r=nullptr; node(int a){ c=a; } } *root=nullptr;//假设已经存好数据了 void insert2(node *p,int num){ if(p==nullptr) p=new node(num); else{ if(p->c<num) insert2(p->r,num); else insert2(p->l,num); } } int main(){ int n; cin>>n;//7 for(int i=1;i<=n;i++){ cin>>a;//5 3 7 2 4 6 8 insert1(1,a); insert2(root,a); } } 堆：大顶堆，小顶堆 /* 完美的错误示范 int dui[10000];//根1 void insert(int i,int num){ if(dui[i/2]>num) {dui[i]=num;return ;} else{ dui[i/2]=b; swap(dui[i],dui[i/2]); insert(i/2,num); } } int main(){ int n; cin>>n;//7 for(int i=1;i<=n;i++){ cin>>a;//5 3 7 2 4 6 8 insert(1,a); } } */ 下节课：堆排序，哈夫曼树 作业： 1336，1339，1364等其他树结构练习题 安装虚拟机 代码补全： 1、指针树的zxbl 2、指针树的hxbl 3、zx+hx->xx 结构体操作 node a; a.c;//对象调用成员变量 node *p; p->c;//指针调用成员变量 (*p).c;//指针调用成员变量 背：字符串应用（函数） |