亚洲免费av电影一区二区三区,日韩爱爱视频,51精品视频一区二区三区,91视频爱爱,日韩欧美在线播放视频,中文字幕少妇AV,亚洲电影中文字幕,久久久久亚洲av成人网址,久久综合视频网站,国产在线不卡免费播放

        ?

        平衡二叉樹調(diào)整教學(xué)探討

        2009-06-20 08:45:46張標漢
        計算機教育 2009年10期
        關(guān)鍵詞:教學(xué)探討

        張標漢

        文章編號:1672-5913(2009)10-0051-02

        摘要:平衡二叉樹教學(xué)中傳統(tǒng)的旋轉(zhuǎn)方法不太容易被學(xué)生理解,針對這一問題,本文通過分析二叉排序樹的基本原理,摸索出一種在教學(xué)實踐中更加容易被學(xué)生理解的平衡二叉樹調(diào)整方法。

        關(guān)鍵詞:二叉排序樹 平衡二叉樹 教學(xué)探討

        中圖分類號:G642

        文獻標識碼:B

        在“數(shù)據(jù)結(jié)構(gòu)與算法”課程教學(xué)中,許多教科書在介紹平衡二叉樹調(diào)整這部分內(nèi)容時,采用的都是旋轉(zhuǎn)的方法,將不平衡二叉樹用左右、順逆時針旋轉(zhuǎn)的方法使失去平衡的二叉排序樹調(diào)整為平衡二叉樹。但是在實際教學(xué)過程中,筆者發(fā)現(xiàn)這樣的方法不太容易被學(xué)生理解,許多學(xué)生尤其是??茖W(xué)生搞不清楚怎么旋轉(zhuǎn)、圍繞誰旋轉(zhuǎn)。針對這一問題,筆者通過不斷的教學(xué)實踐摸索出一種更容易被學(xué)生接受和理解的平衡二叉樹調(diào)整方法——填空法,這種方法充分利用了二叉排序樹的特點,采用填空的方式對失衡的二叉排序樹進行調(diào)整使之保持平衡。

        1基本原理

        我們知道,二叉排序樹具有這樣一個特點:左子樹上所有結(jié)點的值均小于它的根結(jié)點的值,右子樹上所有結(jié)點的值均大于它的根結(jié)點的值。即有這樣一個關(guān)系:左<根<右。利用這個特點,當(dāng)我們在插入結(jié)點使得原平衡二叉樹失去平衡而需要進行調(diào)整時,首先尋找最小不平衡子樹。最小不平衡子樹的尋找方法是:從插入的結(jié)點出發(fā),依次計算其祖先的平衡因子,發(fā)現(xiàn)的第一個平衡因子的絕對值大于1的結(jié)點就是最小不平衡子樹的根結(jié)點,則以它為根結(jié)點的子樹就是最小不平衡子樹。先考慮最簡單的情況,這棵最小不平衡子樹僅由三個結(jié)點構(gòu)成。此時最小不平衡子樹可以分為四種基本類型,分別是:LL型、LR型、RL型和RR型。如圖1所示:

        在教科書中,這四種情況是分別討論的:對LL型做一次順時針旋轉(zhuǎn),對LR型先逆時針旋轉(zhuǎn)后順時針旋轉(zhuǎn),對RL型先順時針旋轉(zhuǎn)后逆時針旋轉(zhuǎn),對RR型做一次逆時針旋轉(zhuǎn)。但應(yīng)用填空法,這四種基本情況的調(diào)整可以統(tǒng)一在一起:

        可以知道,要使得由三個結(jié)點構(gòu)成的二叉排序樹平衡,其基本結(jié)構(gòu)必定是一個結(jié)點作為根結(jié)點,一個作為左孩子結(jié)點,一個作為右孩子結(jié)點。如圖2所示:

        根據(jù)二叉排序樹的特點(左<根<右),我們只要把上述每種基本情況中的三個結(jié)點按值從小到大排列,將最小的一個填在左孩子結(jié)點位置,最大的一個填在右孩子結(jié)點位置,中間的填在根結(jié)點位置。很容易地就可以將上述四種最小不平衡子樹調(diào)整為平衡二叉樹,如圖3所示:

        進一步考慮更為復(fù)雜的情況,假定上述結(jié)點各自還有左右子樹,我們?nèi)匀豢梢允褂梦覀兊奶羁辗ㄝp松的加以調(diào)整。這四種復(fù)雜情況如圖4所示:

        假定都在CL中插入一個結(jié)點使得A的平衡因子的絕對值變?yōu)?從而使得原平衡二叉樹失去平衡,此時以A為根結(jié)點的子樹就是最小不平衡子樹,這棵最小不平衡子樹可以分為7個部分。沿著從根結(jié)點A到插入結(jié)點位置CL的路徑方向依次取三個結(jié)點,假設(shè)為A、B、C,它們和剩下的AL、AR、BL、BR、CL、CR中的4個構(gòu)成的二叉排序樹要成為平衡二叉樹,則由這7個部分組成的平衡二叉樹的基本結(jié)構(gòu)一定是如圖5所示情形:

        其中,A、B、C三者中值最小的為左子樹的根結(jié)點,值最大的為右子樹的根結(jié)點,中間的為整個最小不平衡子樹的根結(jié)點。其余的AL、AR、BL、BR、CL、CR等按從小到大的順序排列,將它們從左到右依次填在樹的第三層即可,完成后的二叉樹一定是平衡二叉樹。對上述四種復(fù)雜情形,平衡后如圖6所示:

        2示例

        例:已知長度為12的表:{Jan,Feb,Mar,Apr,May,June, July,Aug,Sep,Oct,Nov,Dec},按照表中元素順序構(gòu)造一棵平衡二叉排序樹。

        解:構(gòu)造過程如圖7、圖8所示。

        教學(xué)實踐證明,本文采用的填空法要比傳統(tǒng)的旋轉(zhuǎn)法更容易被學(xué)生接受和理解。

        參考文獻:

        [1] 嚴蔚敏,吳偉民. 數(shù)據(jù)結(jié)構(gòu)(C語言版)[M]. 北京:清華大學(xué)出版社,1997.

        [2] 馬秋菊. 數(shù)據(jù)結(jié)構(gòu)(C語言描述)[M]. 北京:中國水利水電出版社,2006.

        Discussion on Teaching of Balancing the Binary Tree

        ZHANG Biao-han

        (The Department of Maths & Computer Science, Sanming College, Sanming 365004, China)

        Abstract:The rotation method for balanced binary tree is not easy to understand by the students, This paper introduced a new method using the characteristics of the binary sort tree that is easier to understand by the students.

        Key words:binary sort tree; balanced binary tree; teaching discussion

        猜你喜歡
        教學(xué)探討
        音樂實施開發(fā)性教學(xué)探討
        未來英才(2016年20期)2017-01-03 18:29:13
        淺談小學(xué)口語交際能力的培養(yǎng)
        中小學(xué)體育教學(xué)改革與發(fā)展的探討
        未來英才(2016年22期)2016-12-28 16:25:22
        探討高中語文教學(xué)中的口語訓(xùn)練
        未來英才(2016年1期)2016-12-26 18:28:38
        探究如何讓初中英語教學(xué)更具有趣味性
        未來英才(2016年1期)2016-12-26 18:15:19
        《計算機網(wǎng)絡(luò)》教學(xué)的探討
        《計算機測控技術(shù)》課程中PID控制部分的教學(xué)探討
        初中歷史課進行趣味教學(xué)的探討
        新課程理念下的初中地理教學(xué)探討
        基于語言學(xué)理論指導(dǎo)下的高校英語教學(xué)探討
        科技資訊(2016年19期)2016-11-15 10:16:46
        插我一区二区在线观看| 国产免费AV片在线看| 人妻夜夜爽天天爽三区麻豆AV网站| av鲁丝一区鲁丝二区| 亚洲爆乳大丰满无码专区| 欧美zozo另类人禽交| 免费人成黄页网站在线观看国产 | 中文字幕精品一区二区2021年| 国产乱人伦av在线无码| 亚洲av无码专区亚洲av| 国产精品高清视亚洲乱码有限公司| 精品无码国产一二三区麻豆| 国产一区在线视频不卡| 亚洲综合日韩一二三区| 人妻 丝袜美腿 中文字幕| 国产三级精品三级在线观看| 高潮毛片无遮挡高清免费| 亚洲中文字幕久久精品蜜桃 | 久久久久久成人毛片免费看| 91中文人妻丝袜乱一区三区| 人妻在线有码中文字幕| 亚洲综合av永久无码精品一区二区 | 日本熟妇精品一区二区三区| 日本a爱视频二区三区| 日本丰满少妇xxxx| 国产成人久久精品一区二区三区| 免费a级毛片出奶水| 国产精品久久无码不卡黑寡妇| 在线无码免费看黄网站| 日本午夜a级理论片在线播放| 在线视频中文字幕一区二区三区 | 欧美色图中文字幕| 丁香婷婷激情俺也去俺来也| 中文字幕亚洲综合久久天堂av| 日韩人妻无码精品-专区| 伊伊人成亚洲综合人网7777| 国产高清国内精品福利99久久| 亚洲国产一区二区,毛片| 中文字幕av久久亚洲精品| 芒果乱码国色天香| 欧美精品久久久久久久久|