以下是二叉搜索树中查找、插入、删除的递归和非递归算法

数据类型设计：

1 struct BSTNode 2 {3     ElementType data;               // 结点元素值4     struct Node *leftChild;         // 左子树根结点5     struct Node *rightChild;        // 右子树根结点6 };

查找数据：

1 // 递归算法 2 bool findBSTree(BSTNode *root, ElementType item) 3 { 4     if(root == NULL)                                           // 若二叉搜索树为空，返回假，结束查找 5         return false;            6     else {                                                     // 若二叉搜索树不为空，则item与根结点的元素值比较 7         if(item == root->data)                                 // 若等于根结点的元素值 8             return true;            9         else if(item < root->data)           10             return findBSTree(root->leftChild, item);          // 若小于根结点的元素值，则递归搜索根结点的左子树11         else           12             return findBSTree(root->rightChild, item);         // 若大于根结点的元素值，则递归搜索根结点的右子树13     }           14 }           15            16 // 非递归算法           17 bool findBSTree(BSTNode *root, ElementType item)           18 {           19     if(root == NULL)                                           // 若二叉搜索树为空，则查找失败20         return false;           21     BSTNode *current = root;           22     while(current != NULL) {                                   /* 重复搜索，直到叶子结点 */23         if(item == current->data)                              // 若查找到24             return true;           25         else if(item < current->data)                          // 若目标元素小于当前结点，则在左子树中查找26             current = current->leftChild;           27         else                                                   // 若目标元素大于当前结点，则在右子树中查找28             current = current->rightChild;29     }30     return false;31 }

插入数据：

1 // 递归算法 2 void insertBSTreeNode(BSTNode *BST, ElementType item) 3 { 4     if(BST == NULL) {                                                /* 若二叉搜索树为空，则新结点作为根结点插入 */ 5         BSTNode *temp = new BSTNode; 6         temp->data = item; 7         temp->leftChild = temp->rightChild = NULL; 8         BST = temp; 9     } else if(item < BST->data)                                      /* 新结点插入到左子树中 */10         insertBSTreeNode(BST->leftChild, item);11     else                                                             /* 新结点插入到右子树中 */12         insertBSTreeNode(BST->rightChild, item);13 }14 15 // 非递归算法16 void insertBSTreeNode(BSTNode *BST, ElementType item)17 {18     BSTNode *newNode = new BSTNode;19     newNode->data = item;20     newNode->leftChild = NULL;21     newNode->rightChild = NULL;22 23     BSTNode *current = BST;24     /* 若二叉搜索树为空，则新结点为根结点 */25     if(current == NULL) {            26         BST = newNode;27         return ;28     }29     /* 重复查找插入位置，直到新结点插入 */30     while(current->leftChild != newNode && current->rightChild != newNode) {31         if(item < current->data) {                                            // 新元素小于当前比较结点值，向左子树查找32             if(current->leftChild != NULL)                                    // 若左孩子存在，使左孩子成为当前结点33                 current = current->leftChild;34             else35                 current->leftChild = newNode;                                 // 左孩子不存在，则新结点为当前结点的左孩子36         } else {                                                              // 新元素不小于当前比较结点，则向右子树查找37             if(current->rightChild != NULL)                                   // 若右孩子存在，则使右孩子成为当前结点38                 current = current->rightChild;39             else40                 current->rightChild = newNode;                                // 若右孩子不存在，则新结点为当前结点的右孩子41         }42     }43 }44 45 // 非递归算法46 void Insert(Link &head, Item item)47 {48     BSTNode *pre = NULL, *curr = NULL;                   // 空树49     if (head == NULL) {50         head = new BSTNode(item);                        // 构造新结点51         return ;52     }53     pre = head;                                          // 从根节点开始查找54     curr = pre;55     while (curr != NULL) {56         if (item.val == curr->item.val)57             return ;                                     // 查找成功，返回58         if (item.val < curcurr->item.val)                // item的值小于当前结点值59             curr = curr->left;                           // 搜索左子树60         else61             curr = curr->right;                          // item的值大于当前结点值，搜索右子树62         pre = curr ? curr : pre;63     }64     if(item.val == pre->item.val)                        // 查找成功，返回65         return ;66     if(item.val < pre->item.val)                         // 小于当前结点67         pre->left = new BSTNode(item);                   // 构造新结点作为当前结点的左孩子68     else69         pre->right = new BSTNode(item);                  // 大于当前结点，构造新结点作为当前结点的右孩子70 }

 

 删除数据：

1  // 递归算法    注意：传进来的根结点指针是引用类型的！！！  2 bool deleteBSTreeNode(BSTNode * &BST, ElementType item)  3 {  4     /* 若二叉树为空，则删除失败 */  5     if(BST == NULL)  6         return false;  7     /* 若根结点就是要删除的结点 */  8     if(item == BST->data) {                                              9         BSTNode * temp = BST;                                                 // 记下根结点指针 10         if(BST->leftChild == NULL) {                                          // 若左子树为空树，则右孩子即为删除后的根结点 11             BST = BST->rightChild; 12             delete temp; 13             return true; 14         } else if(BST->rightChild == NULL) {                                  // 若右子树为空，左孩子即为删除后的根结点 15             BST = BST->leftChild; 16             delete temp; 17             return true; 18         } else {                                                              // 若左右子树均不为空 19             if(BST->leftChild->rightChild == NULL) {                        // 若左孩子无右子树,左孩子就是根结点的中序前件 20                 BST->data = BST->leftChild->data;                             // 中序前件的值赋给根结点 21                 return deleteBSTreeNode(BST->leftChild, BST->leftChild->data);// 删除左子树的根结点，并返回删除结果 22             } else {                                                          // 若左孩子有右子树 23                 BSTNode *prev = BST; 24                 BSTNode *current = BST->leftChild; 25                 while(current->rightChild != NULL) {                       // 找根结点的中序前件(左子树的最右边的一个结点) 26                     prev = current; 27                     current = current->rightChild; 28                 } 29                 BST->data = current->data;                                    // 中序前件的值赋给根结点 30                 return deleteBSTreeNode(current, current->data);              // 删除中序前件结点，并返回删除结果 31             } 32         } 33     } 34     /* 若待删除元素小于根结点值 */ 35     if(item < BST->data) 36         return deleteBSTreeNode(BST->leftChild, item);                        // 递归到左子树中查找并作删除，返回删除结果 37     /* 若待删除元素大于根结点值 */ 38     if(item > BST->data) 39         return deleteBSTreeNode(BST->rightChild, item);                       // 递归到右子树中查找并作删除，返回删除结果 40 } 41  42 // 非递归算法 43 bool deleteBSTreeNode(BSTNode *BST, ElementType item) 44 { 45     BSTNode *current = BST, *prior = NULL;                          // current为当前比较的结点，prior为current的父亲结点 46     /* 从二叉搜索树根结点开始查找要删除的结点 */ 47     while(current != NULL && current->data != item) { 48         prior = current; 49         if(item < current->data)                                    // item小于current结点值，则向左子树中查找 50             current = current->leftChild; 51         else  52             current = current->rightChild;                          // item不小于current结点值，则向右子树查找 53     } 54     /* 没找到目标元素 */ 55     if(current == NULL) 56         return false; 57     /* 找到目标结点，执行删除目标结点操作 */ 58     if(current->leftChild == NULL && current->rightChild == NULL) { /***** current为叶子结点 */ 59         if(current == BST)                                          // current为根结点 60             BST = NULL; 61         else {                                                      // current不为根结点 62             if(prior->leftChild == current)                         // current是父结点prior的左孩子 63                 prior->leftChild = NULL; 64             else                                                    // current是父结点prior的右孩子 65                 prior->rightChild = NULL; 66         } 67     } else if(current->leftChild == NULL) {                         /***** current是只有右孩子的单支结点 */ 68         if(current == BST)                                          // current为根结点 69             BST = current->rightChild; 70         else { 71             if(current == prior->leftChild)                         // current是父结点prior的左孩子 72                 prior->leftChild = current->rightChild; 73             else                                                    // current是父结点prior的右孩子 74                 prior->rightChild = current->rightChild; 75         } 76     } else if(current->rightChild == NULL) {                        /***** current是只有左孩子的单支结点 */ 77         if(current == BST)                                          // current为根结点 78             BST = current->leftChild; 79         else { 80             if(current == prior->leftChild)                         // current是父点prior的左孩子 81                 prior->leftChild = current->leftChild; 82             else                                                    // current是父节点prior的右孩子 83                 prior->rightChild = current->leftChild; 84         } 85     } else {                                                        /***** current为双支结点 */ 86         /* 查找current的中序前件结点 */ 87         BSTNode *inorderPrevious = current->leftChild;              // current结点的中序前件inorderPrevious 88         BSTNode *previous = current;                                // previous记下inorderPrevious的父结点 89         while(inorderPrevious->rightChild != NULL) { 90             previous = inorderPrevious; 91             inorderPrevious = inorderPrevious->rightChild; 92         } 93         previous->rightChild = inorderPrevious->leftChild;          // 将inorderPrevious的左子树上移到它本身所在的位置 94         inorderPrevious->leftChild = current->leftChild;            // 使current的左右子树成为inorderPrevious的左右子树 95         inorderPrevious->rightChild = current->rightChild; 96         if(current == BST)                       // 若current结点是根结点，则inorderPrevious成为根结点 97             BST = inorderPrevious; 98         else {                                   // 若current结点不是根结点，用inorderPrevious替代current在二叉树中的位置 99             if(current == prior->leftChild)100                 prior->leftChild = inorderPrevious;101             else102                 prior->rightChild = inorderPrevious;103         }104     }105 }