目录1.设计一个分治算法来计算二叉树的层数(具体来说对于空树和单节点树该算法应该分别返回0和1)。这个算法的效率类型是怎样的?2.下列算法试图计算一棵二叉树的叶子数。3.计算一棵二叉树的高度在不显式或隐式使用堆栈的情况下确保其与本节的分治算法有相同的渐近效率。当然你也可以使用不同的算法。4.用数学归纳法证明式(5.2)。5.遍历下面的二叉树6.选择一个二叉树的经典遍历算法(前序、中序和后序)写出它的伪代码。假设该算法是一个递归算法求它的递归调用次数。7.应用三种经典遍历算法的哪一种在遍历一棵二叉查找树时会产生一个有序列表请给出证明8.a.画出一棵10节点的二叉树节点分别标为012…9如何排列才能让它的中序遍历和后序遍历分别生成以下列表9310427685(中序)和9140367582(后序)?b.对于同样n个标为012…n-1的节点组成的二叉树来说请给出两个排列它们不可能是同一棵二叉树的中序和后序遍历列表。c.设计一个算法它能根据二叉树的中序和后序遍历列表构造该树。列表是由n个标为012…n-1的节点构成的。这个算法对无解的输入也应正确识别。9.我们把一棵扩展二叉树的内部路径长度(internal path length)I定义为连接根到每个内部节点的路径长度的总和。简单起见我们把一棵扩展二叉树的外部路径长度(external path length)E定义为连接根到每个外部节点的路径长度的总和。请证明EI2n n是该树的内部节点的个数。10.编写一个程序用于计算一棵二叉查找树的内部路径长度。使用该程序对检索一棵随机二叉查找树时的平均键值比较次数做一个实证研究。11.巧克力块谜题 有一块n×m格的巧克力我们要把它掰成n×m个1×1的小块。我们只能沿直线掰而且不能几块同时掰。设计一个算法用最少的次数掰完巧克力该次数是多少用二叉树的特性来论证答案。1.设计一个分治算法来计算二叉树的层数(具体来说对于空树和单节点树该算法应该分别返回0和1)。这个算法的效率类型是怎样的?把树分成左子树和右子树递归求两边层数当前树层数 左右最大层数 1。算法TreeHeight(T) // 输入二叉树 T 的根节点 // 输出树的层数空树0单节点1 if T null then // 空树 return 0 else leftHeight TreeHeight(T.left) // 分递归左子树 rightHeight TreeHeight(T.right) // 分递归右子树 // 治取最大 1 return max(leftHeight, rightHeight) 1时间效率是Θ(n)2.下列算法试图计算一棵二叉树的叶子数。算法 LeafCounter(T) //递归计算二叉树的叶子数 //输入一棵二叉树T //输出T的叶子数 if T∅ return 0 else return LeafCounter(Tleft)LeafCounter(TRight)该算法正确吗如果正确请证明否则请改正。错误正确应该是空树返回 0叶子节点返回 1否则返回左 右叶子数效率 Θ(n)算法 LeafCounter(T) // 递归计算二叉树的叶子数 // 输入二叉树 T // 输出T 的叶子节点总数 if T ∅ // 空树 return 0 else if T.left ∅ 且 T.right ∅ // 真正的叶子节点无子节点 return 1 else return LeafCounter(T.left) LeafCounter(T.right)3.计算一棵二叉树的高度在不显式或隐式使用堆栈的情况下确保其与本节的分治算法有相同的渐近效率。当然你也可以使用不同的算法。用队列进行层次遍历每遍历完一层高度 1最后得到树高。算法 TreeHeightNonRecursive(T) // 非递归、无栈、求二叉树高度 // 效率Θ(n)与分治算法相同 if T ∅ then return 0 // 空树高度0 创建队列 Q 根节点入队 Q height 0 // 高度初始化为0 while Q 不为空 do levelSize 队列中元素个数 // 当前层的节点数 height height 1 // 遍历一层高度1 // 遍历当前所有节点 for i 1 to levelSize do 出队一个节点 node if node.left ≠ ∅ then 左孩子入队 if node.right ≠ ∅ then 右孩子入队 return height4.用数学归纳法证明式(5.2)。设n内部结点个数x外部结点个数对任意扩展二叉树xn1当 n0空树内部结点数 n0外部结点数 x1定义满足x011假设对所有满足 0kn 的 k公式都成立x_kk1即任意少于 n 个内部结点的扩展二叉树外结点数 内结点数 1。设树 T 有n 个内部结点。将 T 分为左子树nL 个内部结点xL 个外部结点右子树nR 个内部结点xR 个外部结点显然nnLnR1根结点 左内部 右内部因为 nLnnRn根据归纳假设xLnL1,xRnR1整棵树的外部结点总数xxLxR(nL1)(nR1)(nLnR1)1n1公式对 n 成立。5.遍历下面的二叉树a.用前序法 b.用中序法 c.用后序法a. Preorder: a b d e c fb. Inorder: d b e a c fc. Postorder: d e b f c a6.选择一个二叉树的经典遍历算法(前序、中序和后序)写出它的伪代码。假设该算法是一个递归算法求它的递归调用次数。算法 Inorder(T) // 递归中序遍历二叉树 T if T ≠ ∅ then Inorder(T.left) // 递归左子树 访问 T 的根节点 Inorder(T.right) // 递归右子树设二叉树有n 个节点,总递归调用次数 2n 1 次7.应用三种经典遍历算法的哪一种在遍历一棵二叉查找树时会产生一个有序列表请给出证明左子树 → 根 → 右子树基例若树只有一个节点中序遍历输出该节点显然有序。归纳假设假设所有节点数少于 n 的 BST中序遍历都输出递增序列。归纳步骤设 BST 有 n 个节点先遍历左子树输出小于根的递增序列然后输出根最后遍历右子树输出大于根的递增序列组合起来就是左递增序列 根 右递增序列→整体递增有序8.a.画出一棵10节点的二叉树节点分别标为012…9如何排列才能让它的中序遍历和后序遍历分别生成以下列表9310427685(中序)和9140367582(后序)?已知中序9, 3, 1, 0, 4, 2, 7, 6, 8, 5后序9, 1, 4, 0, 3, 6, 7, 5, 8, 2后序最后一个 根在中序里找到根左边是左子树右边是右子树递归重复最终树为2 / \ 3 8 / \ / \ 9 0 7 5 / \ 1 4b.对于同样n个标为012…n-1的节点组成的二叉树来说请给出两个排列它们不可能是同一棵二叉树的中序和后序遍历列表。中序2, 0, 1后序0, 1, 2c.设计一个算法它能根据二叉树的中序和后序遍历列表构造该树。列表是由n个标为012…n-1的节点构成的。这个算法对无解的输入也应正确识别。算法 BuildTree(inOrder, postOrder, inStart, inEnd, postIdx) if inStart inEnd return null // 后序最后一个是根 val postOrder[postIdx] 创建节点 node(val) postIdx postIdx - 1 // 在中序里找根位置 mid mid 查找 inOrder 中 val 的下标 // 先构造右子树因为后序顺序左 → 右 → 根 node.right BuildTree(inOrder, postOrder, mid1, inEnd, postIdx) node.left BuildTree(inOrder, postOrder, inStart, mid-1, postIdx) return node9.我们把一棵扩展二叉树的内部路径长度(internal path length)I定义为连接根到每个内部节点的路径长度的总和。简单起见我们把一棵扩展二叉树的外部路径长度(external path length)E定义为连接根到每个外部节点的路径长度的总和。请证明EI2n n是该树的内部节点的个数。当n0空树只有 1 个外部节点I 0E 0公式000成立假设对于所有少于 n 个内部节点的扩展二叉树公式都成立E′I′2n′设一棵二叉树 T 有n 个内部节点根为 r。左子树nL 内点路径长 IL、EL右子树nR 内点路径长 IR、ER显然nnLnR1内部路径长度外部路径长度代入 E公式成立。10.编写一个程序用于计算一棵二叉查找树的内部路径长度。使用该程序对检索一棵随机二叉查找树时的平均键值比较次数做一个实证研究。#include stdio.h #include stdlib.h #include time.h typedef struct Node { int key; struct Node *left, *right; } Node; // 创建节点 Node* newNode(int item) { Node* temp (Node*)malloc(sizeof(Node)); temp-key item; temp-left temp-right NULL; return temp; } // 插入 BST Node* insert(Node* node, int key) { if (node NULL) return newNode(key); if (key node-key) node-left insert(node-left, key); else node-right insert(node-right, key); return node; } // 计算内部路径长度递归 int internalPathLength(Node* root, int depth) { if (root NULL) return 0; // 当前节点深度 左 右 return depth internalPathLength(root-left, depth1) internalPathLength(root-right, depth1); } // 随机生成 BST 并测试 int main() { srand(time(0)); int n 10000; // 节点数 Node* root NULL; // 随机插入 for (int i0; in; i) { root insert(root, rand()); } int I internalPathLength(root, 0); double avg (double)I / n; printf(内部路径长度 I %d\n, I); printf(平均比较次数 ≈ %.2f\n, avg); return 0; }11.巧克力块谜题 有一块n×m格的巧克力我们要把它掰成n×m个1×1的小块。我们只能沿直线掰而且不能几块同时掰。设计一个算法用最少的次数掰完巧克力该次数是多少用二叉树的特性来论证答案。最少次数 n × m − 1把掰巧克力过程建模为扩展二叉树每次掰 一个内部节点最终 1×1 小块 外部节点总块数 外部节点数 xn×m已知公式x n 1→ 内部节点数 外部节点数 − 1→掰的次数 n×m − 1
算法设计与分析-习题5.3
目录1.设计一个分治算法来计算二叉树的层数(具体来说对于空树和单节点树该算法应该分别返回0和1)。这个算法的效率类型是怎样的?2.下列算法试图计算一棵二叉树的叶子数。3.计算一棵二叉树的高度在不显式或隐式使用堆栈的情况下确保其与本节的分治算法有相同的渐近效率。当然你也可以使用不同的算法。4.用数学归纳法证明式(5.2)。5.遍历下面的二叉树6.选择一个二叉树的经典遍历算法(前序、中序和后序)写出它的伪代码。假设该算法是一个递归算法求它的递归调用次数。7.应用三种经典遍历算法的哪一种在遍历一棵二叉查找树时会产生一个有序列表请给出证明8.a.画出一棵10节点的二叉树节点分别标为012…9如何排列才能让它的中序遍历和后序遍历分别生成以下列表9310427685(中序)和9140367582(后序)?b.对于同样n个标为012…n-1的节点组成的二叉树来说请给出两个排列它们不可能是同一棵二叉树的中序和后序遍历列表。c.设计一个算法它能根据二叉树的中序和后序遍历列表构造该树。列表是由n个标为012…n-1的节点构成的。这个算法对无解的输入也应正确识别。9.我们把一棵扩展二叉树的内部路径长度(internal path length)I定义为连接根到每个内部节点的路径长度的总和。简单起见我们把一棵扩展二叉树的外部路径长度(external path length)E定义为连接根到每个外部节点的路径长度的总和。请证明EI2n n是该树的内部节点的个数。10.编写一个程序用于计算一棵二叉查找树的内部路径长度。使用该程序对检索一棵随机二叉查找树时的平均键值比较次数做一个实证研究。11.巧克力块谜题 有一块n×m格的巧克力我们要把它掰成n×m个1×1的小块。我们只能沿直线掰而且不能几块同时掰。设计一个算法用最少的次数掰完巧克力该次数是多少用二叉树的特性来论证答案。1.设计一个分治算法来计算二叉树的层数(具体来说对于空树和单节点树该算法应该分别返回0和1)。这个算法的效率类型是怎样的?把树分成左子树和右子树递归求两边层数当前树层数 左右最大层数 1。算法TreeHeight(T) // 输入二叉树 T 的根节点 // 输出树的层数空树0单节点1 if T null then // 空树 return 0 else leftHeight TreeHeight(T.left) // 分递归左子树 rightHeight TreeHeight(T.right) // 分递归右子树 // 治取最大 1 return max(leftHeight, rightHeight) 1时间效率是Θ(n)2.下列算法试图计算一棵二叉树的叶子数。算法 LeafCounter(T) //递归计算二叉树的叶子数 //输入一棵二叉树T //输出T的叶子数 if T∅ return 0 else return LeafCounter(Tleft)LeafCounter(TRight)该算法正确吗如果正确请证明否则请改正。错误正确应该是空树返回 0叶子节点返回 1否则返回左 右叶子数效率 Θ(n)算法 LeafCounter(T) // 递归计算二叉树的叶子数 // 输入二叉树 T // 输出T 的叶子节点总数 if T ∅ // 空树 return 0 else if T.left ∅ 且 T.right ∅ // 真正的叶子节点无子节点 return 1 else return LeafCounter(T.left) LeafCounter(T.right)3.计算一棵二叉树的高度在不显式或隐式使用堆栈的情况下确保其与本节的分治算法有相同的渐近效率。当然你也可以使用不同的算法。用队列进行层次遍历每遍历完一层高度 1最后得到树高。算法 TreeHeightNonRecursive(T) // 非递归、无栈、求二叉树高度 // 效率Θ(n)与分治算法相同 if T ∅ then return 0 // 空树高度0 创建队列 Q 根节点入队 Q height 0 // 高度初始化为0 while Q 不为空 do levelSize 队列中元素个数 // 当前层的节点数 height height 1 // 遍历一层高度1 // 遍历当前所有节点 for i 1 to levelSize do 出队一个节点 node if node.left ≠ ∅ then 左孩子入队 if node.right ≠ ∅ then 右孩子入队 return height4.用数学归纳法证明式(5.2)。设n内部结点个数x外部结点个数对任意扩展二叉树xn1当 n0空树内部结点数 n0外部结点数 x1定义满足x011假设对所有满足 0kn 的 k公式都成立x_kk1即任意少于 n 个内部结点的扩展二叉树外结点数 内结点数 1。设树 T 有n 个内部结点。将 T 分为左子树nL 个内部结点xL 个外部结点右子树nR 个内部结点xR 个外部结点显然nnLnR1根结点 左内部 右内部因为 nLnnRn根据归纳假设xLnL1,xRnR1整棵树的外部结点总数xxLxR(nL1)(nR1)(nLnR1)1n1公式对 n 成立。5.遍历下面的二叉树a.用前序法 b.用中序法 c.用后序法a. Preorder: a b d e c fb. Inorder: d b e a c fc. Postorder: d e b f c a6.选择一个二叉树的经典遍历算法(前序、中序和后序)写出它的伪代码。假设该算法是一个递归算法求它的递归调用次数。算法 Inorder(T) // 递归中序遍历二叉树 T if T ≠ ∅ then Inorder(T.left) // 递归左子树 访问 T 的根节点 Inorder(T.right) // 递归右子树设二叉树有n 个节点,总递归调用次数 2n 1 次7.应用三种经典遍历算法的哪一种在遍历一棵二叉查找树时会产生一个有序列表请给出证明左子树 → 根 → 右子树基例若树只有一个节点中序遍历输出该节点显然有序。归纳假设假设所有节点数少于 n 的 BST中序遍历都输出递增序列。归纳步骤设 BST 有 n 个节点先遍历左子树输出小于根的递增序列然后输出根最后遍历右子树输出大于根的递增序列组合起来就是左递增序列 根 右递增序列→整体递增有序8.a.画出一棵10节点的二叉树节点分别标为012…9如何排列才能让它的中序遍历和后序遍历分别生成以下列表9310427685(中序)和9140367582(后序)?已知中序9, 3, 1, 0, 4, 2, 7, 6, 8, 5后序9, 1, 4, 0, 3, 6, 7, 5, 8, 2后序最后一个 根在中序里找到根左边是左子树右边是右子树递归重复最终树为2 / \ 3 8 / \ / \ 9 0 7 5 / \ 1 4b.对于同样n个标为012…n-1的节点组成的二叉树来说请给出两个排列它们不可能是同一棵二叉树的中序和后序遍历列表。中序2, 0, 1后序0, 1, 2c.设计一个算法它能根据二叉树的中序和后序遍历列表构造该树。列表是由n个标为012…n-1的节点构成的。这个算法对无解的输入也应正确识别。算法 BuildTree(inOrder, postOrder, inStart, inEnd, postIdx) if inStart inEnd return null // 后序最后一个是根 val postOrder[postIdx] 创建节点 node(val) postIdx postIdx - 1 // 在中序里找根位置 mid mid 查找 inOrder 中 val 的下标 // 先构造右子树因为后序顺序左 → 右 → 根 node.right BuildTree(inOrder, postOrder, mid1, inEnd, postIdx) node.left BuildTree(inOrder, postOrder, inStart, mid-1, postIdx) return node9.我们把一棵扩展二叉树的内部路径长度(internal path length)I定义为连接根到每个内部节点的路径长度的总和。简单起见我们把一棵扩展二叉树的外部路径长度(external path length)E定义为连接根到每个外部节点的路径长度的总和。请证明EI2n n是该树的内部节点的个数。当n0空树只有 1 个外部节点I 0E 0公式000成立假设对于所有少于 n 个内部节点的扩展二叉树公式都成立E′I′2n′设一棵二叉树 T 有n 个内部节点根为 r。左子树nL 内点路径长 IL、EL右子树nR 内点路径长 IR、ER显然nnLnR1内部路径长度外部路径长度代入 E公式成立。10.编写一个程序用于计算一棵二叉查找树的内部路径长度。使用该程序对检索一棵随机二叉查找树时的平均键值比较次数做一个实证研究。#include stdio.h #include stdlib.h #include time.h typedef struct Node { int key; struct Node *left, *right; } Node; // 创建节点 Node* newNode(int item) { Node* temp (Node*)malloc(sizeof(Node)); temp-key item; temp-left temp-right NULL; return temp; } // 插入 BST Node* insert(Node* node, int key) { if (node NULL) return newNode(key); if (key node-key) node-left insert(node-left, key); else node-right insert(node-right, key); return node; } // 计算内部路径长度递归 int internalPathLength(Node* root, int depth) { if (root NULL) return 0; // 当前节点深度 左 右 return depth internalPathLength(root-left, depth1) internalPathLength(root-right, depth1); } // 随机生成 BST 并测试 int main() { srand(time(0)); int n 10000; // 节点数 Node* root NULL; // 随机插入 for (int i0; in; i) { root insert(root, rand()); } int I internalPathLength(root, 0); double avg (double)I / n; printf(内部路径长度 I %d\n, I); printf(平均比较次数 ≈ %.2f\n, avg); return 0; }11.巧克力块谜题 有一块n×m格的巧克力我们要把它掰成n×m个1×1的小块。我们只能沿直线掰而且不能几块同时掰。设计一个算法用最少的次数掰完巧克力该次数是多少用二叉树的特性来论证答案。最少次数 n × m − 1把掰巧克力过程建模为扩展二叉树每次掰 一个内部节点最终 1×1 小块 外部节点总块数 外部节点数 xn×m已知公式x n 1→ 内部节点数 外部节点数 − 1→掰的次数 n×m − 1
