正文內容

[電腦基礎知識]第7章樹(編輯修改稿)

2026-02-15 15:32 本頁面

　

【文章內容簡介】 (T) 12 Delete(t) 13 Height(t) 14 Size(t) 二叉樹的實現 ? 實現方法：將二叉樹的所有結點，按照一定的次序依次存儲到一組連續的存儲單元中。對于完全二叉樹，可采用 “ 以編號為地址 ” 的策略將結點存入作為順序存儲結構的一維數組。 ? 具體實現如下：將一棵具有 n個結點的完全二叉樹，從樹根起，自上層到下層，逐層從左到右給所有結點編號，其中每個結點的編號作為結點的名稱。將編號為 i的結點存入一維數組的第 i個單元，這樣，就能得到一個足以反映整個二叉樹結構的線性序列。 bt: 0 1 2 3 4 5 6 7 8 9 10 11 12 結點 A B C D E F G H I J K L 完全二叉樹 a b c d e f g h i j k l (1) 順序存儲結構 1 2 3 4 5 6 7 8 9 10 11 12 性質 5：如果對一棵有 n個結點的完全二叉樹的結點按層序編號，則對任一結點 i（ 1=i=n),有：（ 1）如果 i＝ 1，則結點 i無雙親，是二叉樹的根；如果 i1，則其雙親是結點 [i/2]。（ 2）結點 i的左兒子結點為 2i，結點 i的右兒子結點為 2i+1。（ 3）當 i為奇數且不為 1時，結點 i的左兄弟結點為 i1,當 i為偶數時，結點 i的右兄弟結點為 i+1。 [i/2] i i+1 2i+1 2(i+1) 2i+3 i+1 2(i+1) 2i+3 i 2i 2i+1 圖完全二叉樹中結點 i和 i+1 (a)i和 i+1結點在同一層 (b)i和 i+1結點不在同一層 2i 如圖所示為完全二叉樹上結點及其左右子樹在結點之間的關系。由上述關系可知，完全二叉樹中結點的層次關系足以反映結點之間的邏輯關系。在這種存儲結構中，借助二叉樹的性質，可以比較方便地實現二叉樹的各種基本運算。因此，對完全二叉樹而言，順序存儲結構既簡單又節省存儲空間。 T[16] 11 A B c F E D ● ● ● ● ● ● ● ● ● 1 2 4 8 9 10 5 6 3 7 12 13 14 15 (1) 順序存儲結構 0 0 0 0 F E 0 0 0 D C 0 B A 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 0 一般二叉樹缺點 : 對于一般的二叉樹而言，存儲空間造成極大的浪費。在最壞情況下，一個高度為 k且只有 k+1個結點的右單枝樹卻需要 2k+11個結點的存儲空間。例如，只有 3個結點的右單枝樹 : 2. 二叉樹的結點度表示法這種表示法將二叉樹中所有結點依其后序列表排列，并在每個結點中附加一個 0~3之間的整數，以表示結點的狀態。（鏈式存儲結構（二叉鏈表結構）） ? 每個結點由數據域、左指針域和右指針域組成。 left element right A E C B D F A ^ D B ^ C ^ ^ E ^ ^ F ^ 二叉樹的二叉鏈表存儲結構類型描述 Typedef struct btnode *btlink。 struct btnode { TreeItem element。 btlink left。 btlink right。 } Btnode。 left element right left element right left element right 課堂練習 ? 分別畫出下圖所示二叉樹的二叉鏈表、二叉樹的結點度表示法和順序存儲結構示意圖。 B E A F D C ? 已知一棵二叉樹的先序序列和中序序列分別為 A B D G H E C F I J 及 G D H B E A C I J F，請畫出這棵二叉樹。 G B C A D E F I J H ? 用指針實現的抽象數據類型二叉樹結構定義為： typedef struct binarytree *BinaryTree。 typedef struct binarytree{ btlink root。 }BTree。 btlink NewBNode( ) { btlink p。 if((p=malloc(sizeof(Btnode)))==0) Error(“Exhausted memory.”)。 else return p。 } ? 創建一棵空二叉樹 BinaryTree BinaryInit( ) { BinaryTree T=malloc(sizeof *T)。 Troot=0。 return T。 } ? 抽象數據類型二叉樹的基本運算返回根結點標號 int BinaryEmpty(BinaryTree T) { return Troot==0。 } TreeItem Root(BinaryTree T) { if(BinaryEmpty(T)) Error(“Tree is empty”) return Trootel

點擊復制文檔內容

教學課件相關推薦

[電腦基礎知識]第7章樹(編輯修改稿)

[電腦基礎知識]windowsxp第2講-資料下載頁

電腦基礎知識ppt課件-資料下載頁

[電腦基礎知識]計算機基礎知識培訓-資料下載頁

[電腦基礎知識]第5章8086匯編語言程序設計-資料下載頁

[電腦基礎知識]第2章交換機與路由器-資料下載頁

[電腦基礎知識]第2章基本數據結構及其運算-資料下載頁

第8章mfc基礎知識-資料下載頁

dreamweaver第1章基礎知識-資料下載頁

[電腦基礎知識]c語言5章循環控制-資料下載頁

采油樹基礎知識培訓-資料下載頁

[電腦基礎知識]word部分-資料下載頁

[電腦基礎知識]ch-資料下載頁

[電腦基礎知識]系統安裝-資料下載頁

新手學習電腦基礎知識-資料下載頁

[電腦基礎知識]hwswcodesign-資料下載頁

[電腦基礎知識]第7章樹(更新版)

[電腦基礎知識]第7章樹(專業版)

[電腦基礎知識]第7章樹(留存版)

[電腦基礎知識]第7章樹-文庫吧