树——基础二叉树知识点¶
树是n个结点的有限集合，它或者是空集，或者满足以下条件：
- 有一个被称为根的结点；
- 其余结点可分为m(m \geqslant 0)个互不相交的集合T_{1}, T_{2}, \cdots, T_{m}，这些集合本身也是一棵树，并称它们为根结点的子树.
树中唯一一个没有直接前驱的结点称为**根结点**，叶结点**也称为终端结点。除根以外的非叶结点也被称为**内部结点。
一个结点直接后继的数目称为**结点的度**。树中所有结点的度的最大值称为这棵**树的度**。
结点的直接后继称为结点的**子结点**，而结点的直接前驱称为它的**父结点**。在树中，每个结点都存在着唯一的一条到根结点的路径，路径上的所有结点都是该结点的**祖先结点**。**子孙结点**是指该结点的所有子树中的全部结点。也就是说，树中除根之外的所有结点都是根结点的子孙。
结点的层次，也称为**深度**，是从根结点到这个结点所经过的边数。一棵树中结点的最大层次称为**树的高度或深度**。**结点的高度**指的是以该结点为根的子树的高度。
若将树中每个结点的子树看成自左向右有序的，则称该树为**有序树**，否则称为**无序树**。
找树根和节点的孩子¶
- 一本通-1336：【例3-1】找树根和孩子
给定一棵树，输出树的根root，孩子最多的结点max以及他的孩子。
树的根入度为0，只需用一个二维矩阵统计每个节点的孩子，每个节点对应的数组大小就是孩子的数量。
#include <bits/stdc++.h>
using namespace std;
int n, m;
vector<vector<int> > grid(105);
vector<int> inDegree(105);
void solve()
{
int root = -1, node = -1, maxVal = 0;
for (int i = 1; i <= n; ++i) {
if (grid[i].size() > maxVal) {
maxVal = grid[i].size();
node = i;
}
if (inDegree[i] == 0) root = i;
}
cout << root << endl;
cout << node << endl;
int len = grid[node].size();
sort(grid[node].begin(), grid[node].end());
for (int i = 0; i < len; ++i) {
cout << grid[node][i];
if (i != len - 1) cout << ' ';
}
cout << endl;
}
int main()
{
std::ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> n >> m;
int from, to;
for (int i = 0; i < m; ++i) {
cin >> from >> to;
grid[from].push_back(to);
++inDegree[to];
}
solve();
return 0;
}
二叉树主要性质¶
- 一颗非空二叉树的第i层上最多有2^{i-1}的点。
若使第i层的节点个数最多，则i-1层必须是每个节点都有两个子节点。采用归纳法，当i=1时，显然成立，设当i=k时成立，则第k+1层节点最多是k层的两倍为2^k，成立。
- 一颗高度为k的二叉树，最多具有2^{k}-1个节点。
满二叉树，相当于求解： $$ \sum _{i=0} {k-1}2i=2^k-1 $$
- 对于一颗非空二叉树，如果叶节点数为n_0，度为2的节点数为n_2，则n_0=n_2+1。
证明：设二叉树中度为1的节点个数为n_1，节点总个数为n则： $$ n = n_1 + n_2 + n_0 $$ 因为二叉树中节点是两两相连，则边（B）的数量为： $$ B = n -1 $$ 因为边都是从度为1或2的节点引出，所以有： $$ B = n_1 + 2n_2 $$ 于是有： $$ n-1=n_1+2n_2 $$ 所以联立可得：n_0=n_2+1
- 具有n个节点的完全二叉树的高度k=[log_2n] +1。
设具有n个节点的完全二叉树的高度为k，则完全二叉树的前k-1层必是满的，所以有2^{k-1}-1个节点，则第k层最少有一个节点，最多有2^{k-1}个节点，所以有不等式： $$ 2^{k-1} -1 < n \leq 2^k-1\ k-1 \leq log_2n < k\ log_2n <k \leq log_2n+1 \ k = [log_2n]+1 $$
- 如果有一颗n个节点的完全二叉树中的节点按层自上而下（第一层到[log_2n]+1层），每一层自左向右编号，设根节点的编号是1，则对任意一个编号为i的节点（1\leq i \leq n），有：
- 如果i=1，则该节点是二叉树的根节点，如果i > 1则其父节点的编号是[i/2]
- 如果2i > n，则编号为i的结点为叶节点，没有儿子（注意完全二叉树的限制），否则左儿子的编号2i
- 如果2i+1>n，则编号为i的结点没有右儿子，否则右儿子的编号是2i+1。
满二叉树与完全二叉树¶
满二叉树和完全二叉树可以不用建树的方法，而利用其下标的关系，利用数组进行模拟。
- 一本通-1363：小球（drop）（满二叉树模拟/利用奇偶性巧妙转化）
这道题同时还是《算法竞赛入门经典》的6.3二叉树中的题目。
首先来估算数据范围，其中深度最大是20，那么意味着节点的数目是2^{20}\approx 10^6，所以如果是模拟的化，开这么大的数组也是没问题的，由于每个小球都要走二叉树的深度的次数，所以时间复杂度是6 \times 10^ 6 \times 20 = 1.2 \times 10^7，所以还是在时间限制范围内的。
模拟的方法：由于题目指明是满二叉树，满二叉树一个很重要的性质是左右子节点和父节点存在对应关系，设父节点下标为k，左子节点下标为2k，右子节点下标为2k+1。
#include <bits/stdc++.h>
using namespace std;
vector<bool> node(2 * 1e6, false);
int n;
int solve(int num)
{
int curPos = 1, prePos = 1;
for (int i = 1; i <= num; ++i) {
curPos = 1, prePos = 1;
while (curPos <= n) {
if (node[curPos]) {
node[curPos] = false;
prePos = curPos;
curPos = curPos * 2 + 1;
}
else {
node[curPos] = true;
prePos = curPos;
curPos <<= 1;
}
}
}
return prePos;
}
int main()
{
std::ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int depth, num; cin >> depth >> num;
n = (1 << depth) - 1; //满二叉树全部节点的个数
cout << solve(num) << endl;
return 0;
}
第二种方法：在《算法竞赛入门经典》里面，给出了一种很巧妙的实现，非常类似于约瑟夫环这种类型，往往存在着简单的解法。我们发现对于根节点，也就是标号为1的节点，它为true还是false只和奇偶有关，也就是第一个小球时是false，第三个小球是false。然后类似递归的去解决，比如标号为2的节点，很显然，只有标号为奇数的小球才会落在左子树2，然后我们对这些小球“重新编号”，那么第一个小球是1，第三个小球是2，相当于递归的去解决问题了。这样做的一个好处是根本不需要去开一个大数组去存储树上每个节点的状态，也不需要去做一些没有用处的模拟。另外如果是多组输入的情况下，很显然第二种方法更能节省时间。
#include <bits/stdc++.h>
using namespace std;
int main()
{
std::ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int depth, num;
cin >> depth >> num;
int k = 1;
for (int i = 0; i < depth - 1; ++i) {
if (num & 1) { //小球标号为奇数
k <<= 1; num = ((num + 1) >> 1);
}
else { //小球标号为偶数
k = k * 2 + 1; num >>= 1;
}
}
cout << k << endl;
return 0;
}
- 洛谷-P1087 FBI树（满二叉树下标关系）
我们可以把由“0”和“1”组成的字符串分为三类：全“0”串称为B串，全“1”串称为I串，既含“0”又含“1”的串则称为F串。
FBI树是一种二叉树，它的结点类型也包括F结点，B结点和I结点三种。由一个长度为2N的“01”串S可以构造出一棵FBI树T，递归的构造方法如下：
T的根结点为R，其类型与串S的类型相同；
若串S的长度大于1，将串S从中间分开，分为等长的左右子串S1和S2；由左子串S1构造R的左子树T1，由右子串S2构造R的右子树T2。
现在给定一个长度为2N的“01”串，请用上述构造方法构造出一棵FBI树，并输出它的后序遍历序列。
#include <bits/stdc++.h>
using namespace std;
int n = 1 << 11;
int N;
vector<char> seq(n);
void build()
{
for (int i = (1 << N) - 1; i >= 1; --i) {
int left = 2 * i, right = 2 * i + 1;
if (seq[left] == seq[right]) {
switch(seq[left]) {
case 'F': seq[i] = 'F'; break;
case 'I': seq[i] = 'I'; break;
default: seq[i] = 'B';
}
}
else {
seq[i] = 'F';
}
}
}
void postTraversal(int pos)
{
if (pos > n) return;
postTraversal(pos * 2);
postTraversal(pos * 2 + 1);
cout << seq[pos];
}
int main()
{
std::ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> N;
n = (1 << (N + 1)) - 1; //总的节点个数
for (int i = (1 << N); i <= n; ++i) {
char ch; cin >> ch;
seq[i] = (ch == '0') ? 'B' : 'I';
}
build();
postTraversal(1);
return 0;
}
扩展二叉树¶
先序、中序和后序序列中的任何一个都不能唯一确定一棵二叉树，采用.对空节点进行补齐，把这样处理的二叉树称为扩展二叉树。扩展二叉树的先序和后序序列能唯一确定其二叉树。
现给出扩展二叉树的先序序列，输出中序和后序序列。
- 一本通-1340：【例3-5】扩展二叉树
#include <bits/stdc++.h>
using namespace std;
class Tree
{
struct TreeNode {
char ch;
TreeNode *left, *right;
TreeNode(char x): ch(x), left(NULL), right(NULL) {}
};
TreeNode *root;
int pos;
void build(const string & s, TreeNode *& root)
{
if (s[++pos] != '.') {
root = new TreeNode(s[pos]);
build(s, root -> left);
build(s, root -> right);
}
else root = NULL;
}
void inorderTraversal(TreeNode *root)
{
if (root) {
inorderTraversal(root -> left);
cout << root -> ch;
inorderTraversal(root -> right);
}
}
void postorderTraversal(TreeNode *root)
{
if (root) {
postorderTraversal(root -> left);
postorderTraversal(root -> right);
cout << root -> ch;
}
}
void makeEmpty(TreeNode *& root)
{
if (root) {
makeEmpty(root -> left);
makeEmpty(root -> right);
delete root;
root = NULL;
}
}
public:
Tree(): root(NULL), pos(-1) {}
~Tree() { makeEmpty(root); }
void build(const string & s){ build(s, root); }
void inorderTraversal() { inorderTraversal(root); }
void postorderTraversal() { postorderTraversal(root); }
};
int main()
{
std::ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
string s;
cin >> s;
Tree obj;
obj.build(s);
obj.inorderTraversal();
cout << endl;
obj.postorderTraversal();
cout << endl;
return 0;
}