技術 [Day 29] 闖進Python異世界 - Lowest Common Ancestor

二元樹的相關題型中，有一個題目叫 Lowest Common Ancestor 我認為是相當經典的。 題目可以參考 Hackerrank 的 Lowest Co...

技術 [Day 28] 闖進Python異世界 - Valid BST

今天的目標是判斷一個二元搜尋樹是否合法？(Hackerrank 上的 Is this a Binary Search Tree ? ) 二元搜尋樹不同於二元樹的...

技術 [Day 27] 闖進Python異世界 - Level Order Traversal of BST

這種遍歷法就比較好去想像，我們是一層一層的去印出節點內容 舉例來說，有一棵樹長這樣: _1_ _3_ _7_ 9 8 4 2 那經過...

技術 [Day 26] 闖進Python異世界 - Traversal of BST

Linked List 的 Traversal 其實很簡單，基本上不是由前向後走，就是由後向前走。 但是，樹要怎麼被遍歷呢？每一個節點都可以分岔出數個岔路，每一...

技術 [Day 25] 闖進Python異世界 - Height of BST

在介紹樹的時候，我們有提到樹的相關性質，其中，樹的高度就是其中一個。 今天的目標就是來計算樹的高度。 其實只要幾行程式碼搭配遞迴思維，就可以完成！再來就是考慮...

技術 [Day 24] 闖進Python異世界 - Insertion in BST

二元搜尋樹的特色就是任意子樹的根節點資料大於左子樹的資料，且小於左子樹的資料。 因此我們在建構二元搜尋樹的時候也要依照他的邏輯！ 為求方便，我們就使用 Hack...

技術 [Day 23] 闖進Python異世界 - Tree Class

一個資料結構的開始，我們都是先實作他的節點類別和資料結構類別。 就先從節點類別開始吧！初始化： 資料內容為參數 所有指標初始為空 class Node:...

技術 [Day 29] 用C++ 設計程式中的系統櫃：BST::isValid()

學了二元搜尋樹的基本，那想過怎麼判斷這棵樹是不是二元搜尋樹嗎？ 還記得有一個遍歷演算法叫做「中序遍歷」或 inorder traversal 嗎？用這個遍歷法...

技術 [Day 28] 用C++ 設計程式中的系統櫃：BST::lowestCommonAncestor()

在二元搜尋樹中，有這麼一個經典的題目：尋找兩節點的共同祖先！ 但是共同祖先可以有很多個，所以我們會選擇最接近的共同祖先作為這題的輸出。 那要怎麼實作呢？ 我們...

技術 [Day 26] 用C++ 設計程式中的系統櫃：BST::remove() Part 1/2

刪除節點一向都是比較困難的，我們要去注意 根節點是不是我們要去刪除的目標節點 如何連接目標節點的父節點與子節點 如果目標節點有兩個子節點，又該如何與父節點連接...

技術 [Day 25] 用C++ 設計程式中的系統櫃：BST::Search()

今日目標： BST::getMax() BST::getMin() BST::search(int tg) (註：tg 為 target 的縮寫)...

技術 [Day 24] 用C++ 設計程式中的系統櫃：BST::traversal() Part3/3

今天要來完成第四種遍歷法：Level Order Traversal 比起前三者來說，他顯得更加直觀，因為他是按照 level 大小來輸出資料，換句話說，就是由...

技術 [Day 23] 用C++ 設計程式中的系統櫃：BST::traversal() Part2/3

上一篇文章，我們對三種遍歷法都有一定的認識了，今天我們要練習用迴圈來實作，難度會深一點！ 我們都知道在遍歷一棵樹時，會遇到無數的岔路，那你有想過要怎麼紀錄岔路嗎...

技術 [Day 22] 用C++ 設計程式中的系統櫃：BST::traversal() Part1/3

想輸出鏈結串列其實很容易，只要找到當前節點的 next 即可找到下一個節點。有了節點，我們就可以輸出節點中的資料。這個是之前介紹過的 LinkedList::p...

技術 [Day 21] 用C++ 設計程式中的系統櫃：BST::insert()

新增節點的方式大概可以以兩種方式來概括： 非遞迴形式：void BST::insert(int); 相對直觀 使用 while 迴圈 遞迴形式：void...

技術 [Day 20] 用C++ 設計程式中的系統櫃：Class BST

建立一棵樹之前，我們需要先建立「樹節點」類別。 由於實作的樹為「二元搜尋樹」，所以我們稱樹節點類別為 BSTNode 定義 BSTNode 從之前的二元樹模型...