聊聊「二叉搜索樹」的那些事兒

二叉查找樹（Binary Search Tree），（又：二叉搜索樹，二叉排序樹）它或者是一棵空樹，或者是具有下列性質的二叉樹： 若它的左子樹不空，則左子樹上所有節點的值均小於它的根節點的值； 若它的右子樹不空，則右子樹上所有節點的值均大於它的根節點的值； 它的左、右子樹也分別為二叉排序樹。「中序遍歷」可以讓節點有序。

原理

二叉排序樹的查找過程和次優二叉樹類似，通常採取二叉鏈表作為二叉排序樹的存儲結構。中序遍歷二叉排序樹可得到一個關鍵字的有序序列，一個無序序列可以通過構造一棵二叉排序樹變成一個有序序列，構造樹的過程即為對無序序列進行排序的過程。每次插入的新的節點都是二叉排序樹上新的葉子節點，在進行插入操作時，不必移動其它節點，只需改動某個節點的指針，由空變為非空即可。搜索，插入，刪除的複雜度等於樹高，O(log(n))。

實現樹節點#import /** 二叉樹節點 */ @interface DDBinaryTreeNode : NSObject /** 值 */ @property (nonatomic, assign) NSInteger value; /** 左節點 */ @property (nonatomic, strong) DDBinaryTreeNode *leftNode; /** 右節點 */ @property (nonatomic, strong) DDBinaryTreeNode *rightNode; @end創建

二叉排序樹的創建無非就是不斷查找和插入的過程，當我們查找某個值沒有找到時，我們就會將該值插入到二叉排序樹中。因為在查找的過程中可以確定該結點要插入的合適位置，所以插入就顯得比較簡單了。

#import @class DDBinaryTreeNode; @interface DDBinarySearchTreeHandler : NSObject /** * 創建二叉排序樹 * 二叉排序樹：左節點值全部小於根節點值，右節點值全部大於根節點值 * * @param values 數組 * * @return 二叉樹根節點 */ + (DDBinaryTreeNode *)createTreeWithValues:(NSArray *)values; /** * 向二叉排序樹節點添加一個節點 * * @param treeNode 根節點 * @param value

值 * * @return 根節點 */ + (DDBinaryTreeNode *)addTreeNode:(DDBinaryTreeNode *)treeNode value:(NSInteger)value; /** * 二叉搜索樹中某個值的節點 * * @param value

值 * @param rootNode 樹根節點 * * @return 節點 */ + (DDBinaryTreeNode *)searchTreeNodeWithValue:(NSInteger)value inTree:(DDBinaryTreeNode *)rootNode; @end+ (DDBinaryTreeNode *)createTreeWithValues:(NSArray *)values { DDBinaryTreeNode *root = nil; for (NSInteger i = 0; i

根據查找樹的性質我們可以很簡單的寫出添加的代碼，一個一個的比較，注意每插入的一個總是葉子節點。再進行調整。最終形成的效果圖如下：

+ (DDBinaryTreeNode *)addTreeNode:(DDBinaryTreeNode *)treeNode value:(NSInteger)value { if (!treeNode) { treeNode = [[DDBinaryTreeNode alloc] init]; treeNode.value = value; NSLog(@"node:%td", value); } else if (value value) { isLeftChild = true; current = current.leftNode; } else { isLeftChild = false; current = current.rightNode; } if (current == nil) { return; } } // 如果待刪除的節點沒有任何子節點 // 直接將該節點的原本指向該節點的指針設置為nil if (current.leftNode == nil && current.rightNode == nil) { if (current == rootNode) { rootNode = nil; } if (isLeftChild == true) { parent.leftNode = nil; } else { parent.rightNode = nil; } } // 如果待刪除的節點有一個子節點,且其為左子節點 else if (current.rightNode == nil) { // 判斷當前節點是否為根節點 if (current == rootNode) { rootNode = current.leftNode; } else if (isLeftChild) { // 掛載到父節點的左子樹 parent.leftNode = current.leftNode; } else { // 掛載到父節點的右子樹 parent.rightNode = current.leftNode; } } else if (current.leftNode == nil) { if (current == rootNode) { rootNode = current.rightNode; } else if (isLeftChild) { parent.leftNode = current.rightNode; } else { parent.rightNode = current.rightNode; } } // 如果待刪除的節點有兩個子節點 else if (current.leftNode != nil && current.rightNode != nil) { // 尋找右子樹中的最小值 DDBinaryTreeNode *successor = [DDBinarySearchTreeHandler successor:current]; if (current == rootNode) { rootNode = successor; } else if (isLeftChild) { parent.leftNode = successor; } else { parent.rightNode = successor; } successor.leftNode = current.leftNode; } } /** 在樹中查找最合適的節點 */ + (DDBinaryTreeNode *)successor:(DDBinaryTreeNode *)node { DDBinaryTreeNode *successsor = nil; DDBinaryTreeNode *successsorParent = nil; DDBinaryTreeNode *current = node.rightNode; while (current != nil) { successsorParent = successsor; successsor = current; current = current.leftNode; } if (successsor != node.rightNode) { successsorParent.leftNode = successsor.rightNode; successsor.rightNode = node.rightNode; } return successsor; }

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！