【数据结构1-2】二叉树
温馨提示：这篇文章已超过447天没有更新，请注意相关的内容是否还可用！
树形结构不仅能表示数据间的指向关系，还能表示出数据的层次关系，而有很明显的递归性质。因此，我们可以利用树的性质解决更多种类的问题。
但是在平常的使用中，我们并不需要使用这么复杂的结构，只需要建立一个包含int right和int left的结构体即可，left和right用于指示该节点的左儿子和右儿子。
一、【P4913】二叉树深度（递归/层次遍历）
本题的重点在于二叉树的存储和二叉树的层次遍历。
1. 二叉树存储：考虑一个二叉树的每个节点都有两个子节点，所以我们可以考虑用一个结构体来存储。其中，left和right分别代表节点的左节点编号和右节点编号。
struct node {
int left, right;
};
node tree[MAXN];
2. 二叉树层次遍历：我们可以从根节点出发，先递归遍历该节点的左节点，再递归遍历该节点的右节点。对于每个父亲节点，先比较左右子树的高度，然后选取较高的子树，将其深度加1，每次遍历更新子树的高度。当遍历到叶子节点后返回0（叶子节点的左右子树高度均为0）。
int maxDepth(int id)
{
if (id == 0) return 0;
return 1 + max(maxDepth(Tree[id].left), maxDepth(Tree[id].right));
}
AC代码：
#include
#include
#include
#include
using namespace std;
struct node
{
int left;
int right;
}Tree[1000005];
int maxDepth(int id)
{
if (id == 0) return 0;
return 1 + max(maxDepth(Tree[id].left), maxDepth(Tree[id].right));
}
int main()
{
int n; cin >> n;
for (int i = 1; i > a >> b;
Tree[i].left = a;
Tree[i].right = b;
}
cout e0) return nullptr;
char mid = preorder[s1];
int index = mp[mid]; //找到当前父亲节点在中序遍历inorder中的位置
int left_length = index - s0; //左子树大小
TreeNode* node = new TreeNode(mid);
node->left = buildTree(preorder, mp, s0, index - 1, s1 + 1);
node->right = buildTree(preorder, mp, index + 1, e0, s1 + 1 + left_length);
return node;
}
void PostOrder(TreeNode* tree)
{
if (!tree) return;
PostOrder(tree->left);
PostOrder(tree->right);
cout val;
}
int main()
{
string preorder, inorder;
cin >> inorder >> preorder;
map mp;
//使用map存储，便于搜索
for (int i = 0; i
由于需要通过preorder序列的节点，查询该点在inorder序列的位置，所以将inorder序列用map存储，实现O(1)量级的查询。
使用buildTree函数递归还原整棵树，然后使用postorder函数对树进行后序遍历，得到答案。
三、【P1229】遍历问题（前中后序遍历）
思路：给定inorder能确定树的具体结构，是因为可以确定子树是左子树还是右子树；而只给定preorder和postorder，则不能确定，这就是会出现不同树结构的原因。
只有前和后，那么主要问题就是没有办法处理只有一个子树的情况，因为这种情况下不知道子树究竟是这个节点的左子树还是右子树，也就是说其实这道题要判断遍历中存在着多少个只有一棵子树的情况。对于前，如果一个结点的下个结点等于后中对应结点的前一个结点的话，那么这个结点就是根节点且其只有一个子树。sum初始化为1，出现一个只有一棵子树的情况，就把sum*2（每次会出现两种不同的情况，分别是出现左子树和出现右子树）。
AC代码：
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
const int INF = 0x7fffffff;
int main()
{
string preorder, postorder;
cin >> preorder >> postorder;
int sum = 1;
for (int i = 0; i postorder;
preorder(inorder, postorder);
}
将2，3，4三题进行比较，2的解题思路具有普适性，但是建树的过程相对复杂；4的解题思路较为清晰，但是缺点在于只能输出序列，并不能得到完整的树。
五、【P5076】简化二叉树（二叉搜索树）
参考：https://www.cnblogs.com/do-while-true/p/13566274.html
但值得强调的是，二叉搜索树是一种低级的平衡二叉树，因为在最差情况下，可以会呈现链状结构，导致时间复杂度为O(n)，而不是所需的O(logN)。因此，只需要了解即可，重点需要掌握的是平衡二叉树。
splay搜索树的几种操作：
（1）插入：x 是当前节点的下标，v 是要插入的值。要在树上插入一个 v 的值，就要找到一个合适 v 的位置，如果本身树的节点内有代表 v 的值的节点，就把该节点的计数器加 11 ，否则一直向下寻找，直到找到叶子节点，这个时候就可以从这个叶子节点连出一个儿子，代表 v 的节点。具体向下寻找该走左儿子还是右儿子是根据二叉搜索树的性质来的。
void add(int x,int v)
{
tree[x].siz++;
//如果查到这个节点，说明这个节点的子树里面肯定是有v的，所以siz++
if(tree[x].val==v){
//如果恰好有重复的数，就把cnt++，退出即可，因为我们要满足第四条性质
tree[x].cnt++;
return ;
}
if(tree[x].val>v){//如果v=val)
{//如果当前值大于val，就说明查的数大了，所以要往左子树找
if (tree[x].ls==0)//如果没有左子树就直接返回找到的ans
return ans;
else//如果不是的话，去查左子树
return queryfr(tree[x].ls,val,ans);
}
else
{//如果当前值小于val，就说明我们找比val小的了
if (tree[x].rs==0)//如果没有右孩子，就返回tree[x].val，因为走到这一步时，我们后找到的一定比先找到的大(参考第二条性质)
return (tree[x].val=rk了，就说明答案在左子树里
return queryrk(tree[x].ls,rk);//查左子树
if(tree[tree[x].ls].siz+tree[x].cnt>=rk)//如果左子树大小加上当前的数的多少恰好>=k，说明我们找到答案了
return tree[x].val;//直接返回权值
return queryrk(tree[x].rs,rk-tree[tree[x].ls].siz-tree[x].cnt);
//否则就查右子树，同时减去当前节点的次数与左子树的大小
}
AC代码：
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
const int INF = 0x7fffffff;
struct node
{
int val; //节点值
int left, right; //左右子树
int cnt; //计数器
int siz; //子树大小
}tree[100005];
int cont = 0;//记录节点数量
//初始化
void init()
{
for (int i = 0; i value) //如果x的值大于value，value只能放在x的左子树上
{
if (tree[x].left != 0)//如果左子树上有节点，递归查找
add(tree[x].left, value);
else//如果左子树上没有点，直接添加
{
cont++;
tree[cont].val = value;
tree[cont].siz = tree[cont].cnt = 1;
tree[x].left = cont;
}
}
else if (tree[x].val = value)//当前节点val大于所查value，到左子树查找
{
if (tree[x].left == 0) //左子树不存在，那么前驱为ans
return ans;
else
return query_front(tree[x].left, value, ans); //否则遍历左子树
}
else
{
if (tree[x].right == 0)//若无右孩子，说明当前点满足条件
return (tree[x].val tree[x].val)
return val_to_rank(tree[x].right, value) + tree[tree[x].left].siz + tree[x].cnt;//左子树上的所有点加上根上的点都小于value
}
//按排名找值
int rank_to_val(int x, int rank)
{
if (x == 0)
return INF;
if (tree[tree[x].left].siz >= rank) //如果小于x.val的数多于rank，那么该值一定在左子树上，递归查找
return rank_to_val(tree[x].left, rank);
if (tree[tree[x].left].siz + tree[x].cnt >= rank) //如果左子树上的点数+根上的节点数大于rank，且左子树上的点数小于rank，那么点x的值为所需值
return tree[x].val;
return rank_to_val(tree[x].right, rank - tree[tree[x].left].siz - tree[x].cnt); //否则在右子树上，要先将左子树+根上的点数减去
}
int main()
{
int q; cin >> q;
init();
for (int i = 1; i > op >> v;
if (op == 1)
cout v;
a[u][v] = 1;
a[v][u] = 2;
}
for (int k = 1; k 
