本文共 1329 字，大约阅读时间需要 4 分钟。

Objective-C递归实现二叉搜索树算法

二叉搜索树（Binary Search Tree，BST）是一种常用的数据结构，其特点是任意一个节点的左子树中所有节点的值都小于该节点的值，右子树中所有节点的值都大于该节点的值。Objective-C中可以通过递归的方式来实现BST的插入和搜索操作。

首先，我们需要定义一个节点类，用于存储节点的值和子节点。以下是代码示例：

@interface BinarySearchTreeNode : NSObject    @property int data;    @property BinarySearchTreeNode *left;    @property BinarySearchTreeNode *right;    @property id 
   
     target;@end
   

接下来，我们可以编写插入节点的递归方法。插入方法的思路是：如果当前节点的值大于目标值，则插入到左子树；反之，插入到右子树。如果当前节点为空，则创建一个新的节点，并将其值设置为目标值。

- (BinarySearchTreeNode *)insertWithTarget:(id)target inRoot:(BinarySearchTreeNode *)root {    if (!root) {        return [[BinarySearchTreeNode alloc] init];    }    if (root.data > target) {        return [root.left insertWithTarget:target inRoot:root.left];    } else {        return [root.right insertWithTarget:target inRoot:root.right];    }}

然后，我们编写查找节点的递归方法。查找方法的思路是：如果当前节点的值等于目标值，则返回该节点；如果当前节点的值大于目标值，则查找左子树；反之，查找右子树。如果当前节点为空，则返回null。

- (BinarySearchTreeNode *)searchTarget:(id)target inRoot:(BinarySearchTreeNode *)root {    if (!root) {        return nil;    }    if (root.data == target) {        return root;    } else if (root.data > target) {        return [root.left searchTarget:target inRoot:root.left];    } else {        return [root.right searchTarget:target inRoot:root.right];    }}

通过以上方法，我们可以实现BST的基本插入和搜索功能。递归的方式使得代码简洁且易于理解，同时也保证了算法的正确性。

转载地址：http://ufnfk.baihongyu.com/