LinkedList-TreeIV

二元樹節點刪除二元樹刪除可分為幾種狀況: ❶ 刪除的節點為樹葉:只要將相連的父節點指向Null即可。 ❷ 刪除的節點只有一顆子樹將其右指標欄放到其父節點的左指標欄。 ❸ 刪除的節點有兩顆子樹，這方式有兩種，雖然結果不同，但都可符合二元樹特性。 1.找出中序立即前行者，即是將遇刪除節點的左子樹最大者向上提，在此節點為2，也就是在該節點的左子樹，往右尋找，直到右指標為Null，這個節點就是中序立即前行者。 2.找出中序立即後繼者，就是將欲刪除節點的右子樹最小者向上提，在此即為節點5，也就是在該節點的右子樹，往左尋找，直到左指標為Null，這個節點就是中序立即後繼者。範例: 將32,24,57,28,10,43,72,62，依照中序方式存入可放10個節點之陣... Read more 24 Sep 2023 - 2 minute read

LinkedList-TreeII

二元樹節點搜尋二元樹在建立過程是依據左子樹<樹根<右子樹的原則，只需從樹根出發比較鍵值，如果比樹根大就往右，否則往左而下，直到相等就可找到打算搜尋的值，如果比到NULL，無法再前進就代表搜尋不到此值。 // 搜索特定鍵值 fn search(&self, target: i32) -> bool { if self.data == target { return true; } if target < self.data { if let Some(left) = &self.left { retu... Read more 23 Sep 2023 - 2 minute read

LinkedList-Tree

鏈結串列實作二元樹鏈結串列實作二元樹就是用鏈結串列來儲存二元樹，好處是對於節點增加與刪除較容易，但卻不好找到父節點，除非在每一個節點增加一個副欄位。 struct TreeNode { data: i32, left: Option<Box<TreeNode>>, right: Option<Box<TreeNode>>, } 範例: 輸入一顆二元樹節點的資料為[40,20,10,50,30]，利用鏈結串列來建立，並輸出左右子樹。 #[derive(Debug)] // 定義一個二元樹節點 struct TreeNode { data: i32, left: Option<Box&... Read more 22 Sep 2023 - 2 minute read

Binary-Tree

樹狀演算法前面有講過樹的基本概念和結構，這邊會講二元樹的應用，樹狀演算法大都是用鏈結串列來處理，鏈結串列的指標用來處理樹相當方便，只需改變指標即可，也可用陣列的連續記憶體來表示二元樹，至於使用陣列或鏈結串列有好有壞。 🌳 完滿二元樹(Full Binary Tree) 當二元樹的高度為h，樹的節點為2^-1，h>=0，則稱為「完滿二元樹」。 🌳 完整二元樹(Complete Binary Tree) 當二元樹的深度為h，所含的節點數小於2^h-1，其節點的編號方式如同深度h的完滿二元樹一樣，從左到右，由上到下的順序一一對應。 🌳 歪斜樹(Skewed Binary Tree) 當一個二元樹完全沒有左節點或右節點時，則稱為左歪斜樹或右歪斜樹。 🌳 嚴格... Read more 21 Sep 2023 - 1 minute read

Double Queues

雙向佇列(double-ended queue) 雙向佇列是一般話的佇列或堆疊。跟佇列的「先進先出FIFO」，和堆疊「後進後出LIFO」比起，雙向佇列可以從最前端或最尾端任意方向，在常數時間複雜度內增刪元素，更為方便。基本操作雙向佇列有符合定義的基本操作: 🚀 new:初始化一個容器。 🚀 push_front: 在容器最前端新增一個元素。 🚀 push_back: 在容器最尾端新增一個元素。 🚀 pop_front: 移除在容器最前端的元素。 🚀 pop_back: 移除在容器最尾端的元素。為了提升方便性，也提供一些方法: 🛸 front: 查看容器最前端的元素。 🛸 back: 查看容器最尾端的元素。 🛸 len: 檢查容器內的元素數目。 🛸 is_... Read more 20 Sep 2023 - 0 minute read

Older Newer