- 树是一种非线性的数据结构，用它能很好地描述有分支和层次特性的数据集合
- ======简单树======
- 树的定义及其相关概念
- 树的父亲表示法，数组
- 二叉树的定义及其基本性质
- 二叉树的遍历：前序、中序、后序遍历，递归
- ======特殊树======
- 完全二叉树的定义与基本性质
- 完全二叉树的数组表示法
- 哈夫曼树的定义、构造及其遍历
- 二叉排序树的定义、构造及其遍历
- ====Handbook部分=====
- 概念
- Tree traversal树的遍历
- Diameter树的直径
- Binary trees二叉树
- 《一本通》题目
- 【例3-1】找树根和孩子">【例3-1】找树根和孩子
- 【例3-2】单词查找树">【例3-2】单词查找树
- 【例3-4】求后序遍历">【例3-4】求后序遍历
- 【例3-5】扩展二叉树">【例3-5】扩展二叉树
- 小球(drop)">小球(drop)
- 二叉树遍历(flist)">二叉树遍历(flist)
- FBI树(fbi)">FBI树(fbi)
- 二叉树输出(btout)">二叉树输出(btout)
- 查找二叉树(tree_a)">查找二叉树(tree_a)
- 对称二叉树(tree_c)">对称二叉树(tree_c)
- 合并果子(fruit)">合并果子(fruit)
- 最小函数值(minval)">最小函数值(minval)
- 看病">看病
- 小明的账单">小明的账单
- 鱼塘钓鱼(fishing）">鱼塘钓鱼(fishing）
树是一种非线性的数据结构，用它能很好地描述有分支和层次特性的数据集合
树型结构在现实世界中广泛存在，比如组织关系图。
树型结构在计算机领域中也有广泛应用，如在编译系统中，用树表示源程序的语法结构。
在数据库系统中，树型结构是数据库层次模型的基础，也是各种索引和目录的主要组织形式。
在许多算法中，经常用树型结构描述问题的求解过程、所有解的状态和求解对策。
在树型结构中，二叉树是最常用的结构，分治个数确定，又可以为空，有良好的递归特性，特别适宜于程序设计。一般树会转换成二叉树进行处理。
======简单树======
树的定义及其相关概念
树的父亲表示法，数组
// 优缺点：利用了树中除根结点外每个结点都有唯一的父结点这个性质// 很容易找到树根，但找孩子时需要遍历整个线性表struct node{int data, parent;}tree[110];
二叉树的定义及其基本性质
二叉树(Binary Tree, BT)是一种特殊的树型结构，每个结点最多有两个子节点。
5种基本形态：
- 空二叉树
- 仅有根结点的二叉树
- 右子树为空的二叉树
- 左右子树均非空的二叉树
- 左子树为空的二叉树
性质：
- 在二叉树的第 i 层上最多有
个结点 - 深度为 depth 的二叉树，至多有
个结点 - 对任意一棵二叉树，如果叶子结点数为
，度为 2 的结点数为
，一定满足
证明：
，算两次
- 具有 n 个结点的完全二叉树，深度为
。注意，根的深度，有的定义是0，有的定义是1 - 对于一棵具有 n 个结点的完全二叉树，对于任意一个结点，编号为 i
if (i > 1) 父结点编号 i / 2
if (2 i > n) 没有左儿子 else 左儿子编号为 2 i
if (2 i + 1 > n) 没有右儿子 else 右儿子编号为 2 i + 1
Catalan数：
- 具有 n 个结点的不同形态的二叉树，有多少棵 ```cpp 一棵具有 n(n > 1) 个结点的二叉树
可以看成是, 由 一个根结点， 一棵具有 i 个结点的左子树， 一棵具有 n - i - 1个结点的右子树组成
i 的取值范围[0, n - 1]
<br /><br /><br /><a name="TFOMj"></a>## 二叉树的孩子表示法，链式存储结构+顺序存储结构```cpp// 链式存储结构struct node{int data;node *lchild, *rchild; //左儿子，右儿子};node *root;// 顺序存储结构const int N = 110;int data[N]；int lchild[N], rchild[N]; // int child[N][2]; 也可以这样写int root;
https://www.cnblogs.com/tarbitrary/p/4030652.html
二叉树的遍历：前序、中序、后序遍历，递归
性质：
- 已知先序和中序，可以确定出二叉树
- 已知中序和后序，可以确定出二叉树
- 已知先序和后序，不可以确定出二叉树
#include <bits/stdc++.h>using namespace std;struct node{char data;node *lchild, *rchild;};node *root;// 按先序输入二叉树的结点，输入$表示空树void build(node* &p){char c;scanf("%c", &c);if (c == '$') p = NULL;else{p = new node();p->data = c;build(p->lchild); build(p->rchild);}}void pre_order(node *p){if (p == NULL) return;if (p->data != '$') cout << p->data;pre_order(p->lchild);pre_order(p->rchild);}void in_order(node *p){if (p == NULL) return;in_order(p->lchild);if (p->data != '$') cout << p->data;in_order(p->rchild);}void post_order(node *p){if (p == NULL) return;post_order(p->lchild);post_order(p->rchild);if (p->data != '$') cout << p->data;}int main(){build(root);pre_order(root);puts("");in_order(root);puts("");post_order(root);puts("");return 0;}/*输入：AB$$C$$输出：ABCBACBCA*/
======特殊树======
完全二叉树的定义与基本性质
完全二叉树的数组表示法
- 对于一棵具有 n 个结点的完全二叉树，对于任意一个结点，编号为 i
if (i > 1) 父结点编号 i / 2
if (2 i > n) 没有左儿子 else 左儿子编号为 2 i
if (2 i + 1 > n) 没有右儿子 else 右儿子编号为 2 i + 1
#include <bits/stdc++.h>using namespace std;const int N = 1010;char data[N];int node[N];int n;void pre_order(int i){if (data[i] == '$') return ;if (data[i] != '$') cout << data[i];if (i * 2 <= n) pre_order(i * 2);if (i * 2 + 1 <= n) pre_order(i * 2 + 1);}void in_order(int i){if (data[i] == '$') return ;if (i * 2 <= n) in_order(i * 2);if (data[i] != 'S') cout << data[i];if (i * 2 + 1 <= n) in_order(i * 2 + 1);}void post_order(int i){if (data[i] == '$') return ;if (i * 2 <= n) post_order(i * 2);if (i * 2 + 1 <= n) post_order(i * 2 + 1);if (data[i] != 'S') cout << data[i];}int main(){memset(data, '$', sizeof data);cin >> n; // 结点总数for (int i = 1; i <= n; i++) cin >> data[i]; // 根结点下标是1，从上到下，从左到右输入pre_order(1);puts("");in_order(1);puts("");post_order(1);puts("");return 0;}/*输入：3A B C输出：ABCBACBCA*/
哈夫曼树的定义、构造及其遍历
定义
Huffman Tree， 给定n个权值作为n个叶子结点，构造一棵二叉树，若该树的WPL(带权路径)长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(Huffman Tree)。
构造
在我们已有的权值（例子里的频次）中，每次都找到2个最小的，将它们构造成一颗二叉树，再插入我们已经构造好的二叉树中，将每个值都插完后，我们的哈夫曼树就构造完成了。
那我们的代码如何实现呢？如果我们要按如上的方法实现哈夫曼树，首先我们要找到的就是最小值，如何找到最小值一定是我们需要面对的最关键的问题。这里有2种方法：
1、先将所有的权值排序，如何再建立哈夫曼树。
2、先建立最小堆，每次从堆顶选元素来建立哈夫曼树。
遍历
二叉排序树的定义、构造及其遍历
定义
二叉排序树（Binary Sort Tree），又称二叉查找树（Binary Search Tree），亦称二叉搜索树。
二叉排序树或者是一棵空树，或者是具有下列性质的二叉树：
（1）若左子树不空，则左子树上所有结点的值均小于它的根结点的值；
（2）若右子树不空，则右子树上所有结点的值均大于它的根结点的值；
（3）左、右子树也分别为二叉排序树；
（4）没有键值相等的节点。
构造
假设我们要为数组 a[] = {10 ， 5 ， 15 ， 6 ， 4 ， 16 }构建一个二叉排序树，我们按顺序逐个插入元素
遍历
查找指定元素的节点（While循环)：
判断当前结点是否为空指针，不是空指针进入key直接和当前结点value相等，return当前结点key大于当前结点value，将右子节点赋予当前结点key小于当前结点value，将左子节点赋予当前结点直到key等于当前结点或者当前结点为空停止while循环
// NOIP2013普及组初赛#include <iostream>using namespace std;const int SIZE = 100;const int INFINITE = 1000000;struct node{int left_child, right_child, value;}a[SIZE];int is_bst( int root, int lower_bound, int upper_bound ){int cur;if (root == 0) return 1;cur = a[root].value;if ((cur > lower_bound) && (cur < upper_bound) &&(is_bst(a[root].left_child, lower_bound, cur) == 1) &&(is_bst(a[root].right_child, cur, upper_bound) == 1) )return 1;return 0;}int main(){int i, n;cin >> n;for (i = 1; i <= n; i++)cin >> a[i].value >> a[i].left_child >> a[i].right_child;cout << is_bst(1, -INFINITE, INFINITE) << endl;return 0;}
====Handbook部分=====
概念
注：先学习图，再学习树。
A tree is a connected, acyclic graph that consists of n nodes and n − 1 edges. Removing any edge from a tree divides it into two components, and adding any edge to a tree creates a cycle. Moreover, there is always a unique path between any two nodes of a tree.（树是图的一部分，连通的，无环，有n个顶点，n-1条边）
The leaves of a tree are the nodes with degree 1, i.e., with only one neighbor.
In a rooted tree, one of the nodes is appointed the root of the tree, and all other nodes are placed underneath the root. For example, in the following tree, node 1 is the root node.
In a rooted tree, the children of a node are its lower neighbors, and the parent of a node is its upper neighbor. Each node has exactly one parent, except for the root that does not have a parent. For example, in the above tree, the children of node 2 are nodes 5 and 6, and its parent is node 1.
The structure of a rooted tree is recursive: each node of the tree acts as the root of a subtree that contains the node itself and all nodes that are in the subtrees of its children. For example, in the above tree, the subtree of node 2 consists of nodes 2, 5, 6 and 8:
Tree traversal树的遍历
General graph traversal algorithms can be used to traverse the nodes of a tree. However, the traversal of a tree is easier to implement than that of a general graph, because there are no cycles in the tree and it is not possible to reach a node from multiple directions.
The typical way to traverse a tree is to start a depth-first search at an arbitrary node. The following recursive function can be used:
void dfs(int s, int e) { //e代表父亲节点// process node sfor (auto u : adj[s]) {if (u != e) dfs(u, s);}}
The function is given two parameters: the current node s and the previous node e. The purpose of the parameter e is to make sure that the search only moves to nodes that have not been visited yet.
//In the first call e = 0, because there is no previous node,//and it is allowed to proceed to any direction in the tree.dfs(x, 0);
Dynamic programming使用dp求子树大小
Dynamic programming can be used to calculate some information during a tree traversal. Using dynamic programming, we can, for example, calculate in O(n) time for each node of a rooted tree the number of nodes in its subtree or the length of the longest path from the node to a leaf.
As an example, let us calculate for each node s a value count[s]: the number of nodes in its subtree. The subtree contains the node itself and all nodes in the subtrees of its children, so we can calculate the number of nodes recursively using the following code:
void dfs(int s, int e) {count[s] = 1;for (auto u : adj[s]) {if (u == e) continue;dfs(u, s);count[s] += count[u];}}
Diameter树的直径
The diameter of a tree is the maximum length of a path between two nodes. Forexample, consider the following tree:
Note that there may be several maximum-length paths. In the above path, we could replace node 6 with node 5 to obtain another path with length 4.
Next we will discuss two O(n) time algorithms for calculating the diameter of a tree. The first algorithm is based on dynamic programming, and the second algorithm uses two depth-first searches.
Algorithm 1
A general way to approach many tree problems is to first root the tree arbitrarily. After this, we can try to solve the problem separately for each subtree. Our first algorithm for calculating the diameter is based on this idea.
An important observation is that every path in a rooted tree has a highest point: the highest node that belongs to the path. Thus, we can calculate for each node the length of the longest path whose highest point is the node. One of those paths corresponds to the diameter of the tree.
For example, in the following tree, node 1 is the highest point on the path that corresponds to the diameter:
We calculate for each node x two values:
- toLeaf(x): the maximum length of a path from x to any leaf
- maxLength(x): the maximum length of a path whose highest point is x
For example, in the above tree, toLeaf(1) = 2, because there is a path 1 → 2 → 6, and maxLength(1)=4, because there is a path 6→2→1→4→7. In this case, maxLength(1) equals the diameter.
Dynamic programming can be used to calculate the above values for all nodes in O(n) time. First, to calculate toLeaf(x), we go through the children of x, choose a child c with maximum toLeaf(c) and add one to this value. Then, to calculate maxLength(x), we choose two distinct children a and b such that the sum toLeaf(a) + toLeaf(b) is maximum and add two to this sum.
//类似floyd呢//还没实现过这种写法,要写一下
Algorithm 2 两次dfs
Another efficient way to calculate the diameter of a tree is based on two depth- first searches. First, we choose an arbitrary node a in the tree and find the farthest node b from a. Then, we find the farthest node c from b. The diameter of the tree is the distance between b and c.
In the following graph, a, b and c could be:
This is an elegant method, but why does it work?
It helps to draw the tree differently so that the path that corresponds to the diameter is horizontal, and all other nodes hang from it:
Node x indicates the place where the path from node a joins the path that corresponds to the diameter. The farthest node from a is node b, node c or some other node that is at least as far from node x. Thus, this node is always a valid choice for an endpoint of a path that corresponds to the diameter.
//这个更好实现，就是跑两遍dfs#include <bits/stdc++.h>using namespace std;const int N = 100010;int h[N], e[N * 2], ne[N * 2], w[N * 2], idx;int dep[N];int T, n;int num, maxn;void add(int a, int b, int c){e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx++;}void dfs(int u, int fa){if (dep[u] > maxn) maxn = dep[u], num = u;for (int i = h[u]; i != -1; i = ne[i]){int j = e[i];if (j == fa) continue;dep[j] = dep[u] + w[i];dfs(j, u);}}int main(){scanf("%d", &T);for (int id = 1; id <= T; id++){memset(h, -1, sizeof h);idx = 0;scanf("%d", &n);for (int i = 0; i < n - 1; i++){int a, b, w;scanf("%d%d%d", &a, &b, &w);a++, b++;add(a, b, w);add(b, a, w);}maxn = 0;memset(dep, 0, sizeof dep);dfs(1, 0);maxn = 0;memset(dep, 0, sizeof dep);dfs(num, 0);printf("Case %d: %d\n", id, maxn);}return 0;}
Binary trees二叉树
A binary tree is a rooted tree where each node has a left and right subtree. It is possible that a subtree of a node is empty. Thus, every node in a binary tree has zero, one or two children.
For example, the following tree is a binary tree:
The nodes of a binary tree have three natural orderings that correspond to different ways to recursively traverse the tree:
- pre-order: first process the root, then traverse the left subtree, then traverse the right subtree
- in-order: first traverse the left subtree, then process the root, then traverse the right subtree
- post-order: first traverse the left subtree, then traverse the right subtree, then process the root
For the above tree, the nodes in pre-order are [1,2,4,5,6,3,7], in in-order [4,2,6,5,1,3,7] and in post-order [4,6,5,2,7,3,1].
If we know the pre-order and in-order of a tree, we can reconstruct the exact structure of the tree. For example, the above tree is the only possible tree with pre-order [1, 2, 4, 5, 6, 3, 7] and in-order [4, 2, 6, 5, 1, 3, 7]. In a similar way, the post-order and in-order also determine the structure of a tree.
However, the situation is different if we only know the pre-order and post- order of a tree. In this case, there may be more than one tree that match the orderings. For example, in both of the trees the pre-order is [1,2] and the post-order is [2,1], but the structures of the trees are different.
一本通中有很多针对二叉树的题目，都是使用the technique of recursion，NOIP真题中有多道类似的题目，需要多加练习。
《一本通》题目
【例3-1】找树根和孩子
//fa[N]维护每个结点的父亲，如果一个节点没有fa，他就是根//son[N]维护孩子个数
【例3-2】单词查找树
//trie树，可以高效的存储和查找字符串
【例3-3】医院设置
//floyd维护出任意两点的距离//枚举医院的位置，更新res
【例3-4】求后序遍历
//给出先序和中序，求后续void dfs(int l1, int r1, int l2, int r2)//根据先序l1位置的根，去找中序中根的位置
【例3-5】扩展二叉树
//给出扩展二叉树的先序序列，输出中序和后序//题解给出的是指针写法【指针】
小球(drop)
//起初所有节点都是false，访问这个点就会设置成相反状态//求第i个小球停在哪个叶子结点上//方法1，模拟1...i个小球的下落过程//方法2，根据左儿子pos*2，右儿子pos*2+1//开一个一维数组，维护结点的true和false
二叉树遍历(flist)
//给出中序序列和按层序列，求先序序列//在按层遍历序列中先遇到根，在中序序列中，找到根的位置，break出来//进行递归处理void dfs(int l1, int r1, int l2, int r2)
FBI树(fbi)
void dfs(int l, int r){//边界//子问题int len = (r - l) / 2;dfs(l, l + len);dfs(l + len + 1, r);//按题意模拟操作}
二叉树输出(btout)
//给出先序和中序，求凹入表示int dfs(int l1, int r1, int l2, int r2)//照样递归下去，dfs返回的是子树大小，用son[N]维护每个结点的子树大小
查找二叉树(tree_a)
//题意是，中序遍历的顺序，值为target的结点是第几个被遍历到的
对称二叉树(tree_c)
//思路1，从s[1]开始，两两为一单位，要么都是#，要么都不是#//思路2，根据左儿子和右儿子的位置，去判断左右儿子要么同时为#，要么同时不是#//两个思路，都需要在读入的字符串后面加上一个#，避免最后一个叶子结点没有兄弟的情况
合并果子(fruit)
//小根堆
最小函数值(minval)
//用一个大根堆，维护前m个较小值//如果堆的大小>=m，新读入的数字，比堆顶小，就更新维护进来
看病
//priority_queue<node> q;自定义结构体使用优先队列
小明的账单
//每天付最大账单和最小账单//使用multiset维护
鱼塘钓鱼(fishing）
//这道题目的处理思路，在另外一个题目也遇到过//类似的操作是，把路程消耗先消耗掉，然后就可以看做随意跳来跳去的//枚举最远走到的池塘位置，先把路上消耗的时间先减去//然后就可以看做已经走过的池塘，可以任意流窜//把已经走过的池塘，每一分钟可以钓的鱼，维护到一个大根堆中//然后就变成，有限的时间，取有限次，每次都是取最大值(greedy)
若有收获，就点个赞吧
0 人点赞
