重温二叉搜索树 - JAVA

二叉搜索树又名为二叉查找树，是一种查找树，一种很重要的数据结构，支持多种动态集合操作，包括插入、删除、查找等操作。

二叉搜索树可以当做字典（其中键就是树节点的关键字，值为任何类型的数据，叫做卫星数据），也可以当做优先队列。

二叉搜索树是递归定义的，定义是对树中的任一节点x，左子树的关键字y不大于该节点的关键字(key[y]<=key[x])，右子树的节点的关键字y不小于该节点的关键字(key[y]>=key[x])。

下面是二叉搜索树的代码，花了好长时间调试，有点生疏了。这里的二叉搜索树是没有重复值的。

#ifndef __BSTree_H__
#define __BSTree_H__
#include 
  
   

template 
   
     struct BSTreeNode { BSTreeNode *left, *right; T val; BSTreeNode(T _val, BSTreeNode *_left=NULL, BSTreeNode *_right=NULL): val(_val), left(_left), right(_right) {} }; template
    
      class BSTree { private: BSTreeNode
     
       *root; size_t size; typedef void (*visitFun)(T); //查找值val节点的父亲 BSTreeNode
      
       * findParent(BSTreeNode
       
         *x) { assert(x != NULL); if (x == root) return NULL; BSTreeNode
        
          *y = root, *p; while (y != NULL && y->val != x->val) { p = y; if (y->val < x->val) { y = y->right; } else if (y->val > x->val) { y = y->left; } } return p; } void inOrderTraversal(BSTreeNode
         
           *root, visitFun visit) { if (root != NULL) { inOrderTraversal(root->left, visit); //访问左子树 //cout << root->val << " "; //访问该节点 visit(root->val); inOrderTraversal(root->right, visit); //访问右子树 } } public: BSTree() { root = NULL; size = 0; } ~BSTree() { releaseMemory(root); } // 释放内存 void releaseMemory(BSTreeNode
          
            *root) { if (root != NULL) { releaseMemory(root->left); releaseMemory(root->right); delete root; } } //查找值为val的节点，如果成功查找则返回该节点指针，否则返回NULL BSTreeNode
           
            * find(T val) { BSTreeNode
            
              *x = root; while (x != NULL) { if (x->val < val) { x = x->right; } else if (x->val > val) { x = x->left; } else { return x; } } return NULL; } //插入val，如果成功插入则返回true，否则（已有值为val的节点）则返回false bool insert(T val) { if (root == NULL) { root = new BSTreeNode
             
              (val); ++size; return true; } BSTreeNode
              
                *x = root, *parent; while (x != NULL) { parent = x; if (x->val < val) { x = x->right; } else if (x->val > val) { x = x->left; } else { // 二叉搜索树中已有值val的节点 return false; } } //循环结束后，parent为叶节点，p为NULL BSTreeNode
               
                 *nodePtr = new BSTreeNode
                
                 (val); if (parent->val > val) parent->left = nodePtr; else parent->right = nodePtr; ++size; } //删除值为val的节点，成功删除则返回true，否则（没找到节点）则返回false bool remove(T val) { BSTreeNode
                 
                   *x = find(val); if (x == NULL) { return false; } BSTreeNode
                  
                    *parent = findParent(x); // 删除根节点 if (parent == NULL) { if (x->left==NULL && x->right==NULL) { delete x; root = NULL; } else if (x->left != NULL) { BSTreeNode
                   
                     *y = x->left, *py = x; assert(y!=NULL); while (y->right != NULL) { py = y; y = y->right; } //y此时是x左子树的最右孩子 x->val = y->val; if (py == x) { py->left = y->left; } else { py->right = y->left; } delete y; } else { BSTreeNode
                    
                      *y = x->right, *py = x; assert(y!=NULL); while (y->left != NULL) { py = y; y = y->left; } //y此时是x右子树的最左孩子 x->val = y->val; if (py == x) { py->right = y->right; } else { py->left = y->right; } delete y; } } // x为叶节点,修改父节点parent指向x的指针为NULL else if (x->left==NULL && x->right==NULL) { parent->val < x->val   parent->right=NULL : parent->left=NULL; delete x; } // x只有一个子女，删除x else if (x->left==NULL || x->right==NULL) { if (x->left == NULL) parent->val < x->val   parent->right=x->right : parent->left=x->right; else parent->val < x->val   parent->right=x->left : parent->left=x->left; delete x; } // x有左右孩子，把x的右子树最左节点y赋给x，然后删除y else { BSTreeNode
                     
                       *y = x->right, *py = x; assert(y!=NULL); while (y->left != NULL) { py = y; y = y->left; } //y此时是x右子树的最左孩子 x->val = y->val; if (py == x) { py->right = y->right; } else { py->left = y->right; } delete y; } --size; return true; } // 中序遍历 void inOrderTraversal(visitFun visit) { inOrderTraversal(root, visit); } size_t getSize() const { return size; } }; #endif

/* Author: freeliao
   Time: 2014/1/3 14:00
   Program: Implementation o

重温二叉搜索树(一)