二叉树和数据结构

简介: 二叉树和数据结构

小红的完全二叉树构造

题目描述

小红想构造一个总共 n 个节点完全二叉树,该二叉树满足以下两个性质:

1. 所有节点的权值值为 1 ~ n 的一个排列。

2. 除了根节点以外,每个节点的权值和它父亲的权值的乘积为偶数。


请你帮小红构造出这个二叉树,并按层序遍历的方式打印所有节点。

输入描述:一个正整数 n,代表二叉树的节点数量。2≤n≤10^5;

输出描述:

输出一行n个正整数,代表小红构造的二叉树的层序遍历的序列。

输入 4

输出2 4 3 1

说明这棵树的结构如下

显然,任意节点和它父亲权值的乘积都是偶数。

#include<iostream>
#include<algorithm>
using namespace std;
void solve() {
  int n, i, j;
  cin>>n;
  for (i = 2; i <= n; i += 2) {
    cout<<i<<' ';
  }
  for (i = 1; i <= n; i += 2) {
    cout<<i<<' ';
  }
  cout<<endl;
}
int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0), cout.tie(0);
  int T = 1;
  while (T--) {
    solve();
  }
  return 0;
}

平衡二叉树

题目描述

平衡二叉树,顾名思义就是一棵“平衡”的二叉树。在这道题中,“平衡”的定义为,对于树中任意一个节点,都满足左右子树的高度差不超过 d. 空树的高度定义为0,单个节点的高度为1,其他情况下树的高度定义为根节点左右子树高度最大值 + 1. 一棵在高度上平衡的树,节点数可能不平衡,因此再定义一棵树的不平衡度为这棵树中所有节点的左右子树的节点数之差的最大值。

给定平衡的定义参数d, 你需要求出所有高度为 n 的平衡树中不平衡度的最大值。

输入描述:两个整数,n, d.

输出描述:一个整数:所有高度为 n 的平衡树中不平衡度的最大值。

输入 4 1

输出  5

说明

下面这棵树在 d=1 的定义下高度是平衡的,其不平衡度为 5。

备注:0 ≤ n, d ≤ 60

#include <iostream>
using namespace std;
typedef long long ll;
class Tree
{
 public:
    ll left;
  ll right;
};
Tree tree[65];
int main()
{
  tree[1].right = 0;
  tree[1].left = 0;
  int n, d;
  while(cin >> n >> d){
    ll l = 1;
  for (int i = 1; i<n; ++i) {
    l = l * 2;
  }
  --l;
  for (int i = 2; i <= d+1; ++i) {
    tree[i].left = i - 1;
  }
  for (int i = 2; i + d<n+1; ++i) {
    tree[i + d].left = tree[i + d - 1].left + tree[i + d - 1].right + 1;
    tree[i + d].right = tree[i-1].left + tree[i-1].right+1;
  }
  cout<< l - tree[n - d].left <<endl;
    }
  return 0;
}

目录
相关文章
|
1天前
|
存储
数据结构——二叉树
数据结构——二叉树
TU^
|
1天前
|
存储 算法
数据结构~~链式二叉树
数据结构~~链式二叉树
TU^
3 0
|
4天前
|
存储
数据结构初阶 初识二叉树
数据结构初阶 初识二叉树
7 0
|
9天前
|
算法
数据结构和算法学习记录——小习题-二叉树的遍历&二叉搜索树
数据结构和算法学习记录——小习题-二叉树的遍历&二叉搜索树
10 0
|
9天前
|
算法
数据结构和算法学习记录——层序遍历(层次遍历)、二叉树遍历的应用(输出二叉树中的叶节点、求二叉树的高度、二元运算表达式树及其遍历、由两种遍历序列确定二叉树)
数据结构和算法学习记录——层序遍历(层次遍历)、二叉树遍历的应用(输出二叉树中的叶节点、求二叉树的高度、二元运算表达式树及其遍历、由两种遍历序列确定二叉树)
11 0
|
9天前
|
存储 算法
数据结构和算法学习记录——二叉树的非递归遍历(中序遍历、先序遍历、后序遍历)
数据结构和算法学习记录——二叉树的非递归遍历(中序遍历、先序遍历、后序遍历)
11 0
|
9天前
|
存储 算法
数据结构和算法学习记录——二叉树的存储结构&二叉树的递归遍历(顺序存储结构、链表存储结构、先序中序后序递归遍历)
数据结构和算法学习记录——二叉树的存储结构&二叉树的递归遍历(顺序存储结构、链表存储结构、先序中序后序递归遍历)
9 0
数据结构和算法学习记录——二叉树的存储结构&二叉树的递归遍历(顺序存储结构、链表存储结构、先序中序后序递归遍历)
|
9天前
|
算法
数据结构和算法学习记录——初识二叉树(定义、五种基本形态、几种特殊的二叉树、二叉树的重要性质、初识基本操作函数)
数据结构和算法学习记录——初识二叉树(定义、五种基本形态、几种特殊的二叉树、二叉树的重要性质、初识基本操作函数)
6 0
|
9天前
深入理解数据结构第三弹——二叉树(3)——二叉树的基本结构与操作
深入理解数据结构第三弹——二叉树(3)——二叉树的基本结构与操作
12 0
|
9天前
|
测试技术
深入理解数据结构第二弹——二叉树(2)——堆排序及其时间复杂度
深入理解数据结构第二弹——二叉树(2)——堆排序及其时间复杂度
13 0