首页 > 代码库 > 二叉搜索树

二叉搜索树

2024-07-12 17:35:49   219人阅读

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

数据类型设计：

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 =http://www.mamicode.com/ 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 =http://www.mamicode.com/ 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 }
 
 






























        

            
                
                  
                
                

                    联系

                    我们