邯山专业做网站,总部在上海的世界500强企业,装修公司哪家好又便宜,一键开启网站模板通用#xff0c;递归思路 树的结构#xff1a;
struct node{int v;node* l;node* r;node(int u):v(u){}//构造函数
}//树的结构
int post[N],pre[N],in[N];//遍历的节点顺序
遍历顺序的性质
先序遍历#xff1a;根左右#xff0c;第一个节点为根节点#xff0c;根节…模板通用递归思路 树的结构
struct node{int v;node* l;node* r;node(int u):v(u){}//构造函数
}//树的结构
int post[N],pre[N],in[N];//遍历的节点顺序
遍历顺序的性质
先序遍历根左右第一个节点为根节点根节点后一个节点为左子树根节点
后序遍历左右根最后一个节点为根节点根节点前一个节点为右子树根节点
中序遍历左根右根节点的左边为左子树节点右边为右子树节点 先序(preorder)与中序(inorder)
先序遍历是根左右递归处理时从前往后推即可递归构造树时先构造左子树再构造右子树
int pos0;
node* create(int l,int r){//l,r为中序遍历的该子树边界if(lr)return new node(-1);node* nodnew(pre[pos]);//遍历根从前往后推int mid;//找到根节点在中序遍历中的位置以此划分左右子树for(midl;midr;mid){if(nod-vin[mid])break;}nod-lcreate(l,mid-1);//先创建左子树nod-rcreate(mid1,r);//后创建右子树return nod;
}
后序(postorder)与中序(inorder)
后序为左右根故从后往前推递归构造树时先构造右子树再构造左子树
int posn-1;
node* create(int l,int r){//l,r为中序遍历的边界if(lr)return new node(-1);node* nodnew node(post[pos--]);//遍历根后序遍历的最后一个节点往前推int mid;//找到根节点在中序遍历中的位置以此划分左右子树for(midl;midr;mid){if(nod-vin[mid])break;}nod-rcreate(mid1,r);//先创建右子树nod-lcreate(l,mid-1);//后创建左子树return nod;
}
先序(preorder)与后序(postorder)
当前树的根在先序遍历中为第一个节点即为pre[l1]在后序遍历中为最后一个节点即为post[r2] 左子树根为先序遍历的根的后一个节点即为pre[l11] 右子树根为后序遍历的根的前一个节点即为post[r2-1]
node* create(int l1,int r1,int l2,int r2){//当前遍历的树的边界if(l1r1||l2r2)return new node(-1);node* nodnew node(pre[l1]);//先序遍历的第一个节点即为根节点//当前树的根在先序遍历中为第一个节点即为pre[l1]在后序遍历中为最后一个节点即为post[r2]//左子树根为先序遍历的根的后一个节点即为pre[l11]//右子树根为后序遍历的根的前一个节点即为post[r2-1]int left1,right1,left1,right2;//左子树的边界//先序遍历//左边界l11left1l11;//右边界右子树根的前一个节点即为右边界for(right1l1;right1r1;right1){if(pre[right11]post[r2-1])break;}//后序遍历//左边界l2后序遍历为左右根第一个肯定是左子树的节点left2l2;//右边界左子树根for(right2l2;right2r2;right2){if(post[right2]pre[l11])break;}nod-lcreate(left1,right1,left2,right2);//构建左子树//右子树边界//先序遍历//左边界右子树根for(left1l1;left1r1;left1){if(pre[left1]post[r2-1])break;}//右边界r1right1r1;//后序遍历//左边界:左根的后一个节点for(left2l2;left2r2;left2){if(post[left2-1]pre[l1-1])break;}//右边界r2-1;right2r2-1;nod-rcreate(left1,right1,left2,right2);//构建右子树return nod;
}
