网站建设影音先锋网址修改wordpress页脚信息

网站建设影音先锋网址,修改wordpress页脚信息,教育培训类网站设计,网络推广怎么做树 结点的度#xff1a;是指该结点的孩子数量 \begin{aligned} \textbf{结点的度}#xff1a;\text{是指该结点的孩子数量} \end{aligned} ​结点的度#xff1a;是指该结点的孩子数量​路径和路径长度#xff1a;树中两个结点之间的路径是由这两个结点之间所经过的结…树结点的度是指该结点的孩子数量 \begin{aligned} \textbf{结点的度}\text{是指该结点的孩子数量} \end{aligned}​结点的度是指该结点的孩子数量​路径和路径长度树中两个结点之间的路径是由这两个结点之间所经过的结点序列构成的而路径长度是路径上所经过的边的个数。 \begin{aligned} \textbf{路径和路径长度} \\ \quad \text{树中两个结点之间的路径是由这两个结点之间所经过的结点序列构成的而路径长度是} \\ \quad \text{路径上所经过的边的个数。} \end{aligned}​路径和路径长度树中两个结点之间的路径是由这两个结点之间所经过的结点序列构成的而路径长度是路径上所经过的边的个数。​树中一个结点的孩子个数称为该结点的度树中结点的最大度数称为树的度 \begin{aligned} \text{树中一个结点的孩子个数称为该结点的度树中结点的最大度数称为树的度} \end{aligned}​树中一个结点的孩子个数称为该结点的度树中结点的最大度数称为树的度​​树结点总数树的总度数1​ ​树结点总数树的总度数1​​树结点总数树的总度数1​森林是 m (m≥0) 棵互不相交的树的集合。森林的概念与树的概念十分相近因为只要把树的根结点删去就成了森林。反之只要给 m 棵独立的树加上一个结点并把这 m 棵树作为该结点的子树则森林就变成了树。 \begin{aligned} \textbf{森林} \text{是} \ m \ (m \geq 0) \ \text{棵互不相交的树的集合。森林的概念与树的概念十分相近因为只要} \\ \text{把树的根结点删去就成了森林。反之只要给} \ m \ \text{棵独立的树加上一个结点并把这} \ m \ \text{棵} \\ \text{树作为该结点的子树则森林就变成了树。} \end{aligned}​森林是m(m≥0)棵互不相交的树的集合。森林的概念与树的概念十分相近因为只要把树的根结点删去就成了森林。反之只要给m棵独立的树加上一个结点并把这m棵树作为该结点的子树则森林就变成了树。​至少有一个结点度为2二叉树是一种特殊的树形结构其特点是每个结点至多只有两棵子树二叉树中不存在度大于2的结点并且二叉树的子树有左右之分其次序不能任意颠倒 \begin{aligned} \\ \quad \boldsymbol{\text{至少有一个结点度为2}} \\ \\ \textbf{二叉树} \text{是一种特殊的树形结构其特点是每个结点至多只有两棵子树二叉树中不存在度大} \\ \text{于2的结点并且二叉树的子树有左右之分其次序不能任意颠倒} \end{aligned}​至少有一个结点度为2二叉树是一种特殊的树形结构其特点是每个结点至多只有两棵子树二叉树中不存在度大于2的结点并且二叉树的子树有左右之分其次序不能任意颠倒​一颗高度为h的完全二叉树叶结点只有可能出现在第h层或第h−1层n0n21n11 或 n10完全二叉树编号的性质 \begin{aligned} \textbf{一颗高度为} h \textbf{的完全二叉树叶结点只有可能出现在第} h \textbf{层或第} h-1 \textbf{层} \\ \\ n_0 n_2 1 \quad\quad n_1 1 \ \text{或} \ n_1 0 \\ \\ \textbf{完全二叉树编号的性质} \end{aligned}​一颗高度为h的完全二叉树叶结点只有可能出现在第h层或第h−1层n0​n2​1n1​1或n1​0完全二叉树编号的性质​高度为h的完全二叉树前h−1层一定是满二叉树 \begin{aligned} \textbf{高度为} h \textbf{的完全二叉树前} h-1 \textbf{层一定是满二叉树} \end{aligned}​高度为h的完全二叉树前h−1层一定是满二叉树​由完全二叉树的性质编号为 i (i≥1) 的结点所在的层次为 ⌊log⁡2i⌋1,具有 n 个 (n0) 结点的完全二叉树的高度为 ⌈log⁡2(n1)⌉ 或 ⌊log⁡2n⌋1。设高度为 h根据性质3和完全二叉树的定义有2h−1−1n≤2h−1或者2h−1≤n2h得 2h−1n1≤2h即 h−1log⁡2(n1)≤h因为 h 为正整数所以 h⌈log⁡2(n1)⌉或者得 h−1≤log⁡2nh所以 h⌊log⁡2n⌋1。 \begin{aligned} \textbf{由完全二叉树的性质编号为} \ i \ (i \geq 1) \ \textbf{的结点所在的层次为} \ \lfloor \log_2 i \rfloor 1, \\ \\ \text{具有} \ n \ \text{个} \ (n 0) \ \text{结点的完全二叉树的高度为} \ \lceil \log_2(n 1) \rceil \ \text{或} \ \lfloor \log_2 n \rfloor 1。 \\ \text{设高度为} \ h\text{根据性质3和完全二叉树的定义有} \\ \quad 2^{h-1} - 1 n \leq 2^h - 1 \quad \text{或者} \quad 2^{h-1} \leq n 2^h \\ \text{得} \ 2^{h-1} n 1 \leq 2^h\text{即} \ h - 1 \log_2(n 1) \leq h\text{因为} \ h \ \text{为正整数所以} \ h \lceil \log_2(n 1) \rceil \\ \text{或者得} \ h - 1 \leq \log_2 n h\text{所以} \ h \lfloor \log_2 n \rfloor 1。 \end{aligned}​由完全二叉树的性质编号为i(i≥1)的结点所在的层次为⌊log2​i⌋1,具有n个(n0)结点的完全二叉树的高度为⌈log2​(n1)⌉或⌊log2​n⌋1。设高度为h根据性质3和完全二叉树的定义有2h−1−1n≤2h−1或者2h−1≤n2h得2h−1n1≤2h即h−1log2​(n1)≤h因为h为正整数所以h⌈log2​(n1)⌉或者得h−1≤log2​nh所以h⌊log2​n⌋1。​交换一颗二叉树的左右子树之后原来的升序序列就会变成降序序列 \begin{aligned} \textbf{交换一颗二叉树的左右子树之后原来的升序序列就会变成降序序列} \end{aligned}​交换一颗二叉树的左右子树之后原来的升序序列就会变成降序序列​传统的二叉链表存储仅能体现一种父子关系不能直接得到结点在遍历中的前驱或后继。前面提到在含n 个结点的二叉树中有n1 个空指针。这是因为每个叶结点都有2个空指针每个度为1的结点都有1个空指针空指针总数为2n0n1又n0n21所以空指针总数为n0n1n21n1。由此设想能否利用这些空指针来存放指向其前驱或后继的指针这样就可以像遍历单链表那样方便地遍历二叉树。引入线索二叉树正是为了加快查找结点前驱和后继的速度。 \begin{aligned} \textbf{传统的二叉链表存储仅能体现一种父子关系不能直接得到结点在遍历中的前驱或后继。前面提} \\ \text{到在含} n \ \text{个结点的二叉树中有} n 1 \ \text{个空指针。这是因为每个叶结点都有2个空指针每个度为1} \\ \text{的结点都有1个空指针空指针总数为} 2n_0 n_1\text{又} n_0 n_2 1\text{所以空指针总数为} n_0 n_1 n_2 1 n 1。 \\ \text{由此设想能否利用这些空指针来存放指向其前驱或后继的指针这样就可以像遍历单链表那样方便地} \\ \text{遍历二叉树。引入线索二叉树正是为了加快查找结点前驱和后继的速度。} \end{aligned}​传统的二叉链表存储仅能体现一种父子关系不能直接得到结点在遍历中的前驱或后继。前面提到在含n个结点的二叉树中有n1个空指针。这是因为每个叶结点都有2个空指针每个度为1的结点都有1个空指针空指针总数为2n0​n1​又n0​n2​1所以空指针总数为n0​n1​n2​1n1。由此设想能否利用这些空指针来存放指向其前驱或后继的指针这样就可以像遍历单链表那样方便地遍历二叉树。引入线索二叉树正是为了加快查找结点前驱和后继的速度。​其中标志域的含义如下ltag{0,lchild域指示结点的左孩子1,lchild域指示结点的前驱rtag{0,rchild域指示结点的右孩子1,rchild域指示结点的后继 \begin{aligned} \textbf{其中标志域的含义如下} \\ \quad \text{ltag} \begin{cases} 0, \text{lchild域指示结点的左孩子} \\ 1, \text{lchild域指示结点的前驱} \end{cases} \\ \quad \text{rtag} \begin{cases} 0, \text{rchild域指示结点的右孩子} \\ 1, \text{rchild域指示结点的后继} \end{cases} \end{aligned}​其中标志域的含义如下ltag{0,1,​lchild域指示结点的左孩子lchild域指示结点的前驱​rtag{0,1,​rchild域指示结点的右孩子rchild域指示结点的后继​​森林转换为二叉树的画法1) 将森林中的每棵树转换成相应的二叉树2) 每棵树的根也可视为兄弟关系在每棵树的根之间加一根连线3) 以第一棵树的根为轴心顺时针旋转 45∘。 \begin{aligned} \textbf{森林转换为二叉树的画法} \\ \quad 1) \ \text{将森林中的每棵树转换成相应的二叉树} \\ \quad 2) \ \text{每棵树的根也可视为兄弟关系在每棵树的根之间加一根连线} \\ \quad 3) \ \text{以第一棵树的根为轴心顺时针旋转} \ 45^\circ。 \end{aligned}​森林转换为二叉树的画法1)将森林中的每棵树转换成相应的二叉树2)每棵树的根也可视为兄弟关系在每棵树的根之间加一根连线3)以第一棵树的根为轴心顺时针旋转45∘。​表5.1 树和森林的遍历与二叉树遍历的对应关系树森 林二 叉 树先根遍历先序遍历先序遍历后根遍历中序遍历中序遍历 \begin{aligned} \textbf{表5.1 树和森林的遍历与二叉树遍历的对应关系} \\ \begin{array}{|c|c|c|} \hline \textbf{树} \textbf{森 林} \textbf{二 叉 树} \\ \hline \text{先根遍历} \text{先序遍历} \text{先序遍历} \\ \hline \text{后根遍历} \text{中序遍历} \text{中序遍历} \\ \hline \end{array} \end{aligned}​表5.1树和森林的遍历与二叉树遍历的对应关系树先根遍历后根遍历​森林先序遍历中序遍历​二叉树先序遍历中序遍历​​​2. 哈夫曼树的构造给定 n 个权值分别为 w1,w2,⋯ ,wn 的结点构造哈夫曼树的算法描述如下1) 将这 n 个结点分别作为 n 棵仅含一个结点的二叉树构成森林 F。2) 构造一个新结点从 F 中选取两棵根结点权值最小的树作为新结点的左、右子树并且将新结点的权值置为左、右子树上根结点的权值之和。3) 从 F 中删除刚才选出的两棵树同时将新得到的树加入 F 中。4) 重复步骤2和3直至 F 中只剩下一棵树为止。 \begin{aligned} \textbf{2. 哈夫曼树的构造} \\ \text{给定} \ n \ \text{个权值分别为} \ w_1, w_2, \cdots, w_n \ \text{的结点构造哈夫曼树的算法描述如下} \\ \quad 1) \ \text{将这} \ n \ \text{个结点分别作为} \ n \ \text{棵仅含一个结点的二叉树构成森林} \ F。 \\ \quad 2) \ \text{构造一个新结点从} \ F \ \text{中选取两棵根结点权值最小的树作为新结点的左、右子树并且} \\ \quad \quad \text{将新结点的权值置为左、右子树上根结点的权值之和。} \\ \quad 3) \ \text{从} \ F \ \text{中删除刚才选出的两棵树同时将新得到的树加入} \ F \ \text{中。} \\ \quad 4) \ \text{重复步骤2和3直至} \ F \ \text{中只剩下一棵树为止。} \end{aligned}​2.哈夫曼树的构造给定n个权值分别为w1​,w2​,⋯,wn​的结点构造哈夫曼树的算法描述如下1)将这n个结点分别作为n棵仅含一个结点的二叉树构成森林F。2)构造一个新结点从F中选取两棵根结点权值最小的树作为新结点的左、右子树并且将新结点的权值置为左、右子树上根结点的权值之和。3)从F中删除刚才选出的两棵树同时将新得到的树加入F中。4)重复步骤2和3直至F中只剩下一棵树为止。​从上述构造过程中可以看出哈夫曼树具有如下特点1) 每个初始结点最终都成为叶结点且权值越小的结点到根结点的路径长度越大。2) 构造过程中共新建了 n−1 个结点双分支结点因此哈夫曼树的结点总数为 2n−1。3) 每次构造都选择2棵树作为新结点的孩子因此哈夫曼树中不存在度为1的结点。例如权值{7,5,2,4}的哈夫曼树的构造过程如图5.25所示。 \begin{aligned} \text{从上述构造过程中可以看出哈夫曼树具有如下特点} \\ \quad 1) \ \text{每个初始结点最终都成为叶结点且权值越小的结点到根结点的路径长度越大。} \\ \quad 2) \ \text{构造过程中共新建了} \ n-1 \ \text{个结点双分支结点因此哈夫曼树的结点总数为} \ 2n-1。 \\ \quad 3) \ \text{每次构造都选择2棵树作为新结点的孩子因此哈夫曼树中不存在度为1的结点。} \\ \text{例如权值}\{7,5,2,4\}\text{的哈夫曼树的构造过程如图5.25所示。} \end{aligned}​从上述构造过程中可以看出哈夫曼树具有如下特点1)每个初始结点最终都成为叶结点且权值越小的结点到根结点的路径长度越大。2)构造过程中共新建了n−1个结点双分支结点因此哈夫曼树的结点总数为2n−1。3)每次构造都选择2棵树作为新结点的孩子因此哈夫曼树中不存在度为1的结点。例如权值{7,5,2,4}的哈夫曼树的构造过程如图5.25所示。​若没有一个编码是另一个编码的前缀则称这样的编码为前缀编码。举例设计字符A, B和C对应的编码0, 10和110是前缀编码。对前缀编码的解码很简单因为没有一个编码是其他编码的前缀。所以识别出第一个编码将它翻译为原字符再对剩余的码串执行同样的解码操作。例如码串0010110可被唯一地翻译为A, A, B和C。另举反例若再将字符D的编码设计为11此时11是110的前缀则上述码串的后三位就无法唯一翻译。 \begin{aligned} \textbf{若没有一个编码是另一个编码的前缀则称这样的编码为前缀编码。} \\ \text{举例设计字符A, B和C对应的编码0, 10和110是前缀编码。对前缀编码的解码很简单因为没有一个编码是其他} \\ \text{编码的前缀。所以识别出第一个编码将它翻译为原字符再对剩余的码串执行同样的解码操作。} \\ \text{例如码串0010110可被唯一地翻译为A, A, B和C。另举反例若再将字符D的编码设计为11} \\ \text{此时11是110的前缀则上述码串的后三位就无法唯一翻译。} \end{aligned}​若没有一个编码是另一个编码的前缀则称这样的编码为前缀编码。举例设计字符A, B和C对应的编码0, 10和110是前缀编码。对前缀编码的解码很简单因为没有一个编码是其他编码的前缀。所以识别出第一个编码将它翻译为原字符再对剩余的码串执行同样的解码操作。例如码串0010110可被唯一地翻译为A, A, B和C。另举反例若再将字符D的编码设计为11此时11是110的前缀则上述码串的后三位就无法唯一翻译。​前缀编码的分析及应用利用二叉树来进行哈夫曼编码的设计可以利用二叉树来设计二进制前缀编码。假设为A, B, C, D四个字符设计前缀编码可以用图5.26所示的二叉树来表示4个叶结点分别表示4个字符且约定左分支表示0右分支表示1从根到叶结点的路径上用分支标记组成的序列作为该叶结点字符的编码可以证明如此得到的必为前缀编码。由图5.26得到字符A, B, C, D的前缀编码分别为0, 10, 110, 111。 \begin{aligned} \textbf{前缀编码的分析及应用} \quad \boldsymbol{\text{利用二叉树来进行哈夫曼编码的设计}} \\ \text{可以利用二叉树来设计二进制前缀编码。假设为A, B, C, D四个字符设计前缀编码可以用} \\ \text{图5.26所示的二叉树来表示4个叶结点分别表示4个字符且约定左分支表示0右分支表示} \\ \text{1从根到叶结点的路径上用分支标记组成的序列作为该叶结点字符的编码可以证明如此得到} \\ \text{的必为前缀编码。由图5.26得到字符A, B, C, D的前缀编码分别为0, 10, 110, 111。} \end{aligned}​前缀编码的分析及应用利用二叉树来进行哈夫曼编码的设计可以利用二叉树来设计二进制前缀编码。假设为A, B, C, D四个字符设计前缀编码可以用图5.26所示的二叉树来表示4个叶结点分别表示4个字符且约定左分支表示0右分支表示1从根到叶结点的路径上用分支标记组成的序列作为该叶结点字符的编码可以证明如此得到的必为前缀编码。由图5.26得到字符A, B, C, D的前缀编码分别为0, 10, 110, 111。​每个分支结点的权值实际上代表了该结点以下的所有叶子结点的路径权重贡献 \begin{aligned} \textbf{每个分支结点的权值实际上代表了该结点以下的所有叶子结点的路径权重贡献} \end{aligned}​每个分支结点的权值实际上代表了该结点以下的所有叶子结点的路径权重贡献​并查集通过Find操作的压缩路径优化后可使集合树的深度不超过O(α(n))其中α(n)是一个增长极其缓慢的函数对于常见的正整数n通常α(n)≤4。 \begin{aligned} 并查集\text{通过Find操作的压缩路径优化后可使集合树的深度不超过} O(\alpha(n))\text{其中} \alpha(n)\text{是一个增长} \\ \text{极其缓慢的函数对于常见的正整数} n\text{通常} \alpha(n)\leq4。 \end{aligned}​并查集通过Find操作的压缩路径优化后可使集合树的深度不超过O(α(n))其中α(n)是一个增长极其缓慢的函数对于常见的正整数n通常α(n)≤4。​并查集如何检测无向图中是否存在环1. 初始化并查集使每个节点指向自己即每个节点是一个独立的集合。2. 遍历所有边⋅对于边 (u,v):⋅使用 find 操作找到 u 和 v 所属的集合即它们的根。⋅如果 u 和 v 属于相同的集合则说明存在环因为它们已经连接在一起又尝试连接自己形成了环。⋅否则使用 union 操作将它们合并到同一个集合中。3. 如果在遍历过程中发现某条边连接了两个相同的根节点说明图中存在环。 \begin{aligned} \textbf{并查集如何检测无向图中是否存在环} \\ \\ \textbf{1. 初始化并查集使每个节点指向自己即每个节点是一个独立的集合。} \\ \\ \textbf{2. 遍历所有边} \\ \quad \cdot \text{对于边} \ (u, v): \\ \quad \cdot \text{使用 find 操作找到} \ u \ \text{和} \ v \ \text{所属的集合即它们的根。} \\ \quad \cdot \text{如果} \ u \ \text{和} \ v \ \text{属于相同的集合则说明存在环因为它们已经连接在一起又尝试连接自己} \\ \quad \quad \text{形成了环。} \\ \quad \cdot \text{否则使用 union 操作将它们合并到同一个集合中。} \\ \\ \textbf{3. 如果在遍历过程中发现某条边连接了两个相同的根节点说明图中存在环。} \end{aligned}​并查集如何检测无向图中是否存在环1.初始化并查集使每个节点指向自己即每个节点是一个独立的集合。2.遍历所有边⋅对于边(u,v):⋅使用find操作找到u和v所属的集合即它们的根。⋅如果u和v属于相同的集合则说明存在环因为它们已经连接在一起又尝试连接自己形成了环。⋅否则使用union操作将它们合并到同一个集合中。3.如果在遍历过程中发现某条边连接了两个相同的根节点说明图中存在环。​若没有一个编码是另一个编码的前缀则称这样的编码为前缀编码。举例设计字符A, B和C对应的编码0, 10和110是前缀编码。对前缀编码的解码很简单因为没有一个编码是其他编码的前缀。所以识别出第一个编码将它翻译为原字符再对剩余的码串执行同样的解码操作。例如码串0010110可被唯一地翻译为A, A, B和C。另举反例若再将字符D的编码设计为11此时11是110的前缀则上述码串的后三位就无法唯一翻译。 \begin{aligned} \textbf{若没有一个编码是另一个编码的前缀则称这样的编码为前缀编码。} \\ \text{举例设计字符A, B和C对应的编码0, 10和110是前缀编码。对前缀编码的解码很简单因为没有一个编码是其他} \\ \text{编码的前缀。所以识别出第一个编码将它翻译为原字符再对剩余的码串执行同样的解码操作。} \\ \text{例如码串0010110可被唯一地翻译为A, A, B和C。另举反例若再将字符D的编码设计为11} \\ \text{此时11是110的前缀则上述码串的后三位就无法唯一翻译。} \end{aligned}​若没有一个编码是另一个编码的前缀则称这样的编码为前缀编码。举例设计字符A, B和C对应的编码0, 10和110是前缀编码。对前缀编码的解码很简单因为没有一个编码是其他编码的前缀。所以识别出第一个编码将它翻译为原字符再对剩余的码串执行同样的解码操作。例如码串0010110可被唯一地翻译为A, A, B和C。另举反例若再将字符D的编码设计为11此时11是110的前缀则上述码串的后三位就无法唯一翻译。​