一、二叉查找树的定义

　　二叉查找树是一种特殊的二叉树，又称为排序二叉树、二叉搜索树、二叉排序树。递归定义如下：

• •  要么二叉查找树是一棵空树
  •  要么二叉查找树由根结点、左子树、右子树组成，其中左子树和右子树都是二叉查找树，且左子树上所有结点的数据域均小于或等于根结点的数据域，右子树上所有结点的数据域均大于根结点的数据域。　　

 

 

二、二叉查找树的基本操作

　　二叉查找树的基本操作有查找、插入、建树、删除。

　　1. 查找操作

　　二叉查找树的性质决定了可以只选择其中一棵子树进行遍历，因此查找将会是从树根到查找结点的一条路径，故最坏复杂度为 O(h)，其中 h 是二叉查找树的高度。代码如下：

1 // 查找二叉查找树中数据域为 x 的结点  2 void search(node* root, int x) { 3     if(root == NULL) {    // 空树，查找失败  4         printf("search failed\n"); 5         return;  6     } 7     if(x == root->data) {    // 查找成功，访问之  8         printf("search success %d\n", root->data);  9     } else if(x < root->data) {        // x 比根结点的数据域小，往左子树查找 10         search(root->lchild, x);11     } else {12         search(root->rchild, x);    // x 比根结点的数据域大，往右子树查找13     } 14 }

 

 

 

 

　　2. 插入操作

　　对一棵二叉查找树来说，查找某个数据域的结点一定是沿着确定的路径进行的。因此，当某个需要查找的值在二叉查找树中查找成功，说明结点已经存在；反之，如果这个需要查找的值在二叉查找树中查找失败，那么说明查找失败的地方一定是结点需要插入的地方。代码如下：

1 // 在二叉树中插入一个数据域为 x 的新结点  2 void insert(node** root, int x) { 3     if((*root) == NULL) {        // 空树，说明查找失败，即为插入位置  4         (*root) = newNode(x);    // 生成数据域为 x 的结点 5         return;  6     }  7     if(x == (*root)->data) {    // 查找成功，说明数据已经存在  8         return; 9     } else if(x < (*root)->data) {        // x 比根结点的数据域小，往左子树查找 10         insert(&(*root)->lchild, x);11     } else {12         insert(&(*root)->rchild, x);    // x 比根结点的数据域大，往右子树查找13     } 14 }

 

 

 

 

 

 

 

 

 

 

　　3. 二叉查找树的建立

　　建立一棵二叉查找树，就是先后插入 n 个结点的过程。代码如下：

1 // 二叉查找树的建立 2 node* create(int data[], int n) {3     node* root = NULL;        // 新建根结点 root4     int i;5     for(i=0; i

 

 

 

 

 

 

 

　　4. 二叉查找树的删除

　　为了保证操作之后仍然是一棵二叉查找树，可以以树中比待删除结点小的最大结点覆盖该结点，然后删除找到的最大结点；也可以以树中比待删除结点大的最小结点覆盖该结点，然后删除找到的最小结点。下面两个函数用来寻找以 root 为根的树中最大或最小权值的结点，用以辅助寻找结点的前驱和后继，代码如下：

1 // 寻找以 root 为根结点的树中的最大权值结点  2 node* findMax(node* root) { 3     while(root->rchild != NULL) { 4         root = root->rchild;        // 不断往右，直到没有右孩子  5     } 6     return root; 7 }  8  9 // 寻找以 root 为根结点的树中的最小权值结点 10 node* findMin(node* root) {11     while(root->lchild != NULL) {12         root = root->lchild;        // 不断往左，直到没有左孩子 13     }14     return root;    15 }

 

 

 

 

　　删除操作的代码如下：

1 void deleteNode(node** root, int x) { 2     if((*root) == NULL) { 3         return;            // 不存在数据为 x 的结点  4     } 5     if((*root)->data == x) {        // 找到欲删除结点  6         if((*root)->lchild == NULL && (*root)->rchild == NULL) { 7             // 叶子结点，直接删除  8             (*root) = NULL;  9         } else if((*root)->lchild != NULL) {    // 左子树不为空 10             node* pre = findMax((*root)->lchild);    // 找前驱结点11             (*root)->data = pre->data;                // 用前驱结点覆盖原结点 12             deleteNode(&(*root)->lchild, pre->data);    // 在左子树中删除前驱结点 13         } else {                                // 右子树不为空 14             node* next = findMin((*root)->rchild);    // 找后继结点15             (*root)->data = next->data;                // 用后继结点覆盖原结点 16             deleteNode(&(*root)->rchild, next->data);    // 在左子树中删除后继结点 17         } 18     } else if((*root)->data > x) {19         deleteNode(&(*root)->lchild, x);            // 在左子树删除 x 20     } else {21         deleteNode(&(*root)->rchild, x);            // 在右子树删除 x 22     }23 }

 

 

 

 

　　完整的测试代码如下：

1 /*  2     二叉查找树   3 */  4   5 #include 
      
         6 #include 
       
          7 #include 
        
           8 #include 
         
            9 #include 
          
            10 #include 
           
             11 12 #define typename int 13 #define maxn 20 14 // 二叉树结构定义 15 typedef struct _node { 16 typename data; // 数据域 17 struct _node* lchild; // 指向左子树的根结点 18 struct _node* rchild; // 指向右子树的根结点 19 } node; 20 21 // 生成一个新节点，v为数据 22 node* newNode(typename v) { 23 node* Node = (node*)malloc(sizeof(node)); 24 Node->data = v; 25 // 初始状态下没有左右子树 26 Node->lchild = Node->rchild = NULL; 27 return Node; 28 } 29 30 // 查找二叉查找树中数据域为 x 的结点 31 void search(node* root, int x) { 32 if(root == NULL) { // 空树，查找失败 33 printf("search failed\n"); 34 return; 35 } 36 if(x == root->data) { // 查找成功，访问之 37 printf("search success %d\n", root->data); 38 } else if(x < root->data) { // x 比根结点的数据域小，往左子树查找 39 search(root->lchild, x); 40 } else { 41 search(root->rchild, x); // x 比根结点的数据域大，往右子树查找 42 } 43 } 44 45 // 在二叉树中插入一个数据域为 x 的新结点 46 void insert(node** root, int x) { 47 if((*root) == NULL) { // 空树，说明查找失败，即为插入位置 48 (*root) = newNode(x); // 生成数据域为 x 的结点 49 return; 50 } 51 if(x == (*root)->data) { // 查找成功，说明数据已经存在 52 return; 53 } else if(x < (*root)->data) { // x 比根结点的数据域小，往左子树查找 54 insert(&(*root)->lchild, x); 55 } else { 56 insert(&(*root)->rchild, x); // x 比根结点的数据域大，往右子树查找 57 } 58 } 59 60 // 二叉查找树的建立 61 node* create(int data[], int n) { 62 node* root = NULL; // 新建根结点 root 63 int i; 64 for(i=0; i
            
             rchild != NULL) { 73 root = root->rchild; // 不断往右，直到没有右孩子 74 } 75 return root; 76 } 77 78 // 寻找以 root 为根结点的树中的最小权值结点 79 node* findMin(node* root) { 80 while(root->lchild != NULL) { 81 root = root->lchild; // 不断往左，直到没有左孩子 82 } 83 return root; 84 } 85 86 void deleteNode(node** root, int x) { 87 if((*root) == NULL) { 88 return; // 不存在数据为 x 的结点 89 } 90 if((*root)->data == x) { // 找到欲删除结点 91 if((*root)->lchild == NULL && (*root)->rchild == NULL) { 92 // 叶子结点，直接删除 93 (*root) = NULL; 94 } else if((*root)->lchild != NULL) { // 左子树不为空 95 node* pre = findMax((*root)->lchild); // 找前驱结点 96 (*root)->data = pre->data; // 用前驱结点覆盖原结点 97 deleteNode(&(*root)->lchild, pre->data); // 在左子树中删除前驱结点 98 } else { // 右子树不为空 99 node* next = findMin((*root)->rchild); // 找后继结点100 (*root)->data = next->data; // 用后继结点覆盖原结点 101 deleteNode(&(*root)->rchild, next->data); // 在左子树中删除后继结点 102 } 103 } else if((*root)->data > x) {104 deleteNode(&(*root)->lchild, x); // 在左子树删除 x 105 } else {106 deleteNode(&(*root)->rchild, x); // 在右子树删除 x 107 }108 } 109 110 // 先序遍历111 void preorder(node* root) {112 if(root == NULL) {113 return; // 空树，递归边界 114 }115 printf("%d\n", root->data); // 访问该结点116 preorder(root->lchild); // 访问左子树 117 preorder(root->rchild); // 访问右子树 118 } 119 120 int main() {121 int data[10] = { 5, 1, 8, 0, 3, 6, 9, 2, 4, 7};122 node* root = NULL;123 root = create(data, 10); // 创建二叉查找树 124 preorder(root); // 先序遍历 125 search(root, 11); // 查找数据域为 11 的结点 126 deleteNode(&root, 5); // 删除数据域为 5 的结点 127 preorder(root); // 先序遍历 128 129 return 0;130 }