#include <bits/stdc++.h>
using namespace std;
const int N = 1 << 8;
struct Node {
int winner;
int loser;
};
Node tree[N * 2];
int a[N];
void build(int node, int l, int r) {
if (l == r) {
tree[node].winner = l;
tree[node].loser = -1;
return;
}
int mid = (l + r) / 2;
build(node<<1, l, mid);
build(node <<1 | 1, mid + 1, r);
int left_winner = tree[node<<1].winner;
int right_winner = tree[node<<1|1].winner;
if (a[left_winner] > a[right_winner]) {
tree[node].winner = left_winner;
tree[node].loser = right_winner;
} else {
tree[node].winner = right_winner;
tree[node].loser = left_winner;
}
}
int main() {
int n;
cin >> n;
int total = 1 << n;
for (int i = 1; i <= total; ++i) {
cin >> a[i];
}
build(1, 1, total);
cout << tree[1].loser << endl;
return 0;
}
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 1e6 + 5;
struct No {
int left;
int right;
}tr[MAX_N];
int maxDepth(int node) {
if (node == 0) {
return 0;
}
int leftDepth = maxDepth(tr[node].left);
int rightDepth = maxDepth(tr[node].right);
return max(leftDepth, rightDepth) + 1;
}
int main() {
int n;
cin >> n;
for (int i = 1; i <= n; ++i) {
cin >> tr[i].left >> tr[i].right;
}
int depth = maxDepth(1);
cout << depth << endl;
return 0;
}
三种遍历方式
（前序找根，中序找分割）
#include <iostream>
using namespace std;
struct TreeNode {
int val;
TreeNode *left, *right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
// 前序遍历（根左右）
void preorder(TreeNode* root) {
if (!root) return;
cout << root->val << " "; // 先访问根节点
preorder(root->left); // 再遍历左子树
preorder(root->right); // 最后遍历右子树
}
// 中序遍历（左根右）
void inorder(TreeNode* root) {
if (!root) return;
inorder(root->left); // 先遍历左子树
cout << root->val << " "; // 再访问根节点
inorder(root->right); // 最后遍历右子树
}
// 后序遍历（左右根）
void postorder(TreeNode* root) {
if (!root) return;
postorder(root->left); // 先遍历左子树
postorder(root->right); // 再遍历右子树
cout << root->val << " "; // 最后访问根节点
}
int main() {
/* 构建测试树：
1
/ \
2 3
/ \
4 5
*/
TreeNode* root = new TreeNode(1);
root->left = new TreeNode(2);
root->right = new TreeNode(3);
root->left->left = new TreeNode(4);
root->left->right = new TreeNode(5);
cout << "前序遍历: ";
preorder(root); // 1 2 4 5 3
cout << "\n中序遍历: ";
inorder(root); // 4 2 5 1 3
cout << "\n后序遍历: ";
postorder(root); // 4 5 2 3 1
return 0;
}
判断完二叉树（找第一个不饱和节点）
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
bool isCompleteBinaryTree(vector<int>& tree) {
int n = tree.size();
if (n <= 1) {
return true; // 空树或者只有一个节点的树是完全二叉树
}
queue<int> q;
q.push(1); // 根节点下标为1，将其入队
bool flag = false; // 标记是否遇到了第一个“不饱和节点”（空节点）
while (!q.empty()) {
int curIndex = q.front();
q.pop();
if (curIndex >= n || tree[curIndex] == -1) {
flag = true; // 遇到空节点或者超出数组范围，标记开始检查后续是否有非空节点
} else {
if (flag) {
return false; // 如果已经标记且当前节点非空，不是完全二叉树
}
q.push(2 * curIndex); // 左子节点下标
q.push(2 * curIndex + 1); // 右子节点下标
}
}
return true;
}
建立平衡二叉树
#include<bits/stdc++.h>
using namespace std;
const int maxn=1010;
int n,number[maxn],CBT[maxn],indexl=0;
void inorder(int root)
{
if(root>n)return;
inorder(root*2);//往左子树递归
CBT[root]=number[indexl++];
inorder(root*2+1);//往右子树递归
}
int main()
{
cin>>n;
for(int i=0;i<n;i++)cin>>number[i];
sort(number,number+n); //二叉搜索树中序
inorder(1);
for(int i=1;i<=n;i++)
{
cout<<CBT[i];
if(i<n)cout<<" ";
}
return 0;
}
判断是不是平衡二叉树
bool isBST(int l, int r) {
if (l >= r) return true;
int i = l + 1;
while (i <= r && pre[i] < pre[l]) i++;
int j = i;
while (j <= r && pre[j] >= pre[l]) j++;
return j == r + 1 && isBST(l + 1, i - 1) && isBST(i, r);
}
由前中构建二叉树
#include <iostream>
#include <map>
using namespace std;
const int N = 40;
int n;
int pre[N], in[N];
map<int, int> level;
void digui(int root, int st, int ed, int index){
if(st > ed) return;
level[index] = pre[root];
int i = st;
while(i < ed && in[i] != pre[root]) i ++;
//右子树
digui(root + 1 + i - st, i + 1, ed , 2 * index);
//左子树
digui(root + 1 ,st , i - 1, 2 * index + 1);
}
int main(){
cin >> n;
for(int i = 1; i <= n; i ++) cin >> in[i];
for(int i = 1; i <= n; i ++) cin >> pre[i];
digui(1, 1, n, 1);
auto it = level.begin();
cout << it -> second;
while(++ it != level.end()) cout << ' ' << it -> second;
cout << "\n";
return 0;
}
bool Compare(int root1, int root2)
{
if(root1 == -1 && root2 == -1) return true;
if((root1 == -1 && root2 != -1) || (root1 != -1 && root2 == -1)) return false;
if(tree1[root1].data != tree2[root2].data) return false;
return (Compare(tree1[root1].left, tree2[root2].left) && Compare(tree1[root1].right, tree2[root2].right))
|| (Compare(tree1[root1].left, tree2[root2].right) && Compare(tree1[root1].right, tree2[root2].left));
}
//当出现前后相等的时候，有可能为相邻
#include <iostream>
#include <string>
using namespace std;
int main() {
string pre, post;
cin >> pre >> post;
int n = pre.size();
int pos[128] = {0};
for (int i = 0; i < n; ++i) {
pos[post[i]] = i;
}
int k = 0;
for (int i = 0; i < n - 1; ++i) {
if (pos[pre[i]] - 1 == pos[pre[i + 1]]) {
k++;
}
}
cout << (1LL << k) << endl;
return 0;
}
#include <bits/stdc++.h> // 包含所有标准库头文件，竞赛常用写法
using namespace std;
unordered_map<char, int> pos; // 全局哈希表，记录中序遍历中每个字符的位置索引
/**
* 根据前序遍历和中序遍历构建二叉树，并返回后序遍历结果字符串
* @param pre 前序遍历字符串
* @param in 中序遍历字符串
* @param preL 当前子树在前序遍历中的起始位置
* @param inL 当前子树在中序遍历中的起始位置
* @param inR 当前子树在中序遍历中的结束位置
* @return 当前子树的后序遍历结果字符串
*/
string post(string& pre, string& in, int preL, int inL, int inR) {
// 递归终止条件：前序遍历越界或中序遍历范围无效
if (preL >= pre.size() || inL > inR) return "";
// 当前子树的根节点（前序遍历的第一个字符）
char root = pre[preL];
// 获取根节点在中序遍历中的位置
int p = pos[root];
// 递归构建左子树：
// - 前序遍历：根的下一个位置（preL + 1）
// - 中序遍历：左子树的起始（inL）到根的前一个位置（p - 1）
string left = post(pre, in, preL + 1, inL, p - 1);
// 递归构建右子树：
// - 前序遍历：跳过左子树的所有节点（preL + p - inL + 1）
// - 中序遍历：根的右边（p + 1）到当前结束位置（inR）
string right = post(pre, in, preL + p - inL + 1, p + 1, inR);
// 后序遍历：左子树结果 + 右子树结果 + 根节点
return left + right + root;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
string in, pre; // 存储输入的中序和前序遍历字符串
cin >> in >> pre;
// 构建中序遍历字符到位置的映射（加速查找）
for (int i = 0; i < in.size(); ++i)
pos[in[i]] = i;
cout << post(pre, in, 0, 0, in.size() - 1) << "\n";
return 0;
}
简单的二叉树可以用set或者muiltset代替；
auto it = ms.lower_bound(x);
cout << distance(ms.begin(), it) + 1 << ‘\n’;
#include <bits/stdc++.h>
using namespace std;
#define int long long
int n,m;
map<int,int> mp;
void bd(int u,int l,int r){
if(l==r){
tr[u]=l;
}else{
int mid=(l+r)/2;
bd(u<<1,l,mid);
bd(u<<1|1,mid+1,r);
}
}
void find(string s,int pos,int u,int l,int r){
if(pos==n){
cout<<tr[u]<<"\n";
return ;
}
if(s[pos]=='y'){
find(s,pos+1,u<<1,l,(l+r)/2);
}else{
find(s,pos+1,u<<1|1,(l+r)/2+1,r);
}
}
signed main(){
cin>>n>>m;
string s;
bd(1,1,(1<<n));
for(int i=0;i<m;i++){
cin>>s;
find(s,0,1,1,(1<<n));
}
}//
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, m;
cin >> n >> m;
string s;
for (int i = 0; i < m; i++) {
cin >> s;
int res = 1;
for (int j = 0; j < n; j++) {
if (s[j] == 'n') {
res += (1 << (n - j - 1));
}
}
cout << res << "\n";
}
return 0;
}
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n,m,ans=1,b[N];
struct node{
int date,l,r;
}tree[N];
void dfs(int x){
if(x>n) return;
//后续遍历
if(tree[x].l) dfs(tree[x].l);
if(tree[x].r) dfs(tree[x].r);
scanf("%d",&tree[x].date);
}
int main()
{
int i,j;
scanf("%d",&n);
for(i=1;i<=n;i++){
//建树
if(2*i<=n) tree[i].l=2*i;
if(2*i+1<=n) tree[i].r=2*i+1;
}
dfs(1);
for(i=1;i<=n;i++){
if(i!=1) printf(" ");
printf("%d",tree[i].date);
}
return 0;
}
树上任意两点间的距离可以直接通过最短路算法获得。
树的深度就是距离根节点最远的那个点的距离。
树的宽度是节点最多的一层，同一层的节点距离根节点的距离都是相同的
