[電腦基礎知識]第2章基本數(shù)據(jù)結構及其運算(編輯修改稿)
2025-02-15 07:39 本頁面
【文章內容簡介】 ： 一律轉為完全二叉樹 ！ 方法很簡單 ， 將各層空缺處統(tǒng)統(tǒng)補上 “ 虛結點 ” ， 其內容為空 。 A B ^ C ^ ^ ^ D ^ … E [1] [2] [3] [4] [5] [6] [7] [8] [9] … [16] A B E C D 缺點： ① 浪費空間；②插入、刪除不便 二叉樹的鏈式存儲 結點定義： struct BinTreeNode { ElemType data。 BinTreeNode *leftChild, *rightChild。 }。 這里 leftChild和 rightChild分別為某一結點指向其左孩子和右孩子的指針 。 對于葉子結點或一個新生成的結點而言 ， 其左孩子和右孩子指針都應為空值 。 二叉樹的鏈式存儲 A B C ∧ ∧ D ∧ ∧ E ∧ ∧ 利用這種結點形式存儲的樹一般稱為 二叉鏈表。 從根結點出發(fā)，可以訪問二叉樹的任何結點。 為了能夠訪問二叉樹，必須保留指向根結點的指針 。這和單鏈表必須保留頭指針的道理一樣。 二叉樹的鏈式存儲結構 第 21 頁 二叉樹鏈式存儲舉例： A B E C D ^ A B ^ D ^ C ^ ^ E ^ 優(yōu)點： ① 不浪費空間；②插入、刪除方便 二叉樹的常用算法包括： 獲取根結點指針 、 判斷樹是否為空 、 插入或刪除結點 、 插入或刪除子樹 、 二叉樹遍歷等 。 二叉樹類可描述如下： class BinTree { public: BinTreeNode *root。 //定義根結點指針 BinTree() { root=NULL。 } //構造函數(shù) ， 定義空樹 bool IsEmpty() { return root==NULL。 } //判斷樹是否為空 //在葉子結點 p下插入左子樹 q void Ins_lchild(BinTreeNode *p,BinTreeNode *q) {pleftChild=q。} //在葉子結點 p下插入右子樹 q void Ins_rchild(BinTreeNode *p,BinTreeNode *q) {prightChild=q。 } //刪除結點 p的左子樹 void Del_lchild(BinTreeNode *p) { pleftChild=NULL。 } //刪除結點 p的右子樹 void Del_rchild(BinTreeNode *p) { prightChild=NULL。 } void PreOrder(BinTreeNode *t)。 //先序遍歷 void InOrder(BinTreeNode *t)。 //中序遍歷 void PostOrder(BinTreeNode *t)。 //后序遍歷 }。 第 23 頁 遍歷二叉樹 Traversing Binary Tree 遍歷定義 —— 遍歷用途 —— 遍歷方法 —— 指按某條搜索路線遍訪每個結點且不重復（又稱周游）。 它是樹結構插入、刪除、修改、查找和排序運算的前提，是二叉樹一切運算的基礎和核心。 對每個結點的查看通常都是 “ 先左后右 ” 。 第 24 頁 遍歷規(guī)則 ——— 二叉樹由根、左子樹、右子樹構成，定義為 D、 L、 R 以根結點為參照系 注：“先、中、后”的意思是指訪問的 結點 D是先于子樹出現(xiàn)還是后于子樹出現(xiàn)。 ? D、 L、 R的組合定義了六種可能的遍歷方案： LDR, LRD, DLR, DRL, RDL, RLD ? 若限定 先 左 后 右 ，則有三種實現(xiàn)方案： DLR LDR LRD 先 序遍歷 中 序遍歷 后 序遍歷 第 25 頁 例 1： 先序遍歷的結果是： 中序遍歷的結果是： 后序遍歷的結果是： A B C D E D B E A C D E B C A 口訣： DLR— 先序遍歷，即 先根再左再右 LDR— 中序遍歷，即先左再根再右 L
教學課件相關推薦
鄂ICP備17016276號-1