必胜高考网_全国高考备考和志愿填报信息平台

必勝高考網 > 計算機類 > 計算機等級 > 資訊 >

全國計算機等級考試四級復習綱要:樹和二叉樹

時間: 家輝2 資訊

  (2)二叉樹的順序存儲結構

  二叉樹的順序存儲結構由一個一維數組構成,二叉樹上的結點按某種次序分別存入該數組的各個單元。顯然,這里的關鍵在于結點的存儲次序,這種次序應能反映結點之間的邏輯關系(父子關系),否則二叉樹的基本運算就難以實現。

  由二叉樹的性質5可知,若對任一完全二叉樹上的所有結點按層編號,則結點編號之間的數值關系可以準確地反映結點之間的邏輯關系。因此,對于任何完全二叉樹來說,可以采用“以編號為地址”的策略將結點存入作為順序存儲結構的一維數組。具體地說就是:將編號為i的結點存入一維數組的第i個單元。

  在這一存儲結構中,由于一結點的存儲位置(即下標)也就是它的編號,故結點間的邏輯關系可通過它們下標間的數值關系確定。

  (3)雙親表示法

  樹上每個結點的孩子可以有任意多個,但雙親只有一個。因此,通過指向雙親的指針而將樹中所有結點組織在一起形成一種存儲結構是十分簡法的。樹的這種存儲表示方法稱為雙親表示法。在雙親表示法下,每個存儲結點由兩個域組成:數據域———用于存儲樹上結點中的數據元素;“指針”域———用于指示本結點之雙親所在的存儲結點。值得注意的是,“指針”域的類型定義可以有兩種選擇。第一種是將其定義為高級語言(如C語句)中的指針類型。通過將存儲結點中的指針域定義為高級語言中的指針類型,就得到各種鏈式存儲結構,如單鏈表、二叉鏈表、孩子鏈表等等。第二種選擇是將“指針”域定義為整型、子界型等型。嚴格地說,無論選擇上述哪種定義,得到的都是鏈式存儲結構,因為在這兩種定義之下,各存儲結點之間的聯結是通過“指針”完成的,而且這些指針反映了結點之間的邏輯關系。

  為了區別這兩種鏈式結構,通常將指針域定義為高級語言中的指針類型的各種鏈式存儲結構(如單鏈表、二叉鏈表等等)稱為“動態鏈表”,相應的指針稱為“動態指針”;將指針域定義為整型、子界型等類型的各種鍵式存儲結構稱為“靜態鏈表”,相應的“指針”稱為:“靜態指針”。動態鏈表中的結點是通過高級語言中的標準過程例如C語言的庫函數malloc(size)動態(即運行期間)生成的(動態鏈表由此得名),無需事先規定鏈表的容量,因此動態鏈表的大小是動態變化的。相反,靜態鏈有的容量必須事先說明,因而其大小是固定的。然而,在某些情況下,特別是當結點數固定不變且可事先確定時,采用靜態鏈表往往更加方便、直觀。

  靜態雙親鏈表由一個一維數組樹成。數組的每個分量包含兩個域:數據域和雙親域。數據域用于存儲樹上一個結點中的數據元素;雙親域用于存放本結點的雙親結點在數組中的序號(下標值)。

56711 主站蜘蛛池模板: 金属检测机_金属分离器_检针验针机_食品药品金属检探测仪器-广东善安科技 | 广州展台特装搭建商|特装展位设计搭建|展会特装搭建|特装展台制作设计|展览特装公司 | 深圳善跑体育产业集团有限公司_塑胶跑道_人造草坪_运动木地板 | 振动台-振动试验台-振动冲击台-广东剑乔试验设备有限公司 | 心得体会网_心得体会格式范文模板 | 收录网| 钢格板|镀锌钢格板|热镀锌钢格板|格栅板|钢格板|钢格栅板|热浸锌钢格板|平台钢格板|镀锌钢格栅板|热镀锌钢格栅板|平台钢格栅板|不锈钢钢格栅板 - 专业钢格板厂家 | 西安标准厂房_陕西工业厂房_西咸新区独栋厂房_长信科技产业园官方网站 | 河南生物显微镜,全自动冰冻切片机-河南荣程联合科技有限公司 | 可程式恒温恒湿试验箱|恒温恒湿箱|恒温恒湿试验箱|恒温恒湿老化试验箱|高低温试验箱价格报价-广东德瑞检测设备有限公司 | 酒吧霸屏软件_酒吧霸屏系统,酒吧微上墙,夜场霸屏软件,酒吧点歌软件,酒吧互动游戏,酒吧大屏幕软件系统下载 | 北京网站建设首页,做网站选【优站网】,专注北京网站建设,北京网站推广,天津网站建设,天津网站推广,小程序,手机APP的开发。 | 壹作文_中小学生优秀满分作文大全 | 深圳市宏康仪器科技有限公司-模拟高空低压试验箱-高温防爆试验箱-温控短路试验箱【官网】 | 提升海外网站流量,增加国外网站访客UV,定制海外IP-访客王 | 禹城彩钢厂_钢结构板房_彩钢复合板-禹城泰瑞彩钢复合板加工厂 | 电动葫芦|手拉葫芦|环链电动葫芦|微型电动葫芦-北京市凌鹰起重机械有限公司 | 德州万泰装饰 - 万泰装饰装修设计软装家居馆 | 杭州代理记账费用-公司注销需要多久-公司变更监事_杭州福道财务管理咨询有限公司 | 西装定制/做厂家/公司_西装订做/制价格/费用-北京圣达信西装 | 全自动五线打端沾锡机,全自动裁线剥皮双头沾锡机,全自动尼龙扎带机-东莞市海文能机械设备有限公司 | 电缆桥架生产厂家_槽式/梯式_热镀锌线槽_广东东莞雷正电气 | 石栏杆_青石栏杆_汉白玉栏杆_花岗岩栏杆 - 【石雕之乡】点石石雕石材厂 | HYDAC过滤器,HYDAC滤芯,现货ATOS油泵,ATOS比例阀-东莞市广联自动化科技有限公司 | 阁楼货架_阁楼平台_仓库仓储设备_重型货架_广州金铁牛货架厂 | 原子吸收设备-国产分光光度计-光谱分光光度计-上海光谱仪器有限公司 | 水压力传感器_数字压力传感器|佛山一众传感仪器有限公司|首页 | 钢格板|镀锌钢格板|热镀锌钢格板|格栅板|钢格板|钢格栅板|热浸锌钢格板|平台钢格板|镀锌钢格栅板|热镀锌钢格栅板|平台钢格栅板|不锈钢钢格栅板 - 专业钢格板厂家 | 10吨无线拉力计-2吨拉力计价格-上海佳宜电子科技有限公司 | 国际船舶网 - 船厂、船舶、造船、船舶设备、航运及海洋工程等相关行业综合信息平台 | 东莞压铸厂_精密压铸_锌合金压铸_铝合金压铸_压铸件加工_东莞祥宇金属制品 | 车牌识别道闸_停车场收费系统_人脸识别考勤机_速通门闸机_充电桩厂家_中全清茂官网 | 网站建设-临朐爱采购-抖音运营-山东兆通网络科技 | 宿舍管理系统_智慧园区系统_房屋/房产管理系统_公寓管理系统 | 工装定制/做厂家/公司_工装订做/制价格/费用-北京圣达信工装 | 山东活动策划|济南活动公司|济南公关活动策划-济南锐嘉广告有限公司 | 网络推广公司_网络营销方案策划_企业网络推广外包平台-上海澜推网络 | 都江堰招聘网-都江堰人才网 都江堰人事人才网 都江堰人才招聘网 邢台人才网_邢台招聘网_邢台123招聘【智达人才网】 | 百方网-百方电气网,电工电气行业专业的B2B电子商务平台 | 上海瑶恒实业有限公司|消防泵泵|离心泵|官网 | 上海小程序开发-小程序制作-上海小程序定制开发公司-微信商城小程序-上海咏熠 |