newoodfhb
2021-05-20 20:36:09
摸了这么久，二叉树学废归来。
树是数据结构中的重中之重，尤其以各类二叉树为学习的难点，树形结构是一种一对多的数据结构，而二叉树是一种每个结点最多只有两个子树作为后继的树形结构，也就是一对二的结构，特殊性在于其每个结点左右子树对数据的区分。
class Tree{
int data;
Tree left;
Tree right;
//略（写不出）
}普通一对二结构，无其他要求，见图：
普通二叉树的基础上，除了最后一层不需要填满外，其他层都被填满。（平衡树要达到的结果）如图：
每一层结点皆被填满。如图：
同样数据的二叉树可以有多种情况，完全二叉树是二叉树的理想情况，斜树是最坏情况，满二叉树和完全二叉树是前推后的关系。二叉树如若不用好左右子树，变成斜树数据分布倾向一边，便失去了其结构区分数据的特性，与单链表一般无二；如若能将其特性正确用上，变成完全二叉树操作数据效率将大大提高。
以下为此树遍历为例
遍历的代码因为我未真正实现二叉树，有些许错误，但逻辑无误，所以请各位当作伪代码来看。
public static void pre(Tree node){
if(node==null)
return;
System.out.println(node.data);
pre(node.left);
pre(node.right);
}输出：52148769
public static void pre(Tree node){
if(node==null)
return;
pre(node.left);
System.out.println(node.data);
pre(node.right);
}输出：12456789
public static void pre(Tree node){
if(node==null)
return;
pre(node.left);
pre(node.right);
System.out.println(node.data);
}输出：1267985
前中后序遍历无非访问结点时机不同，前序遍历即访问；后序遍历至叶子结点在回溯时访问；中序遍历完左边访问左边，遍历完右边访问右边，左右分明，也因此能通过前序或后序与中序的结合推出二叉树来。
此题考查中序同后序和先序的关系。通过后序的最后一个结点可以得到每个子树的根结点，继而从中序中找到根结点并将序列分为左右子树，不断重复。
这里使用了StringBuilder类，因为其中有一个方法可以寻找某个字符串位置，String没有，而且StringBuilder处理字符串是最快的，必学必精。
因为是后序的关系，最后一个便是根结点，直接找到在中序中的位置，借此分出左右子树，再根据这两个子树的长度将后序也分离出左右子树，对应中序的左右子树，再进行不断的分割，直到无法分割为止。
如题中：
中序遍历：BADC
后序遍历：BDCA
第一轮分割：后序中最后一结点A即为根节点，在中序中找到A的位置为1(从零数),据此分成左子树：B，右子树：DC，又再根据这两个子树长度将后序分成左子树：B，右子树：DC，这样就分出了左右子树的中序和后序遍历，后面依此分割即可。
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
StringBuilder mid = new StringBuilder(sc.next());//中序
StringBuilder after = new StringBuilder(sc.next());//后序
itra(mid,after);
}
private static void itra(StringBuilder mid, StringBuilder after) {
// TODO Auto-generated method stub
if(mid.length()==0||after.length()==0)//分完停止
{
return;
}
char a = after.charAt(after.length()-1);//获得后序最后一个结点作为根节点
System.out.print(a);//因为前序遍历即访问，遇到根节点就输出，输出a
int add=mid.indexOf(a+"");//在中序中找到分割位置
pre.deleteCharAt(after.length()-1);//删除后序最后一个结点
StringBuilder left = new StringBuilder(mid.substring(0,add)) ;//获取中序左子树
StringBuilder right = new StringBuilder(mid.substring(add+1));//获取中序右子树
StringBuilder lafter = new StringBuilder(after.substring(0,add));//获取后序左子树
StringBuilder rafter = new StringBuilder(after.substring(add));//获取后序右子树
itra(left,lafter);//分割左子树
itra(right,rafter);//分割右子树
}
}
public static void lift(Tree node){
if(node==null)
return;
Queue<Tree> qu = new LinkedList<>();
qu.add(node);
while(!qu.isEmpty())
{
po = qu.poll();
System.out.println(po.data);
if(po.left!=null)
qu.add(po.left);
if(po.right!=null)
qu.add(po.right);
}
}输出：5281479
层序遍历属于BFS思想，在二叉树中遍历只是结点数量的不同，在平面地图上遍历是向四周扩散，在二叉树上是向子树上一层一层扩散。BFS通常需要队列来进行，用的方法不多，增删改查要会，出队方法为poll()，返回第一个进入队列的结点。
为了提交结果规范，定义了两个队列，好分清每一层，qu队列用来遍历，pos队列存储一层的结点。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> result = new LinkedList<>();
Queue<TreeNode> qu = new LinkedList<>();
Queue<TreeNode> pos = new LinkedList<>();
if(root==null)
return result;
pos.add(root);
while(!pos.isEmpty())
{
List<Integer> li = new LinkedList<>();
while(!pos.isEmpty())
{
TreeNode po = pos.poll();
qu.add(po);
li.add(po.val);
}
result.add(li);
while(!qu.isEmpty())//层序遍历
{
TreeNode po = qu.poll();//出队操作在此，记牢
if(po.left!=null)
pos.offer(po.left);
if(po.right!=null)
pos.offer(po.right);
}
}
return result;
}
}线段树是一种能对数据的区间进行操作的二叉树结构，线段树形成的树一定是完全二叉树，凭此能发挥出二叉树的高效查找优势，从而对数据进行修改。线段树通过数组存储，取左右子树方式为对当前结点编号乘上2得到左子树编号，乘上2加1得到右子树编号。可以先实现一次，以便了解线段树的结构。
class Tree{
int data;
int lazy; //若干懒标记，后面提到
}
Tree[] t = new Tree[n+1]; //建立一个区间为[1,n]线段树
int[] data = new int[m]; //用来建立线段树的m个数据
public static int getLeft(int node) //获取左结点编号
{
return node<<1;
}
public static int getRight(int node) //获取右结点编号
{
return node<<1|1;
}
public static void build(int left,int right,node){
if(left==right) //单元素区间，即[x,x]这样的区间，其他区间数值依赖于此种区间的值，此种区间在线段树中作为叶子结点。
{
t[node].data = data[left];
return;
}
int mid = left+right>>1;
build(left,mid,getLeft(node));
build(mid+1,right,getRight(node)); //此处对数组结点跳跃式遍历让区间获取结点
t[node].data = t[getLeft(node)].data + t[getRight(node)].data //对区间进行操作，此处并非一定要求和操作，也可以进行其他操作
}
我们在每次修改指定区间的数据的时候，往往会对数据从指定区间修改到单元素区间，一次修改到底，一次修改还好说，数据规模大了效率就慢了。为了简化区间修改过程，懒标记出现了。
懒标记用来存储区间即将要进行的操作数据，如若此区间被指定要修改了，会先在此区间记录下要操作的数据，多次指定，多次存储，待用到此区间时一次性操作完，由于各区间的包含关系，需要当前区间操作完的同时将操作数据传给下一个要修改的子区间。
如[1,3]，[1,2]，[3,3]。[1,3]指定要加上3，此时区间[1,3]的懒标记便存上3，如国再加上4，便存上3+4，等用到区间[1,3]便将此区间一次性加上3+4，加完了后，便将操作数据传给子区间[1,2]，[3,3]，即懒标记为3+4。
package luoguTree;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;
public class P3372LineTree {
static StreamTokenizer sc = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
public static long getLong()
{
try {
sc.nextToken();
} catch (Exception e) {
// TODO: handle exception
}
return (long)sc.nval;
}
public static int getInt()
{
try {
sc.nextToken();
} catch (Exception e) {
// TODO: handle exception
}
return (int)sc.nval;
}
static long[] t; //线段树各区间数据
static long[] v; //创建树用的数据
static long[] la; //懒标记用
public static void main(String[] args) {
int n = getInt();
int m = getInt();
v = new long[n+2];
for(int i=1;i<=n;i++)
{
v[i] = getLong();
}
la = new long[n*4+1];
t = new long[n*4+1];
build(1,n,1);
for(int i=0;i<m;i++)
{
int op = getInt();
if(op==1)
{
int x = getInt();
int y = getInt();
long k = getLong();
updata(x,y,k,1,n,1); //从区间[1,n]，结点1开始查找
}
else
{
int x = getInt();
int y = getInt();
System.out.println(sum(x,y,1,n,1));
}
}
}
//创建线段树
private static void build(int l, int r, int node) {
// TODO Auto-generated method stub
if(l==r)
{
t[node] = v[l];
return;
}
int mid = l+r>>1;
build(l, mid, node<<1);
build(mid+1,r,node<<1|1);
t[node] = t[node<<1]+t[node<<1|1];
}
//获取区间和
private static long sum(int x, int y,int l,int r,int node) {
// TODO Auto-generated method stub
if(x<=l&&y>=r) //被指定区间包含便返回其区间和，不需要遍历到底
return t[node];
lab(node,l,r); //进行一次求和并下传操作
int mid = l+r>>1;
long ans=0;
if(x<=mid) //获取左区间和
{
ans+=sum(x,y,l,mid,node<<1);
}
if(y>mid) //获取右区间和
{
ans+=sum(x,y,mid+1,r,node<<1|1);
}
return ans;
}
//更新结点信息
private static void updata(int x, int y, long k,int l,int r,int node) {
// TODO Auto-generated method stub
if(l>=x&&r<=y) //找到被指定区间包含的区间便可标记后退出
{
t[node] += k*(r-l+1);
la[node] += k;
return;
}
int mid = l+r>>1;
lab(node,l,r);//由于在未查到指定区间前，指定区间并未有之前的懒标记，所以要对不断进行求和并下传至指定区间包含的区间，否则会丢失上方的标记。
//以下是查找指定区间
if(x<=mid)
{
updata(x,y,k,l,mid,node<<1);
}
if(y>mid)
{
updata(x,y,k,mid+1,r,node<<1|1);
}
t[node] = t[node<<1]+t[node<<1|1];
}
private static void lab(int node,int l,int r) {
// TODO Auto-generated method stub
if(la[node]==0)
return;
int rr = node<<1|1;
int ll = node<<1;
int mid = l+r>>1;
la[rr] += la[node];
la[ll] += la[node]; //下传标记
t[rr] += la[node]*(r-(mid+1)+1);
t[ll] += la[node]*(mid-l+1); //子区间求和
la[node] = 0; //当前区间求和操作完了要将懒标记归零
}
}
此题并没有用类实现线段树（当时做的时候不熟悉），不过各方面操作一样。不过此处懒标记操作是为子区间进行求和并标记，即先找到区间后对子区间进行操作，这是因为传至单元素区间后，便不需要再传了，这样操作便能避免标记再往外处传，能刚好传至单元素区间。
static class Tree{
long v;
long lax,laa;//两个懒标记,lax为懒乘法标记，laa懒加法标记
public Tree()
{
lax=1;//根据1乘任何数都为原数，懒乘法标记初始值为1
}
}先来看运算过程
[1,3]+3 = (a[1]+3) + (a[2]+3) + (a[3]+3)
[1,3]x2 = (a[1]+3)x2 + (a[2]+3)x2 + (a[3]+3)x2
[1,3]+4 = ((a[1]+3)x2+4)+ ((a[2]+3)x2+4)+ ((a[3]+3)x2+4)
从第一步看，只有一个加法看不出什么；第二步乘法根据算式可以看出乘上了a[n]和懒加法标记即为所得值，但代码中并未直接这样做，而是根据运算的结合律，分为了两部分，懒乘法标记和结点值的相乘，懒乘法标记和懒加法标记的相乘；间接的根据结合律展开将懒乘法标记乘上懒加法标记作为新的懒加法标记存进去，懒乘法标记更新就跟懒加法标记累加一样的步骤累乘即可；最后懒加法标记归零，懒乘法标记根据1乘任何数都为原数而归一。第三步于代码中讨论。其他与区间加差不多。
private static void mark(int l, int r, int node) {
// TODO Auto-generated method stub
if(t[node].lax==1&&t[node].laa==0)
return;
int m = l+r>>1;
int ll = getL(node);
int rr = getR(node);
t[ll].v = (t[ll].v*t[node].lax+t[node].laa*(m-l+1)%mod)%mod;
t[rr].v = (t[rr].v*t[node].lax+t[node].laa*(r-(m+1)+1)%mod)%mod;
//此处对应结合律的展开，懒加法标记已经在上次更新便乘上了懒乘法标记，即上方第二步，新子区间值=(子区间值X懒乘法标记+懒加法标记X懒乘法标记)
t[ll].lax = (t[ll].lax*t[node].lax)%mod;
t[rr].lax = (t[rr].lax*t[node].lax)%mod;//累乘懒乘法标记
t[ll].laa = (t[ll].laa*t[node].lax+t[node].laa)%mod;
t[rr].laa = (t[rr].laa*t[node].lax+t[node].laa)%mod;
//将懒乘法标记乘上懒加法标记并且不能把同一结点的懒加法标记落下，得到新懒加法标记，即上方的第三步，新子树懒加法标记 = (子树左懒加法标记X懒乘法标记+懒加法标记)
t[node].laa=0;
t[node].lax=1;
}import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;
public class Main {
static StreamTokenizer sc = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
public static long getLong()
{
try {
sc.nextToken();
} catch (Exception e) {
// TODO: handle exception
}
return (long)sc.nval;
}
public static int getInt()
{
try {
sc.nextToken();
} catch (Exception e) {
// TODO: handle exception
}
return (int)sc.nval;
}
static class Tree{
long v;
long lax,laa;//两个懒标记,一个记录乘法，一个记录加法
public Tree()
{
lax=1;
}
}
static Tree[] t;
static long mod;
static long[] v;
public static void main(String[] args) {
int n = getInt();
int m = getInt();
mod = getLong();
v = new long[n+1];
int len = n*4+1;
t = new Tree[len];
for(int i=1;i<len;i++)
t[i] = new Tree();
for(int i=1;i<=n;i++)
{
v[i] = getLong();
}
build(1,1,n);
for(int i=0,x,y;i<m;i++)
{
int op = getInt();
x = getInt();
y = getInt();
switch (op) {
case 1:
long k = getLong();
updatax(x,y,1,n,1,k);
break;
case 2:
long d = getLong();
updataa(x, y, 1,n,1,d);
break;
case 3:
System.out.println(sum(x,y,1,n,1));
break;
}
}
}
private static long sum(int x, int y, int l, int r, int node) {
// TODO Auto-generated method stub
if(l>=x&&r<=y)
{
return t[node].v;
}
mark(l,r,node);
int m = l+r>>1;
long ans=0;
if(x<=m)
{
ans = (ans+sum(x,y,l,m,getL(node)))%mod;
}
if(y>m)
{
ans = (ans+sum(x, y, m+1, r, getR(node)))%mod;
}
return ans;
}
private static void mark(int l, int r, int node) {
// TODO Auto-generated method stub
if(t[node].lax==1&&t[node].laa==0)
return;
int m = l+r>>1;
int ll = getL(node);
int rr = getR(node);
t[ll].v = (t[ll].v*t[node].lax+t[node].laa*(m-l+1)%mod)%mod;
t[rr].v = (t[rr].v*t[node].lax+t[node].laa*(r-(m+1)+1)%mod)%mod;
t[ll].lax = (t[ll].lax*t[node].lax)%mod;
t[rr].lax = (t[rr].lax*t[node].lax)%mod;
t[ll].laa = (t[ll].laa*t[node].lax+t[node].laa)%mod;
t[rr].laa = (t[rr].laa*t[node].lax+t[node].laa)%mod;
t[node].laa=0;
t[node].lax=1;
}
private static void updatax(int x, int y, int l, int r, int node, long k) {
// TODO Auto-generated method stub
if(l>=x&&r<=y)
{
t[node].laa = (t[node].laa*k)%mod;//懒加法标记得在乘数进入处更新一次，否则待到第一次更新懒标记处不符合结合律
t[node].lax = (k*t[node].lax)%mod;
t[node].v = (t[node].v*k)%mod; //此两行根据结合律乘上即可
return;
}
mark(l, r, node);
t[node].v = (t[getR(node)].v+t[getL(node)].v)%mod;
int m = l+r>>1;
if(x<=m)
{
updatax(x,y,l,m,getL(node),k);
}
if(y>m)
{
updatax(x, y, m+1, r, getR(node) ,k);
}
t[node].v = (t[getR(node)].v+t[getL(node)].v)%mod;
}
private static void updataa(int x, int y, int l, int r, int node, long d) {
// TODO Auto-generated method stub
if(l>=x&&r<=y)
{
t[node].laa = (t[node].laa+d)%mod;
t[node].v = (t[node].v+d*(r-l+1))%mod;
return;
}
mark(l, r, node);
int m = l+r>>1;
t[node].v = (t[getR(node)].v+t[getL(node)].v)%mod;
if(x<=m)
{
updataa(x,y,l,m,getL(node),d);
}
if(y>m)
{
updataa(x, y, m+1, r, getR(node) ,d);
}
t[node].v = (t[getR(node)].v+t[getL(node)].v)%mod;
}
private static void build(int node, int l, int r) {
// TODO Auto-generated method stub
if(l==r)
{
t[node].v = v[l]%mod;
return;
}
int mid = l+r>>1;
build(getL(node), l, mid);
build(getR(node),mid+1,r);
t[node].v = (t[getR(node)].v + t[getL(node)].v)%mod;
}
private static int getL(int node) {
// TODO Auto-generated method stub
return node<<1;
}
private static int getR(int node) {
// TODO Auto-generated method stub
return node<<1|1;
}
}
我真的太菜了，学了将近两周，二叉树实现都没搞懂是怎么回事，平衡树更是差点没把我送回老家，愣是看三四天都看不会写不出，前头遍历笑嘻嘻，后面平衡mmp，难爆了！！！庆幸的是把线段树弄懂了，虽然也用了差不多一周的时间，说不定再看两三天平衡树就会了？？？不过不看了，该往下一阶段的图论继续学习最短路径，最小生成树了，学过，但没怎么懂，不出意外下周此刻再更(虽然没人看，随机摸鱼)。