6.3《画出二叉树》

6.3画出二叉树 高中信息技术/教科版/选择性必修1 目录 1.情景导入， 引入新课 2.海龟作图绘制二叉树 三、编程实践变化的二叉树 四、课堂小结 1.情景导入，引入新课 为了理解复杂的数据结构，我们经常用图形方式对数据结构进行可视化的表达，但一般看到的都是节点——连线的抽象形象。在信息时代，依靠计算机和自动化编程的辅助，视觉艺术也在发生重大的变革。我们可以用递归算法来创作一幅真正的绘画作品。 2.手动操作，理解二叉排序树 Python语言的发行版本内置了一个作图模块 turtle，可以通过模拟海龟在沙滩上爬行的动作，绘制出计算机图形。turtle模块的使用非常简洁，可以用很少量的代码画出精美的图形。运行下面的程序可以画出一个边长为 100的等边三角形。 任务一绘制简单的二叉树 活动1海龟作图入门 01. import turtle #导人turtle模块 02. p=turtle.Pen() #创建一支画笔(海龟) 03.p.pencolor('blue') #设置画笔的颜色为蓝色 04.p.pensize(5) #设置画笔的粗细为5 05.#最初画笔(海龟)朝向正右方，向前画长度为1 的直线 Python语言的发行版本内置了一个作图模块 turtle，可以通过模拟海龟在沙滩上爬行的动作，绘制出计算机图形。turtle模块的使用非常简洁，可以用很少量的代码画出精美的图形。运行下面的程序可以画出一个边长为 100的等边三角形。 任务一绘制简单的二叉树 活动1海龟作图入门 06.p.forward(100) 07.p.left(120) #画笔(海龟)向左转120度 08.p.forward(100) #向前画长度为100的直线 09.p.left(120) #画笔(海龟)向左转12度 10.p.forward(100) #向前画长度为100的直线 11p.left(120) #画笔(海龟)向左转12度 当然，画笔的函数还包括后退画线 backward(n)和向右转right(n)如果只是想移动画笔(海龟) 而不画线，可以用 penup()函数将画笔抬起，再用 forward(n)和 backward(n)移动，到需要画线的时候，再用 pendown0函数来恢复画线状态。 任务一绘制简单的二叉树 活动1海龟作图入门 如图 6.3.2所示，请在计算机上试试海龟作图。(1)输入和运行画等边三角形的程序，并将程序改为使用 for 环语句。 (2)编写一个画绿色正方形的程序，边长为100，线宽为3。 (3)编写一个画红色五角星的程序，边长为100，线宽为7。 分解二叉树图形 二叉树结构是对自然界植物的一种仿生，我们对二叉树进行可视化，就能够还原出一棵树的大致样子。与数据结构的图示稍有不同的是，我们要把树根画在下方，让树干和树枝向上伸展，如图所示。 任务一绘制简单的二叉树 活动1海龟作图入门 分解二叉树图形 正如二叉树结构分为根、左子树和右子树，可视化二叉树也同样分为三个部分:树干、向左倾斜的小二叉树和向右倾斜的小二叉树。二叉树的定义满足使用递归的条件，所以我们可以用递归的方法来绘制二叉树，如图 所示。 任务一绘制简单的二叉树 活动1海龟作图入门 用递归方法，结合海龟作图模块的画图功能，可以很快写出绘制二叉树的程序。绘制二叉树的递归算法可描述如下。 (1)从初始位置出发，绘制指定长度的树干。 (2)向左旋转一个角度，绘制缩小的左子树。 (3)向右旋转一个角度，绘制缩小的右子树。 (4)画笔回到初始方向和位置。 下面，我们来实现一个绘制二叉树的函数DrawBTree(n)，函数参 数n表示树干的长度。 任务一绘制简单的二叉树 活动2 绘制简单的二叉树 根据上述算法描述，补全下面的代码。 01. import turtle #导入turtle模块 02.p=turtle.Pen() #创建一支画笔(海龟) 03.def DrawBTree(n): 04..if n<10: #如果树干太短，则不绘制直接退出 05.return 06.p.forward(n) #画出长度为n的树干 任务一绘制简单的二叉树 活动2 绘制简单的二叉树 07.p.left(30) #向左转 30度 08.DrawBTree(n-10) #画一棵树干更短的二叉树 09.p.right( ) #向右转 度 10. #画一棵树干更短的二叉树 11..p.left( ) #回正画笔的方向 12.p.backward( ）#回退到初始位置 13.return 任务一绘制简单的二叉树 活动2 绘制简单的二叉树 60 60 DrawBTree(n - 10) 30 n 补全上面的程序代码之后，请将程序代码输入到计算机中，并加上下列调用代码，进行调试运行。 14.p.pencolor('green') #设置画笔的颜色为绿色 15.p.left(90) #将画笔从初始的朝向正右方调整为朝向正上方 16.DrawBTree(50) #画一棵树干长度为50的二叉树 任务一绘制简单的二叉树 活动2 绘制简单的二叉树 成功绘制出一棵简单的二叉树后，可以尝试修改树干的长度、左右子树倾斜的角度，看看绘制效果如何。分小组讨论，为什么绘制二叉树的递归算法中，最后一步将画笔回复到初始方向和位置很重要? 递归与分形图形 分形(Fractal) 通常被定义为“一个粗糙或零碎的几何形状，可以分成数个部分，且每一部分都 (至少近似地 ) 是整体缩小后的形状”，即具有自相似的性质。1973 年，数学家曼德尔布罗 ( Benoit BMandelbrot)首次提出了分形的概念。 任务一绘制简单的二叉树 活动2 绘制简单的二叉树 3.编程实践变化的二叉树 画出简单的二叉树以后，我们还可以发挥想象力，为二叉树加入更多变化，使其更具有艺术化效果。例如: ·树干的宽度随层级变细; ·树干的颜色和长度引入随机变化; ·小二叉树伸展方向引入随机变化。 由此，将艺术二叉树的递归算法修改如下 (1) 从初始位置出发，绘制指定长度、宽度和颜色的树干 (2)向左旋转一个随机的角度，绘制随机缩小尺寸、随机颜色的左子树。 (3)向右旋转一个随机的角度，绘制随机缩小尺寸、随机颜色的右子树。 4)画笔回到初始方向和位置 任务二 绘制多彩的二叉树 活动1设置可视化参数 根据上述算法描述，补全下面的代码。 01. import turtle #导入turtle模块 02.import random #导入random随机数模块 03. p=turtle.Pen() #创建一支画笔(海龟) 04.#颜色集合 05.colorset=('green'，'red','blue'，'brown'，'black') 06. def DrawArtBTree(n，w，c): 07.if n<10: #如果树干太短，则不绘制直接退出 08.return 任务二 绘制多彩的二叉树 活动1设置可视化参数 09.p.pencolor( ) #设定画笔的颜色 10.p. #设定画笔的粗细 11.p.forward(n) #画出长度为n的树干 12.tleft=random.randint(30，60) #左转随机角度 13.tright=random.randint(30，60) #右转随机角度 14.nleft=n- #左子树长度减少5~1 随机量 15.nright=n- #右子树长度减少5~1 随机量 16.#随机挑选左子树颜色 17.lcolor=colorset[random.randint( ， )] 18.#随机挑选右子树颜色 任务二 绘制多彩的二叉树 活动1设置可视化参数 C pensize(w) random.randint(5，10） random.randint(5，10） 0 4 19.rcolor=colorset[random.randint( ， )] 20.p.left( ）#向左转 21.DrawArtBTree(_ ，w*0.5+1, ）#画左侧的小二叉树 22.p.right( ) #向右转 23. #画右侧的小二叉树 24.p.left( ) #回正画笔的方向 25.p.pencolor( ） #设定画笔的颜色 26.p. . #设定画笔的粗细 27.p.backward( ) #回退到初始位置 return 任务二 绘制多彩的二叉树 活动1设置可视化参数 0 4 tleft nleft lcolor tleft +tright DrawArtBTree(nright，w *.5 +lrcolor) tright c pensize(w) n 补全上面的程序代码之后，请将程序代码输入到计算机中，并加上下列调用代码，进行调试运行。 29. p.left(90) #将画笔从初始的朝向正右方调整为朝向正上方 30#画一棵树干长度为60的艺术二叉树 31. DrawArtBTree(60，8，'green') 任务二 绘制多彩的二叉树 活动1设置可视化参数 我们还可以往艺术二叉树程序中添加代码，画出更多装饰，得更加多姿多彩的树图形。例如，把树干太短不绘制改为绘制片片树，可以画出带有树叶的树，还可以随机加入花和果，如图所示。 任务二 绘制多彩的二叉树 活动2加入更多变化元素 仔细调节树干之间的粗细过渡，增加背景元素，如图 所示。 任务二 绘制多彩的二叉树 活动2加入更多变化元素 有了这些参考作品的启发，请修改活动1中的艺术二叉树绘制函数DrawArtBTree，绘制属于你自己的计算机艺术图形。 4.课堂小结 本节课我们学习了海龟作图的基本规则，二叉树图形和递归算法之间的对应关系，以及各种参数调整对于分形图形绘制的影响。 作业布置：请同学们认真完成教材中的拓展练习。 下节课见！ $$