算法竞赛专题解析│搜索基础( 三 ) ：算法竞赛专题解析│搜索基

}
intdfn[maxn]={0};//dfn[i]是节点i的时间戳
intdfn_timer=0;
voiddfn_order(intfather){
if(father!=-1){
dfn[father]=++dfn_timer;
printf("dfn[%c]=%d;",node[father].value,dfn[father]);
//打印访问节点的时间戳
dfn_order(node[father].lchild);
dfn_order(node[father].rchild);
}
}
intvisit_timer=0;
voidvisit_order(intfather){//打印DFS序
if(father!=-1){
printf("visit[%c]=%d;",node[father].value,++visit_timer);
//打印DFS序：第1次访问节点
visit_order(node[father].lchild);
visit_order(node[father].rchild);
printf("visit[%c]=%d;",node[father].value,++visit_timer);
//打印DFS序：第2次回溯
}
}
intdeep[maxn]={0};//deep[i]是节点i的深度
intdeep_timer=0;
voiddeep_node(intfather){
if(father!=-1){
deep[father]=++deep_timer;
printf("deep[%c]=%d;",node[father].value,deep[father]);
//打印树的深度，第一次访问时，深度+1
deep_node(node[father].lchild);
deep_node(node[father].rchild);
deep_timer--;//回溯时，深度-1
}
}
intnum[maxn]={0};//num[i]是以i为父亲的子树上的节点总数
intnum_node(intfather){
if(father==-1)return0;
else{
num[father]=num_node(node[father].lchild)+
num_node(node[father].rchild)+1;
printf("num[%c]=%d;",node[father].value,num[father]);//打印数量
returnnum[father];
}
}
voidpreorder(intfather){//求先序序列
if(father!=-1){
cout<<node[father].value<<"";//先序输出
preorder(node[father].lchild);
preorder(node[father].rchild);
}
}
voidinorder(intfather){//求中序序列
if(father!=-1){
inorder(node[father].lchild);;
cout<<node[father].value<<"";//中序输出
inorder(node[father].rchild);
}
}
voidpostorder(intfather){//求后序序列
if(father!=-1){
postorder(node[father].lchild);;
postorder(node[father].rchild);
cout<<node[father].value<<"";//后序输出
}
}
intbuildtree{//建一棵树
intA=newNode('A');intB=newNode('B');intC=newNode('C');
intD=newNode('D');intE=newNode('E');intF=newNode('F');
intG=newNode('G');intH=newNode('H');intI=newNode('I');
insert(E,B,0);insert(E,G,1);//E的左孩子是B ，右孩子是G
insert(B,A,0);insert(B,D,1);
insert(G,F,0);insert(G,I,1);
insert(D,C,0);insert(I,H,0);
introot=E;
returnroot;
}
intmain{
introot=buildtree;
cout<<"dfnorder:";dfn_order(root);cout<<endl;//打印时间戳
cout<<"visitorder:";visit_order(root);cout<<endl;//打印DFS序
cout<<"deeporder:";deep_node(root);cout<<endl;//打印节点深度
cout<<"numoftree:";num_node(root);cout<<endl;//打印子树上的节点数
cout<<"inorder:";inorder(root);cout<<endl;//打印中序序列
cout<<"preorder:";preorder(root);cout<<endl;//打印先序序列
cout<<"postorder:";postorder(root);cout<<endl;//打印后序序列
return0;
}
/*输出是：
dfnorder:dfn[E]=1;dfn[B]=2;dfn[A]=3;dfn[D]=4;dfn[C]=5;dfn[G]=6;dfn[F]=7;dfn[I]=8;dfn[H]=9;
visitorder:visit[E]=1;visit[B]=2;visit[A]=3;visit[A]=4;visit[D]=5;visit[C]=6;visit[C]=7;visit[D]=8;visit[B]=9;visit[G]=10;visit[F]=11;visit[F]=12;visit[I]=13;visit[H]=14;visit[H]=15;visit[I]=16;visit[G]=17;visit[E]=18;
deeporder:deep[E]=1;deep[B]=2;deep[A]=3;deep[D]=3;deep[C]=4;deep[G]=2;deep[F]=3;deep[I]=3;deep[H]=4;
numoftree:num[A]=1;num[C]=1;num[D]=2;num[B]=4;num[F]=1;num[H]=1;num[I]=2;num[G]=4;num[E]=9;
inorder:ABCDEFGHI
preorder:EBADCGFIH
postorder:ACDBFHIGE
*/
DFS（指针版二叉树）
#include<bits/stdc++.h>
usingnamespacestd;
structnode{
charvalue;
node*l,*r;
node(charvalue='https://pcff.toutiao.jxnews.com.cn/p/20210226/#',node*l=NULL,node*r=NULL):value(value),l(l),r(r){}
};
voidpreorder(node*root){//求先序序列
if(root!=NULL){
cout<<root->value<<"";//先序输出
preorder(root->l);
preorder(root->r);
}
}
voidinorder(node*root){//求中序序列
if(root!=NULL){
inorder(root->l);
cout<<root->value<<"";//中序输出
inorder(root->r);
}
}
voidpostorder(node*root){//求后序序列
if(root!=NULL){
postorder(root->l);
postorder(root->r);
cout<<root->value<<"";//后序输出
}
}
voidremove_tree(node*root){//释放空间
if(root==NULL)return;
remove_tree(root->l);
remove_tree(root->r);
deleteroot;
}
intmain{
node*A,*B,*C,*D,*E,*F,*G,*H,*I;
A=newnode('A');B=newnode('B');C=newnode('C');
D=newnode('D');E=newnode('E');F=newnode('F');
G=newnode('G');H=newnode('H');I=newnode('I');
E->l=B;E->r=G;B->l=A;B->r=D;
G->l=F;G->r=I;D->l=C;I->l=H;