计算机算法分析课程设计 - 1. 动态规划—最优二叉搜索树2. 回溯法—图的着色

算法分析与设计课程教案课程编号：50c24037-01总学时：51 周学时：4适用年级专业（学科类）：2007级计科专业开课时间：2010－2011 学年第1 学期使用教材：王晓东编著计算机算法设计与分析第3版章节第1章1.1~ 1.2 第2 章2.1 课时 2教学目的理解程序与算法的概念、区别与联系；掌握算法在最坏情况、最好情况和平均情况下的计算复杂性概念；掌握算法复杂性的渐近性态的数学表述；理解递归的概念。

教学重点及突出方法重点：程序与算法的概念、算法的时间复杂性、算法复杂性的渐近性态的数学表述以及递归的概念。

通过讲解、举例方法。

教学难点及突破方法难点：算法复杂性与递归通过讲解、举例、提问与引导方法。

相关内容此部分内容基础知识可参考清华大学出版社出版严蔚敏编著的《数据结构》教学过程（教师授课思路、设问及讲解要点）回顾数据结构课程中的算法概念、排序算法等知识，从而引出本课程内容。

提问算法与程序的区别、联系以及算法具有的特性。

讲解算法的复杂性，主要包括时间复杂性与空间复杂性。

讲解最坏情况、最好情况与平均情况的时间复杂性。

讲解算法复杂性在渐近意义下的阶，主要包括O、Ω、θ与o，并通过具体例子说明。

通过具体例子说明递归技术。

主要包括阶乘函数、Fibonacci数列、Ackerman函数、排列问题、整数划分问题、Hanoi塔问题等。

第页章节第2 章2.2~2.5 课时 2 教学目的掌握设计有效算法的分治策略，并掌握范例的设计技巧，掌握计算算法复杂性方法。

教学重点及突出方法重点：分治法的基本思想及分治法的一般设计模式。

通过讲解、举例方法。

教学难点及突破方法难点：计算算法复杂性。

通过讲解、举例、提问与引导方法。

相关内容素材教（教师授课思路、设问及讲解要点）学过程通过生活中解决复杂问题的分解方法，引出分治方法。

讲解分治法的基本思想及其一般算法的设计模式，介绍分治法的计算效率。

通过具体例子采用分治思想来设计有效算法。

《算法设计与分析》教学大纲适用于四年制本科计算机应用技术、信息与计算科学专业（参考学时数：64 学时）一、课程代码7100450，7100451二、课程的性质、任务算法设计与分析是计算机科学的核心问题之一，这门课是计算机专业以及相关专业的一门重要的课程。

本课程的教学目的是：在学生学习掌握了编程的基本技术，掌握了数据结构的基本知识、理论的基础上，比较系统的学习算法理论中的基础部分内容。

在这一课程教学中，培养学生掌握算法设计的方法论，掌握常用的算法设计的方法；掌握算法分析的基本工具、方法、技巧，在解决实际问题时，对于较复杂的问题能抽象出问题的数学模型，设计出有效的算法。

在此基础上学习本课程的中级篇：结构上的算法设计（分类、图的高级部分、流），学生通过这部分的学习，了解算法优化的实现途径，很好的解决数据结构中未能解决的问题、最后是本课程的高级篇：NP完全理论、现代优化计算方法简介。

学生通过这部分的学习初步了解计算复杂性理论的基本内容、现代算法的几个主要发展分支，为今后实际应用或者搞理论研究打下一些必备的理论基础。

三、课程基本要求学生必备的先行课是：高等数学、离散数学、程序设计、数据结构。

本课程不能求快，应循序渐进，培养学生浓厚的学习热情和求知欲。

教学中注重和前期课程数据结构的衔接，使学生明白这门课不同于数据结构的是：数据结构是讨论三种基本数据结构上的基本操作的实现，它是完成“如何做”，算法设计与分析这门课强调的是：怎么巧做，做的更好。

在本课程的后期教学中，特别提倡学生广泛阅读参考书、独立思考、结合实际问题展开讨论的教学方式，并以此达到教师精讲、学生宽学的目的。

课程的基本要求是：1．掌握7种常用的算法设计方法，并能综合、灵活的使用这些基本方法，同时用所学到的知识解决一些实际问题；2．掌握算法分析的基本工具、基本技巧、基本方法；3．掌握数据结构中未能详细、深入了解的部分内容（内存分类，图的高级部分、流上的算法）；4．了解计算复杂性理论中的基本内容，包括：机器模型，NP完全、NP难题，近似计算；5．了解现代的计算算法和算法理论的发展趋势走向。

算法设计与分析课程教学大纲【适用专业】计算机科学与技术【课时】理论课时：32【学分】 2【课程性质、目标和要求】《算法设计与分析》是计算机科学与技术专业的专业课。

无论是计算科学还是计算实践，算法都在其中扮演着重要角色。

本课程的教学目的是讲授在计算机应用中常常遇到的实际问题的解法，讲授设计和分析各种算法的基本原理、方法和技术，培养学生对算法复杂性进行正确分析的能力。

课程基本要求是⑴掌握算法分析的基本概念和理论。

⑵掌握算法设计技术和分析算法以及算法复杂性。

【教学时间安排】本课程计 2 学分，理论课时32, 学时分配如下：【教学内容要点】第一章算法引论一、学习目的要求1．了解算法的计算复杂性分析方法2．理解算法分析的基本理论3．掌握算法分析的基本概念二、主要教学内容1. 算法的基本概念2. 表达算法的抽象机制3. 采用Java语言与自然语言相结合的方式描述算法的方法4. 算法的计算复杂性分析方法第二章递归与分治策略一、学习目的要求1．理解典型范例中递归与分治策略应用技巧2．掌握递归与分治策略3．掌握数学归纳法证明算法正确性方法二、主要教学内容1. 递归的概念2. 分治法的基本思想3. 二分搜索技术4. 大整数的乘法5. Strassen阵乘法6. 棋盘覆盖7. 合并排序8. 快速排序9. 线性时间选择10. 最接近点对问题11. 循环赛日程表第三章动态规划一、学习目的要求1．理解典型范例中动态规划算法的设计思想2．掌握动态规划算法的基本要求以及算法的设计要点二、主要教学内容1. 矩阵连乘问题2. 动态规划算法的基本要素3. 最长公共子序列4. 最大子段和5. 凸多边形最优三角剖分6. 多边形游戏7. 图像压缩8. 电路布线9. 流水作业调度10. 0—l背包问题11. 最优二叉搜索树12. 动态规划加速原理三、课堂讨论选题1. 最长公共子序列2. 0—l背包问题第四章贪心算法一、学习目的要求1．了解贪心算法的理论基础及基本要素2. 理解典型范例中贪心算法的设计思想3. 掌握贪心算法的设计要点二、主要教学内容1. 活动安排问题2. 贪心算法的基本要素3. 最优装载4. 哈夫曼编码5. 单源最短路径6. 最小生成树7. 多机调度问题8. 贪心算法的理论基础三、课堂讨论选题1. 最优装载2. 单源最短路径第五章回溯法一、学习目的要求1．理解回溯法的效率分析方法2．掌握回溯法的算法框架和应用技巧二、主要教学内容1. 回溯法的算法框架2. 装载问题3. 批处理作业调度4. 符号三角形问题5. n后问题6. 0—l背包问题7. 最大团问题8. 图的m着色问题9. 旅行售货员问题10. 圆排列问题11. 电路板排列问题12. 连续邮资问题13. 回溯法的效率分三、课堂讨论选题1. 0—l背包问题2. 图的m着色问题第六章分支限界法一、学习目的要求1．理解分支限界法的基本思想2．掌握典型范例中分支限界法的应用技巧二、主要教学内容1. 分支限界法的基本思想2. 单源最短路径问题3. 装载问题4. 布线问题5. 0-1背包问题6. 最大团问题7. 旅行售货员问题8. 电路板排列问题9. 批处理作业调度三、课堂讨论选题1. 0-1背包问题2. 批处理作业调度第七章概率算法一、学习目的要求1．理解概率算法的基本思想2．掌握典型范例中概率算法的应用技巧二、主要教学内容1. 随机数2. 数值概率算法3. 舍伍德算法4. 拉斯维加斯算法5. 蒙特卡罗算法第八章 NP完全性理论一、学习目的要求1．了解P类与NP类问题2．了解典型的NP完全问题二、主要教学内容1. 计算模型2. P类与NP类问题3. NP完全问题4. 一些典型的NP完全问题第九章近似算法一、学习目的要求1．掌握近似算法的基本思想2．掌握常用近似算法的应用二、主要教学内容1. 近似算法的性能2. 顶点覆盖问题的近似算法3. 旅行售货员问题近似算法4. 集合覆盖问题的近似算法5. 子集和问题的近似算法第十章算法优化策略一、学习目的要求1．掌握算法优化策略2．掌握算法优化的基本方法二、主要教学内容1. 算法优化策略的比较与选择2. 动态规划加速原理3. 问题的算法特征4. 优化数据结构5. 优化搜索策略【教学（实验）内容要点】算法设计与分析实验是算法设计与分析课的一个实践性教学环节。

动态规划-最优⼆叉搜索树摘要： 本章介绍了⼆叉查找树的概念及操作。

主要内容包括⼆叉查找树的性质，如何在⼆叉查找树中查找最⼤值、最⼩值和给定的值，如何找出某⼀个元素的前驱和后继，如何在⼆叉查找树中进⾏插⼊和删除操作。

在⼆叉查找树上执⾏这些基本操作的时间与树的⾼度成正⽐，⼀棵随机构造的⼆叉查找树的期望⾼度为O(lgn)，从⽽基本动态集合的操作平均时间为θ(lgn)。

1、⼆叉查找树 ⼆叉查找树是按照⼆叉树结构来组织的，因此可以⽤⼆叉链表结构表⽰。

⼆叉查找树中的关键字的存储⽅式满⾜的特征是：设x为⼆叉查找树中的⼀个结点。

如果y是x的左⼦树中的⼀个结点，则key[y]≤key[x]。

如果y是x的右⼦树中的⼀个结点，则key[x]≤key[y]。

根据⼆叉查找树的特征可知，采⽤中根遍历⼀棵⼆叉查找树，可以得到树中关键字有⼩到⼤的序列。

介绍了⼆叉树概念及其遍历。

⼀棵⼆叉树查找及其中根遍历结果如下图所⽰：书中给出了⼀个定理：如果x是⼀棵包含n个结点的⼦树的根，则其中根遍历运⾏时间为θ(n)。

问题：⼆叉查找树性质与最⼩堆之间有什么区别？能否利⽤最⼩堆的性质在O(n)时间内，按序输出含有n个结点的树中的所有关键字？2、查询⼆叉查找树 ⼆叉查找树中最常见的操作是查找树中的某个关键字，除了基本的查询，还⽀持最⼤值、最⼩值、前驱和后继查询操作，书中就每种查询进⾏了详细的讲解。

（1）查找SEARCH 在⼆叉查找树中查找⼀个给定的关键字k的过程与⼆分查找很类似，根据⼆叉查找树在的关键字存放的特征，很容易得出查找过程：⾸先是关键字k与树根的关键字进⾏⽐较，如果k⼤⽐根的关键字⼤，则在根的右⼦树中查找，否则在根的左⼦树中查找，重复此过程，直到找到与遇到空结点为⽌。

例如下图所⽰的查找关键字13的过程：（查找过程每次在左右⼦树中做出选择，减少⼀半的⼯作量）书中给出了查找过程的递归和⾮递归形式的伪代码：1 TREE_SEARCH(x,k)2 if x=NULL or k=key[x]3 then return x4 if(k<key[x])5 then return TREE_SEARCH(left[x],k)6 else7 then return TREE_SEARCH(right[x],k)1 ITERATIVE_TREE_SEARCH(x,k)2 while x!=NULL and k!=key[x]3 do if k<key[x]4 then x=left[x]5 else6 then x=right[x]7 return x（2）查找最⼤关键字和最⼩关键字 根据⼆叉查找树的特征，很容易查找出最⼤和最⼩关键字。

分治法1、二分搜索算法是利用（分治策略）实现的算法。

9. 实现循环赛日程表利用的算法是（分治策略）27、Strassen矩阵乘法是利用（分治策略）实现的算法。

34．实现合并排序利用的算法是（分治策略）。

实现大整数的乘法是利用的算法（分治策略）。

17．实现棋盘覆盖算法利用的算法是（分治法）。

29、使用分治法求解不需要满足的条件是（子问题必须是一样的）。

不可以使用分治法求解的是（0/1背包问题）。

动态规划下列不是动态规划算法基本步骤的是（构造最优解）下列是动态规划算法基本要素的是（子问题重叠性质）。

下列算法中通常以自底向上的方式求解最优解的是（动态规划法）备忘录方法是那种算法的变形。

（动态规划法）最长公共子序列算法利用的算法是（动态规划法）。

矩阵连乘问题的算法可由（动态规划算法B）设计实现。

实现最大子段和利用的算法是（动态规划法）。

贪心算法能解决的问题：单源最短路径问题，最小花费生成树问题，背包问题，活动安排问题，不能解决的问题：N皇后问题，0/1背包问题是贪心算法的基本要素的是（贪心选择性质和最优子结构性质）。

回溯法回溯法解旅行售货员问题时的解空间树是（排列树）。

剪枝函数是回溯法中为避免无效搜索采取的策略回溯法的效率不依赖于下列哪些因素（确定解空间的时间）分支限界法最大效益优先是（分支界限法）的一搜索方式。

分支限界法解最大团问题时，活结点表的组织形式是（最大堆）。

分支限界法解旅行售货员问题时，活结点表的组织形式是（最小堆）优先队列式分支限界法选取扩展结点的原则是（结点的优先级）在对问题的解空间树进行搜索的方法中,一个活结点最多有一次机会成为活结点的是( 分支限界法).从活结点表中选择下一个扩展结点的不同方式将导致不同的分支限界法,以下除( 栈式分支限界法)之外都是最常见的方式.（1）队列式(FIFO)分支限界法：按照队列先进先出（FIFO）原则选取下一个节点为扩展节点。

（2）优先队列式分支限界法：按照优先队列中规定的优先级选取优先级最高的节点成为当前扩展节点。

1.一个算法就是一个有穷规则的集合，其中之规则规定了解决某一特殊类型问题的一系列运算，此外，算法还应具有以下五个重要特性:_________,________,________,__________,__________。

2.算法的复杂性有_____________和___________之分，衡量一个算法好坏的标准是______________________。

3.某一问题可用动态规划算法求解的显著特征是____________________________________。

4.若序列X={B,C,A,D,B,C,D}，Y={A,C,B,A,B,D,C,D}，请给出序列X 和Y的一个最长公共子序列_____________________________。

5.用回溯法解问题时，应明确定义问题的解空间，问题的解空间至少应包含___________。

6.动态规划算法的基本思想是将待求解问题分解成若干____________，先求解___________，然后从这些____________的解得到原问题的解。

7.以深度优先方式系统搜索问题解的算法称为_____________。

8.0-1背包问题的回溯算法所需的计算时间为_____________,用动态规划算法所需的计算时间为____________。

9.动态规划算法的两个基本要素是___________和___________。

10.二分搜索算法是利用_______________实现的算法。

二、综合题（50分）1.写出设计动态规划算法的主要步骤。

2.流水作业调度问题的johnson算法的思想。

3.若n=4，在机器M1和M2上加工作业i所需的时间分别为a i和b i，且(a1,a2,a3,a4)=(4,5,12,10)，(b1,b2,b3,b4)=(8,2,15,9)求4个作业的最优调度方案，并计算最优值。

4.使用回溯法解0/1背包问题：n=3，C=9，V={6,10,3}，W={3,4,4},其解空间有长度为3的0-1向量组成，要求用一棵完全二叉树表示其解空间（从根出发，左1右0），并画出其解空间树，计算其最优值及最优解。

动态规划之最优⼆叉搜索树（算法导论）1、⼀些概念⼆叉搜索树：在⼆叉树中，对任意的节点X其左⼦树的所有节点都不⼤于X.key，其右⼦树的所有节点都不⼩于X.key。

满⾜此条件的⼆叉树称为⼆叉搜索树。

对⼆叉搜索树进⾏中序遍历将会得到⼀个单调递增的数列。

最优⼆叉树：在⼆叉树中，不同的节点都有不同的访问频率。

为了减少查找某个节点所需要遍历的次数，通过将访问频率最⾼的节点放在离根节点近的位置，这样就可以减少平均遍历次数。

最优⼆叉树⼜称赫夫曼树。

最优⼆叉搜索树：就是满⾜⼆叉搜索树性质的最优⼆叉树。

2、问题描述现在给定⼀组有序节点的查找概率，以及查找失败的概率。

关键字k1,k2,k3,...,kn的查找的概率分别为p1,p2,p3,...,pn. 对于查找失败的伪关键字，有n+1个分别为：d0,d1,d2,d3,...,dn. 其分别对于的查找概率为：q0,q1,q2,...,qn。

假设现在有五个节点，每个节点的概率为p1,p2,...,p5。

qi表⽰伪关键字di的概率，分别为q0,q1,q2,...,q5。

如下表：该表对应的图如下所⽰。

3、问题解析由于最优⼆叉搜索树需要满⾜节点之间连续有序，因⽽，对于任意满⾜条件的⼦树Ti..j，其节点分别为ki,ki+1,...,kj. 在这个⼦树中查找失败的伪关键字分别为di-1, di, di+1, ..., dj。

r[ i, j ]：表⽰⼦树Ti..j的根节点，⽤来构造满⾜条件的最优⼆叉搜索树；w[ i, j ]：表⽰⼦树Ti..j中从节点i到节点j的访问概率之和，⽤来计算当⼦树Ti..j变成其他节点的⼦树时，这时该⼦树的所有节点的深度都增加了1，这时这颗⼦树所增加的代价就为这颗⼦树的所有节点的概率和包括伪关键字节点的概率。

w[ i, j ] = pi+p(i+1)+...+pj+q(i-1)+qi+q(i+1)+...+qj.e[ i, j ]：表⽰对⼦树Ti..j进⾏⼀次访问的平均代价，当访问的平均代价越⼩，其性能越优；若kr为⼦树Ti..j的根节点，则有：e[i, j] = pr+( e[i, r-1] + w[i, r-1] ) + ( e[r+1, j] + w[r+1, j])⽽：w[i, j] = w[i, r-1] + pr + w[r+1, j]所以e[ i, j ] = e[i, r-1] + w[i, j] + e[r+1, j]于是有：if j == i-1, then e[i, j] = q(i-1);if i <= j, then e[i, j] = min{e[i, r-1]+e[r+1, j]+w[i, j] } ( i <= r <= j )另外还有w[i, j] = w[i, j-1]+pj+qj.4、代码实现（感觉写得很混乱，o(╯□╰)o）<span style="font-size:18px;">#include <stdio.h>#include <string.h>#define MAX 102double p[MAX], q[MAX], price;int r[MAX][MAX];void print(int i, int j, int c){if(i > j){price += q[i-1]*c;return ;}printf("%d ",r[i][j]);price += p[r[i][j]]*c;print(i, r[i][j]-1, c+1);print(r[i][j]+1, j, c+1);}void optimal_bst(int n){double e[MAX][MAX], w[MAX][MAX]; //int r[MAX][MAX];int i, j, k, len, tmp;//initializememset(e, 0, sizeof(e));memset(w, 0, sizeof(w));memset(r, 0, sizeof(r));for(i=1; i<=n+1; i++){e[i][i-1] = q[i-1];w[i][i-1] = q[i-1];}//bottom to upfor(len=1; len<=n; len++){for(i=1; i<=n-len+1; i++){j=i+len-1;w[i][j] = w[i][j-1]+p[j]+q[j];e[i][j] = e[i][i-1]+e[i+1][j]+w[i][j];r[i][j] = i;for(k=i+1; k<=j; k++){tmp = e[i][k-1]+e[k+1][j]+w[i][j];if(e[i][j] > tmp){e[i][j] = tmp;r[i][j] = k;}}}}// printf("e[1][n] = %lf\n",e[1][n]);// printf("w[1][n] = %lf\n",w[1][n]);//print result//print(1, n);}int main(){//freopen("bst.in", "r", stdin);int n, i, j;while(scanf("%d",&n)==1){for(i=1; i<=n; i++)scanf("%lf", &p[i]);for(i=0; i<=n; i++)scanf("%lf", &q[i]);optimal_bst(n);price = 0;print(1, n, 1);printf("\nprice = %.3lf\n",price);}return 0;}</span>。

javascript实现数据结构：树和⼆叉树的应⽤--最优⼆叉树（赫夫曼树），回溯法与树的。

赫夫曼树及其应⽤赫夫曼(Huffman)树⼜称最优树，是⼀类带权路径长度最短的树，有着⼴泛的应⽤。

最优⼆叉树(Huffman树)1 基本概念①结点路径：从树中⼀个结点到另⼀个结点的之间的分⽀构成这两个结点之间的路径。

②路径长度：结点路径上的分⽀数⽬称为路径长度。

③树的路径长度：从树根到每⼀个结点的路径长度之和。

以下图为例：A到F ：结点路径 AEF ；路径长度(即边的数⽬) 2 ；树的路径长度：3*1+5*2+2*3=19；④结点的带权路径长度：从该结点的到树的根结点之间的路径长度与结点的权(值)的乘积。

权(值)：各种开销、代价、频度等的抽象称呼。

⑤树的带权路径长度：树中所有叶⼦结点的带权路径长度之和，记做：WPL=w1*l1+w2*l2+⋯+wn*ln=∑wi*li (i=1,2,⋯,n)其中：n为叶⼦结点的个数；wi为第i个结点的权值； li为第i个结点的路径长度。

⑥ Huffman树：具有n个叶⼦结点(每个结点的权值为wi) 的⼆叉树不⽌⼀棵，但在所有的这些⼆叉树中，必定存在⼀棵WPL值最⼩的树，称这棵树为Huffman树(或称最优树) 。

在许多判定问题时，利⽤Huffman树可以得到最佳判断算法。

下图是权值分别为2、3、6、7，具有4个叶⼦结点的⼆叉树，它们的带权路径长度分别为：(a) WPL=2*2+3*2+6*2+7*2=36 ；(b) WPL=2*1+3*2+6*3+7*3=47 ；(c) WPL=7*1+6*2+2*3+3*3=34 。

其中(c)的 WPL值最⼩，可以证明是Huffman树。

2 Huffman树的构造①根据n个权值{w1, w2, ⋯,wn}，构造成n棵⼆叉树的集合F={T1, T2, ⋯,Tn}，其中每棵⼆叉树只有⼀个权值为wi的根结点，没有左、右⼦树；②在F中选取两棵根结点权值最⼩的树作为左、右⼦树构造⼀棵新的⼆叉树，且新的⼆叉树根结点权值为其左、右⼦树根结点的权值之和；③在F中删除这两棵树，同时将新得到的树加⼊F中；④重复②、③，直到F只含⼀棵树为⽌。

《计算机算法设计与分析》课程设计用分治法解决快速排序问题及用动态规划法解决最优二叉搜索树问题及用回溯法解决图的着色问题一、课程设计目的：《计算机算法设计与分析》这门课程是一门实践性非常强的课程，要求我们能够将所学的算法应用到实际中，灵活解决实际问题。

通过这次课程设计，能够培养我们独立思考、综合分析与动手的能力，并能加深对课堂所学理论和概念的理解，可以训练我们算法设计的思维和培养算法的分析能力。

二、课程设计内容：1、分治法：（2）快速排序；2、动态规划：（4）最优二叉搜索树；3、回溯法：（2）图的着色。

三、概要设计：分治法—快速排序：分治法的基本思想是将一个规模为n的问题分解为k个规模较小的子问题，这些子问题互相独立且与原问题相同。

递归地解这些子问题，然后将各个子问题的解合并得到原问题的解。

分治法的条件：（1) 该问题的规模缩小到一定的程度就可以容易地解决；（2) 该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质；（3) 利用该问题分解出的子问题的解可以合并为该问题的解；（4) 该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子子问题。

抽象的讲，分治法有两个重要步骤：（1）将问题拆开；（2）将答案合并；动态规划—最优二叉搜索树：动态规划的基本思想是将问题分解为若干个小问题，解子问题，然后从子问题得到原问题的解。

设计动态规划法的步骤：（1）找出最优解的性质，并刻画其结构特征；（2）递归地定义最优值（写出动态规划方程）；（3）以自底向上的方式计算出最优值；（4）根据计算最优值时得到的信息，构造一个最优解。

●回溯法—图的着色回溯法的基本思想是确定了解空间的组织结构后，回溯法就是从开始节点（根结点）出发，以深度优先的方式搜索整个解空间。

这个开始节点就成为一个活结点，同时也成为当前的扩展结点。

在当前的扩展结点处，搜索向纵深方向移至一个新结点。

这个新结点就成为一个新的或节点，并成为当前扩展结点。