DSA 问题集第五章

数据结构问题集第五章。
今天考微积分，又是出考场发现写错一题让人不禁怀疑考场是不是风水不太好。毕竟上学期期中也是在这间考的。
woc 逆天一直以为寝室里的烟味是楼下还是楼上烧什么东西导致的结果是我亲爱的室友拉了窗帘在阳台抽烟。md 要吸一个学期的二手烟了。不生气不生气。

1: 可加性好，两条路径拼接长度是两条路径各自和。

2: 取 v 子树中最矮节点 u，depth (v)+height (v)=depth (u)，而 height (T) 定义为最长路径

v 在最长路径上

父节点 - 孩子节点表示：a) 层层上溯，O (h) b) 设置 parent 和 child，O (1) c) 递归删除子树，然后从父亲的儿子列表中删除 d) 两个节点同时上溯，得到高度差。对齐高度后同步移动直到汇合, O (h)。

不能。经过长子 - 兄弟变换的多叉树的根节点只有左儿子，如果二叉树的根节点有两个儿子就必然被还原成森林。

森林 -> 二叉树：空森林对应空二叉树。森林 ${T_1,…,T_n}$，用 $T_1$ 的根节点作为二叉树根，用长子 - 兄弟变换递归产生左子树，${T_2,…,T_n}$ 用长子 - 兄弟变换递归产生右子树

二叉树 -> 森林：空二叉树对应空森林。根节点的左子树的右侧藤蔓作为根的儿子们，右藤蔓连着的左子树递归形成儿子的儿子们，于是递归产生了 $T_1$，右子树递归产生剩余树。

不会变化。如果发现有个祖先的高度没有变化就终止递归。

全是右子树；全是左子树。

可以。表达式栈中，每遇到一个运算符，一元弹出一个随便挂左边右边；二元就弹出两个元素，先 a 后 b，把运算符做根，a 为右子树，b 为左子树，这样的树放回栈中。

a) 每次筛出右藤蔓，把右藤蔓所有点入栈；然后转向左儿子（如果有）。可以进一步美化成访问当前节点，然后依次把右儿子、左儿子入栈，不断从栈顶取节点直到栈空。

template <typename T, typename V> 
void preorder_right_vine(BinNodePosi<T> x, V& visit) {
    Stack<BinNodePosi<T>> S;
    if (x) S.push(x);
    while (!S.empty()) {
        x = S.pop();
        visit(x->data);
        
        // 关键点：分解右侧通路
        if (x->rc) S.push(x->rc); // 将右孩子（右侧通路的延伸）压入栈底挂起
        if (x->lc) S.push(x->lc); // 将左孩子压入栈顶，保证下一步立即执行
    }
}

a) 空树成立。假设对规模 n-1 成立，考查对 n 是否成立。找到左侧藤蔓的末端 u，至少有一个点。访问过程：T：在藤蔓上移动；U：访问 u；Rn,…,R1：递归访问右子树。每个阶段规模不超过 n-1 对每个阶段都能正确得到先序遍历结果，合起来是 $v_1,v_2,…,u,Pre (R_n),…,Pre (R_1)$ 也是正确的。

b) 不行。右子树的藤蔓长度不一定小于原树藤蔓长度。

空间复杂度由藤蔓长度决定。藤蔓有多长就有多少个右节点需要入栈，而且是可以累计的，即如当前访问到节点 v，它的左藤蔓前面的节点的右儿子目前都在栈中，直到左藤蔓头部是个右儿子；它的父亲所在的左藤蔓前面的节点的右儿子目前也在栈中。。。于是 v 所有的左祖先的右儿子都在栈中，而且除此之外没有其他元素。

如果是左藤蔓上的点，给一块钱，在访问的时候花掉；如果是右儿子的点，给两块钱，入栈一块出栈一块。总共不超过 2n，于是 O (n)

显然

中序不行。

先序可以考虑一趟扫描，放栈里，遇到两个 ^^ 就把前一个元素拿出来和这两个组装一个” 叶子 “节点，然后替换成 ^，不断组装。

预排序：O (nlogn)，全部按顺序压栈。

创建空队列比较栈顶和队头的大小，找到最大元素；比较新栈顶和新队头的大小，找到第二大元素，合并后推到队尾。

平均时间复杂度 = 平均查找长度

$N=n!,D_{avg}=\frac{1}{N}\sum^{N_{i = 1} d_i, 定义 E (N)=\sum}N_{i=1}d_i$

$E (N)=E (N - L)+E (L)+N (两边子树接入根节点，所有节点深度 + 1)$

为使得 E (N) 最小，应该是完全二叉树。取 L = 1 / 2N

$E(N)=2E(N/2)+N,E(N)=O(NlogN)$

$D_{avg}=O(logN)=O(nlogn)$

W：排序算法。构造字符集，权重为 $M^{x_i}$，M 是足够大的数。

于是必然存在 M 使得最优编码树是一个藤蔓，从底向上已经排序了权重。

还原到 x_i 即可。