sheet:Tree

Tree #

• luogu1305 练习先序遍历，使用数组存储左右节点。
• uva536 从先序和中序推出后序，不重建树结构。
• uva548 从中序和后序构建树，并找出路径权值最小的叶子节点。中等难度。

Huffman #

• poj3253 Huffman树的思路，使用priority_queue。
• poj1521 Huffman树，直接计算字符串的编码长度，无需对字符串逐个编码。
• uva12676 从每个字符Huffman编码的长度，反推字符串的最少字符数。
• uva240 可变基Huffman编码，要求输出每个编码，需要保存父子关系，对编码的次序有要求。需要多个数组，数据结构较复杂。

二叉搜索树 #

• bailian1577(Falling Leaves) 练习创建二叉搜索树，并先序遍历。
• bailian2309(BST) 分析完全二叉搜索树与二进制的对应关系。
• poj3481(Double Queue) AVL实现 使用cstdio，练习实现AVL。

最近公共祖先 #

• bailian1330(Nearest Common Ancestors) 暴力搜索，向上标记法，模板题。
• hdu2586(How far away) 树上距离从题意中分析出数据结构为树，而不是图。用ST表，树上倍增，找出LCA，进而得到树上距离。
• bailian1986(Distance Queries) Tarjan算法实现离线LCA查询，Edge类有双重含义，一是作为图的边，二是作为查询。使用了两重的链式前向星在同一个类中。数据结构较复杂。
• hdu2874(Connections between cities) 使用Tarjan算法，由于可能出现树林，需要在tarjan函数中添加root参数。测试数据量大，需要使用 优化大量整数的读入。

重心 #

• cf685B(Kay and Snowflake) 一次递归求出所有子树的重心。若y是x的孩子，且y的重心为p，则x的重心必在p到x的路径上。

直径 #

• luoguB4016(树的直径) 练习计算树的直径，用动态规划实现。
• luogu3629(巡逻) 先用BFS求直径，然后将直径上的边的权重设置为-1，再用DP求直径。分析较难。
• luogu1099(树网的核) 两次BFS求出直径，再求树上节点为根的子树的最长距离，最后计算偏心距。

Links #