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

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

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

時間: 家輝2 資訊

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

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

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

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

  (3)雙親表示法

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

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

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

56711 主站蜘蛛池模板: 天津次氯酸钠酸钙溶液-天津氢氧化钠厂家-天津市辅仁化工有限公司 | 青州搬家公司电话_青州搬家公司哪家好「鸿喜」青州搬家 | 工业雾炮机_超细雾炮_远程抑尘射雾器-世纪润德环保设备 | 东莞注册公司-代办营业执照-东莞公司注册代理记账-极刻财税 | 膜结构_ETFE膜结构_膜结构厂家_膜结构设计-深圳市烨兴智能空间技术有限公司 | 房在线-免费房产管理系统软件-二手房中介房屋房源管理系统软件 | 上海质量认证办理中心 | 直读光谱仪,光谱分析仪,手持式光谱仪,碳硫分析仪,创想仪器官网 | 楼梯定制_楼梯设计施工厂家_楼梯扶手安装制作-北京凌步楼梯 | 复合土工膜厂家|hdpe防渗土工膜|复合防渗土工布|玻璃纤维|双向塑料土工格栅-安徽路建新材料有限公司 | 圈酒招商网【jiushuitv.com】_酒水招商_代理_加盟平台 | 哲力实业_专注汽车涂料汽车漆研发生产_汽车漆|修补油漆品牌厂家 长沙一级消防工程公司_智能化弱电_机电安装_亮化工程专业施工承包_湖南公共安全工程有限公司 | 冷却塔厂家_冷却塔维修_冷却塔改造_凉水塔配件填料公司- 广东康明节能空调有限公司 | 步进_伺服_行星减速机,微型直流电机,大功率直流电机-淄博冠意传动机械 | 东莞市超赞电子科技有限公司 全系列直插/贴片铝电解电容,电解电容,电容器 | 磁力去毛刺机_去毛刺磁力抛光机_磁力光饰机_磁力滚抛机_精密金属零件去毛刺机厂家-冠古科技 | 阴离子聚丙烯酰胺价格_PAM_高分子聚丙烯酰胺厂家-河南泰航净水材料有限公司 | 钢格板|镀锌钢格板|热镀锌钢格板|格栅板|钢格板|钢格栅板|热浸锌钢格板|平台钢格板|镀锌钢格栅板|热镀锌钢格栅板|平台钢格栅板|不锈钢钢格栅板 - 专业钢格板厂家 | 艺术涂料_进口艺术涂料_艺术涂料加盟_艺术涂料十大品牌 -英国蒙太奇艺术涂料 | 香港新时代国际美容美发化妆美甲培训学校-26年培训经验,值得信赖! | 工业废水处理|污水处理厂|废水治理设备工程技术公司-苏州瑞美迪 今日娱乐圈——影视剧集_八卦娱乐_明星八卦_最新娱乐八卦新闻 | 磁力抛光研磨机_超声波清洗机厂家_去毛刺设备-中锐达数控 | 不锈钢复合板|钛复合板|金属复合板|南钢集团安徽金元素复合材料有限公司-官网 | 高光谱相机-近红外高光谱相机厂家-高光谱成像仪-SINESPEC 赛斯拜克 | 无菌实验室规划装修设计-一体化实验室承包-北京洁净净化工程建设施工-北京航天科恩实验室装备工程技术有限公司 | 照相馆预约系统,微信公众号摄影门店系统,影楼管理软件-盟百网络 | 袋式过滤器,自清洗过滤器,保安过滤器,篮式过滤器,气体过滤器,全自动过滤器,反冲洗过滤器,管道过滤器,无锡驰业环保科技有限公司 | 巨野电机维修-水泵维修-巨野县飞宇机电维修有限公司 | 河南砖机首页-全自动液压免烧砖机,小型砌块水泥砖机厂家[十年老厂] | 原子吸收设备-国产分光光度计-光谱分光光度计-上海光谱仪器有限公司 | 上海质量认证办理中心 | 湖南长沙商标注册专利申请,长沙公司注册代理记账首选美创! | 不锈钢反应釜,不锈钢反应釜厂家-价格-威海鑫泰化工机械有限公司 不干胶标签-不干胶贴纸-不干胶标签定制-不干胶标签印刷厂-弗雷曼纸业(苏州)有限公司 | 北京征地律师,征地拆迁律师,专业拆迁律师,北京拆迁律师,征地纠纷律师,征地诉讼律师,征地拆迁补偿,拆迁律师 - 北京凯诺律师事务所 | 板式换网器_柱式换网器_自动换网器-郑州海科熔体泵有限公司 | 聚丙烯酰胺_厂家_价格-河南唐达净水材料有限公司 | 北京乾茂兴业科技发展有限公司 | 深圳展厅设计_企业展馆设计_展厅设计公司_数字展厅设计_深圳百艺堂 | 铁艺,仿竹,竹节,护栏,围栏,篱笆,栅栏,栏杆,护栏网,网围栏,厂家 - 河北稳重金属丝网制品有限公司 山东太阳能路灯厂家-庭院灯生产厂家-济南晟启灯饰有限公司 | 禹城彩钢厂_钢结构板房_彩钢复合板-禹城泰瑞彩钢复合板加工厂 | 郑州外墙清洗_郑州玻璃幕墙清洗_郑州开荒保洁-河南三恒清洗服务有限公司 |