二叉树是一种特殊的树形数据结构，具有以下特点：

基本定义

• 节点的度：二叉树中每个节点最多有两个子节点，分别称为左子节点和右子节点。

• 子树的顺序性：二叉树的子树有左右之分，且顺序不能颠倒。

• 递归定义：二叉树可以为空，或者由一个根节点和两棵互不相交的左子树和右子树组成，左子树和右子树本身也是二叉树。

 

基本形态

二叉树有五种基本形态：

1. 空二叉树。

2. 只有一个根节点的二叉树。

3. 只有左子树的二叉树。

4. 只有右子树的二叉树。

5. 左右子树都存在的二叉树。

特殊二叉树

• 满二叉树：每一层的节点数都达到最大值，即如果层数为K，则节点总数为2K−1。所有叶子节点都在最后一层。

• 完全二叉树：深度为K的二叉树，前K-1层是满的，最后一层的节点从左到右连续排列。

 满二叉树一定是完全二叉树，但是完全二叉树不一定是满二叉树

题目描述

一个学校里老师要将班上 NN 个同学排成一列，同学被编号为 1∼N1∼N，他采取如下的方法：

1. 先将 11 号同学安排进队列，这时队列中只有他一个人；

2. 2∼N2∼N 号同学依次入列，编号为 ii 的同学入列方式为：老师指定编号为 ii 的同学站在编号为 1∼(i−1)1∼(i−1) 中某位同学（即之前已经入列的同学）的左边或右边；

3. 从队列中去掉 MM 个同学，其他同学位置顺序不变。

在所有同学按照上述方法队列排列完毕后，老师想知道从左到右所有同学的编号。

输入格式

第一行一个整数 NN，表示了有 NN 个同学。

第 2∼N2∼N 行，第 ii 行包含两个整数 k,pk,p，其中 kk 为小于 ii 的正整数，pp 为 00 或者 11。若 pp 为 00，则表示将 ii 号同学插入到 kk 号同学的左边，pp 为 11 则表示插入到右边。

第 N+1N+1 行为一个整数 MM，表示去掉的同学数目。

接下来 MM 行，每行一个正整数 xx，表示将 xx 号同学从队列中移去，如果 xx 号同学已经不在队列中则忽略这一条指令。

输出格式

一行，包含最多 NN 个空格隔开的整数，表示了队列从左到右所有同学的编号。

输入输出样例

输入 #1复制

4
1 0
2 1
1 0
2
3
3

输出 #1复制

2 4 1

说明/提示

【样例解释】

将同学 22 插入至同学 11 左边，此时队列为：

2 1

将同学 33 插入至同学 22 右边，此时队列为：

2 3 1

将同学 44 插入至同学 11 左边，此时队列为：

2 3 4 1

将同学 33 从队列中移出，此时队列为：

2 4 1

同学 33 已经不在队列中，忽略最后一条指令

最终队列：

2 4 1

【数据范围】

对于 20%20% 的数据，1≤N≤101≤N≤10。

对于 40%40% 的数据，1≤N≤10001≤N≤1000。

对于 100%100% 的数据，1<M≤N≤1051<M≤N≤105。

#include<bits/stdc++.h>
using namespace std;
int n,m,x,k,f;
struct T{
    int l,r;       
	int d;
}t[100010];
int main(){
	ios::sync_with_stdio(false);
	cin.tie(NULL);
    cin>>n;
    t[0].r=0,t[0].l=1;
    t[1].r=0,t[1].l=0;
    for (int i=2;i<=n;i++)
    {
        cin>>x>>f;
        if(f==1){
            t[i].r=t[x].r;
            t[i].l=x;
            t[x].r=i;
            t[t[i].r].l=i;
        }else{
            t[i].r=x;
            t[i].l=t[x].l;
            t[x].l=i;
            t[t[i].l].r=i;
        }
    }
    cin>>m;
    while(m--)
    {
        cin>>x;
        t[x].d=1;
    }
    for (int i=t[0].r;i;i=t[i].r)
    {
        if (t[i].d==0)   
          cout<<i<<" ";
    }
    return 0;
}

 

题目描述

定义如下规则：

1. 空串是「平衡括号序列」
2. 若字符串 SS 是「平衡括号序列」，那么 [S][S] 和 (S)(S) 也都是「平衡括号序列」
3. 若字符串 AA 和 BB 都是「平衡括号序列」，那么 ABAB（两字符串拼接起来）也是「平衡括号序列」。

例如，下面的字符串都是平衡括号序列：

• ()，[]，(())，([])，()[]，()[()]

而以下几个则不是：

• (，[，]，)(，())，([()

现在，给定一个仅由 (，)，[，]构成的字符串 ss，请你按照如下的方式给字符串中每个字符配对：

1. 从左到右扫描整个字符串。
2. 对于当前的字符，如果它是一个右括号，考察它与它左侧离它最近的未匹配的的左括号。如果该括号与之对应（即小括号匹配小括号，中括号匹配中括号），则将二者配对。如果左侧未匹配的左括号不存在或与之不对应，则其配对失败。

配对结束后，对于 ss 中全部未配对的括号，请你在其旁边添加一个字符，使得该括号和新加的括号匹配。

输入格式

输入只有一行一个字符串，表示 ss。

输出格式

输出一行一个字符串表示你的答案。

输入输出样例

输入 #1复制

([()

输出 #1复制

()[]()

输入 #2复制

([)

输出 #2复制

()[]()

说明/提示

数据规模与约定

对于全部的测试点，保证 ss 的长度不超过 100100，且只含 (，)，[，] 四种字符。

#include<bits/stdc++.h>
using namespace std;
char a[105];
int i=0;
int c[105];
int main(){
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	scanf("%s",a);
	i=strlen(a);
	for(int k=0;k<i;k++){
		if(a[k]==']'&&c[k]==0){
			for(int x=k-1;x>=0;x--){
				if(a[x]=='['&&c[x]==0){
					c[x]=1;c[k]=1;
					break;
			    }
			    if(a[x]=='('&&c[x]==0)break;
			}
		}
		if(a[k]==')'&&c[k]==0){
			for(int x=k-1;x>=0;x--){
				if(a[x]=='('&&c[x]==0){
					c[x]=1;c[k]=1;
					break;
                }
                if(a[x]=='['&&c[x]==0)break;
			}
        }
	}
	for(int k=0;k<i;k++){
		if(c[k]==0){
			if(a[k]=='('||a[k]==')'){
				cout<<"()";
			}else cout<<"[]";
		}else cout<<a[k];
	}
	return 0;
}