您现在的位置是：主页 > news > 阿里外贸平台网站建设/网站推广网络营销

阿里外贸平台网站建设/网站推广网络营销

admin2025/6/21 20:40:03【news】

简介阿里外贸平台网站建设,网站推广网络营销,大岭山网站仿做,WordPress主题安全检查算法中，有一种叫做线性查找。 分为：顺序查找。 折半查找。 查找有两种形态： 分为：破坏性查找， 比如有一群mm，我猜她们的年龄，第一位猜到了是23，此时这位mm已经从我脑海里面的mmlis…

阿里外贸平台网站建设,网站推广网络营销,大岭山网站仿做,WordPress主题安全检查算法中，有一种叫做线性查找。 分为：顺序查找。 折半查找。 查找有两种形态： 分为：破坏性查找， 比如有一群mm，我猜她们的年龄，第一位猜到了是23，此时这位mm已经从我脑海里面的mmlis…

算法中，有一种叫做线性查找。

分为：顺序查找。

        折半查找。

 

查找有两种形态：

分为：破坏性查找，   比如有一群mm，我猜她们的年龄，第一位猜到了是23+，此时这位mm已经从我脑海里面的mmlist中remove掉了。

                            哥不找23+的，所以此种查找破坏了原来的结构。

       非破坏性查找， 这种就反之了，不破坏结构。 

 

顺序查找：

    这种非常简单，就是过一下数组，一个一个的比，找到为止。

[java] view plaincopy
  1. using System;  
  2. using System.Collections.Generic;  
  3. using System.Linq;  
  4. using System.Text;  
  5.   
  6.   
  7. namespace Sequential  
  8. {  
  9.     class Program  
  10.     {  
  11.         static void Main(string[] args)  
  12.         {  
  13.             List<int> list = new List<int>() { 2, 3, 5, 8, 7 };  
  14.   
  15.   
  16.             var result = SequenceSearch(list, 3);  
  17.   
  18.   
  19.             if (result != -1)  
  20.                 Console.WriteLine("3 已经在数组中找到，索引位置为：" + result);  
  21.             else  
  22.                 Console.WriteLine("呜呜，没有找到！");  
  23.   
  24.   
  25.             Console.Read();  
  26.         }  
  27.   
  28.   
  29.         //顺序查找  
  30.         static int SequenceSearch(List<int> list, int key)  
  31.         {  
  32.             for (int i = 0; i < list.Count; i++)  
  33.             {  
  34.                 //查找成功，返回序列号  
  35.                 if (key == list[i])  
  36.                     return i;  
  37.             }  
  38.             //未能查找，返回-1  
  39.             return -1;  
  40.         }  
  41.     }  
  42. }  


 

折半查找: 这种查找很有意思，就是每次都砍掉一半，

             比如"幸运52“中的猜价格游戏，价格在999元以下，1分钟之内能猜到几样给几样，如果那些选手都知道折半查找，

             那结果是相当的啊。

           

不过要注意，这种查找有两个缺点：

            第一： 数组必须有序，不是有序就必须让其有序，大家也知道最快的排序也是NLogN的，所以.....呜呜。

            第二： 这种查找只限于线性的顺序存储结构。

 

上代码:

[java] view plaincopy
  1. using System;  
  2. using System.Collections.Generic;  
  3. using System.Linq;  
  4. using System.Text;  
  5.   
  6. namespace BinarySearch  
  7. {  
  8.     class Program  
  9.     {  
  10.         static void Main(string[] args)  
  11.         {  
  12.             List<int> list = new List<int>() { 3, 7, 9, 10, 11, 24, 45, 66, 77 };  
  13.   
  14.             var result = BinarySearch(list, 45);  
  15.   
  16.             if (result != -1)  
  17.                 Console.WriteLine("45 已经在数组中找到，索引位置为：" + result);  
  18.             else  
  19.                 Console.WriteLine("呜呜，没有找到！");  
  20.   
  21.             Console.Read();  
  22.         }  
  23.   
  24.         ///<summary>  
  25. /// 折半查找  
  26. ///</summary>  
  27. ///<param name="list"></param>  
  28. ///<returns></returns>  
  29.         public static int BinarySearch(List<int> list, int key)  
  30.         {  
  31.             //最低线  
  32.             int low = 0;  
  33.   
  34.             //最高线  
  35.             int high = list.Count - 1;  
  36.   
  37.             while (low <= high)  
  38.             {  
  39.                 //取中间值  
  40.                 var middle = (low + high) / 2;  
  41.   
  42.                 if (list[middle] == key)  
  43.                 {  
  44.                     return middle;  
  45.                 }  
  46.                 else  
  47.                     if (list[middle] > key)  
  48.                     {  
  49.                         //下降一半  
  50.                         high = middle - 1;  
  51.                     }  
  52.                     else  
  53.                     {  
  54.                         //上升一半  
  55.                         low = middle + 1;  
  56.                     }  
  57.             }  
  58.             //未找到  
  59.             return -1;  
  60.         }  
  61.     }  
  62. }  

  

     先前也说过，查找有一种形态是破坏性的，那么对于线性结构的数据来说很悲惨，因为每次破坏一下，

可能都导致数组元素的整体前移或后移。

    所以线性结构的查找不适合做破坏性操作，那么有其他的方法能解决吗？嗯，肯定有的，不过要等下一天分享。

 

ps：  线性查找时间复杂度：O(n);

         折半无序（用快排活堆排）的时间复杂度：O(NlogN)+O(logN);

         折半有序的时间复杂度：O(logN);


哈希查找：

 

    对的，他就是哈希查找，说到哈希，大家肯定要提到哈希函数，呵呵，这东西已经在我们脑子里面形成

固有思维了。大家一定要知道“哈希“中的对应关系。

     比如说： ”5“是一个要保存的数，然后我丢给哈希函数，哈希函数给我返回一个”2"，那么此时的”5“

和“2”就建立一种对应关系，这种关系就是所谓的“哈希关系”，在实际应用中也就形成了”2“是key，”5“是value。

    那么有的朋友就会问如何做哈希，首先做哈希必须要遵守两点原则：

          ①:  key尽可能的分散，也就是我丢一个“6”和“5”给你，你都返回一个“2”，那么这样的哈希函数不尽完美。

          ②： 哈希函数尽可能的简单，也就是说丢一个“6”给你，你哈希函数要搞1小时才能给我，这样也是不好的。

 

其实常用的做哈希的手法有“五种”：

第一种：”直接定址法“。

                  很容易理解，key=Value+C； 这个“C"是常量。Value+C其实就是一个简单的哈希函数。

第二种：“除法取余法”。

                  很容易理解， key=value%C;解释同上。

第三种：“数字分析法”。

                  这种蛮有意思，比如有一组value1=112233，value2=112633，value3=119033，

                  针对这样的数我们分析数中间两个数比较波动，其他数不变。那么我们取key的值就可以是

                  key1=22,key2=26,key3=90。 

第四种：“平方取中法”。此处忽略，见名识意。

第五种：“折叠法”。

                 这种蛮有意思,比如value=135790，要求key是2位数的散列值。那么我们将value变为13+57+90=160，

                 然后去掉高位“1”,此时key=60，哈哈，这就是他们的哈希关系，这样做的目的就是key与每一位value都相

                 关，来做到“散列地址”尽可能分散的目地。

 

正所谓常在河边走，哪有不湿鞋。哈希也一样，你哈希函数设计的再好，搞不好哪一次就撞楼了，那么抛给我们的问题

就是如果来解决“散列地址“的冲突。

 

其实解决冲突常用的手法也就2种：

 

第一种： “开放地址法“。

                 所谓”开放地址“，其实就是数组中未使用的地址。也就是说，在发生冲突的地方，后到的那个元素（可采用两种方式

                 :①线性探测，②函数探测）向数组后寻找"开放地址“然后把自己插进入。

 

第二种：”链接法“。

                这个大家暂时不懂也没关系，我就先介绍一下原理，就是在每个元素上放一个”指针域“，在发生冲突的地方，后到的那

               个元素将自己的数据域抛给冲突中的元素，此时冲突的地方就形成了一个链表。

 

上面啰嗦了那么多，也就是想让大家在”设计哈希“和”解决冲突“这两个方面提一点参考和手段。

 

那么下面就上代码了，

     设计函数采用：”除法取余法“。

     冲突方面采用:”开放地址线性探测法"。

[java] view plaincopy
  1.   
[java] view plaincopy
  1. using System;  
  2. using System.Collections.Generic;  
  3. using System.Linq;  
  4. using System.Text;  
  5.   
  6. namespace HashSearch  
  7. {  
  8.     class Program  
  9.     {  
  10.         //“除法取余法”  
  11.         static int hashLength = 13;  
  12.   
  13.         //原数据  
  14.         static List<int> list = new List<int>() { 13, 29, 27, 28, 26, 30, 38 };  
  15.   
  16.         //哈希表长度  
  17.         static int[] hash = new int[hashLength];  
  18.   
  19.         static void Main(string[] args)  
  20.         {  
  21.             //创建hash  
  22.             for (int i = 0; i < list.Count; i++)  
  23.             {  
  24.                 InsertHash(hash, hashLength, list[i]);  
  25.             }  
  26.   
  27.             Console.WriteLine("Hash数据：" + string.Join(",", hash));  
  28.   
  29.             while (true)  
  30.             {  
  31.                 Console.WriteLine("\n请输入要查找数字：");  
  32.                 int result = int.Parse(Console.ReadLine());  
  33.                 var index = SearchHash(hash, hashLength, result);  
  34.   
  35.                 if (index != -1)  
  36.                     Console.WriteLine("数字" + result + "在索引的位置是:" + index);  
  37.                 else  
  38.                     Console.WriteLine("呜呜，" + result + " 在hash中没有找到！");  
  39.   
  40.             }  
  41.         }  
  42.   
  43.         ///<summary>  
  44. /// Hash表检索数据  
  45. ///</summary>  
  46. ///<param name="dic"></param>  
  47. ///<param name="hashLength"></param>  
  48. ///<param name="key"></param>  
  49. ///<returns></returns>  
  50.         static int SearchHash(int[] hash, int hashLength, int key)  
  51.         {  
  52.             //哈希函数  
  53.             int hashAddress = key % hashLength;  
  54.   
  55.             //指定hashAdrress对应值存在但不是关键值，则用开放寻址法解决  
  56.             while (hash[hashAddress] != 0 && hash[hashAddress] != key)  
  57.             {  
  58.                 hashAddress = (++hashAddress) % hashLength;  
  59.             }  
  60.   
  61.             //查找到了开放单元，表示查找失败  
  62.             if (hash[hashAddress] == 0)  
  63.                 return -1;  
  64.             return hashAddress;  
  65.   
  66.         }  
  67.   
  68.         ///<summary>  
  69. ///数据插入Hash表  
  70. ///</summary>  
  71. ///<param name="dic">哈希表</param>  
  72. ///<param name="hashLength"></param>  
  73. ///<param name="data"></param>  
  74.         static void InsertHash(int[] hash, int hashLength, int data)  
  75.         {  
  76.             //哈希函数  
  77.             int hashAddress = data % 13;  
  78.   
  79.             //如果key存在，则说明已经被别人占用，此时必须解决冲突  
  80.             while (hash[hashAddress] != 0)  
  81.             {  
  82.                 //用开放寻址法找到  
  83.                 hashAddress = (++hashAddress) % hashLength;  
  84.             }  
  85.   
  86.             //将data存入字典中  
  87.             hash[hashAddress] = data;  
  88.         }  
  89.     }  
  90. }  


结果：

 

 

索引查找：

     一提到“索引”，估计大家第一反应就是“数据库索引”，对的，其实主键建立“索引”，就是方便我们在海量数据中查找。

关于“索引”的知识，估计大家都比我清楚，我就简单介绍下。

我们自己写算法来实现索引查找时常使用的三个术语：

第一：主表，      这个很简单，要查找的对象。

第二：索引项，   一般我们会用函数将一个主表划分成几个子表，每个子表建立一个索引，这个索引叫做索引项。

第三：索引表,    索引项的集合也就是索引表。

 

一般“索引项”包含三种内容：index，start，length

第一： index，也就是索引指向主表的关键字。

第二：start， 也就是index在主表中的位置。

第三：length, 也就是子表的区间长度。

[java] view plaincopy
  1. using System;  
  2. using System.Collections.Generic;  
  3. using System.Linq;  
  4. using System.Text;  
  5.   
  6. namespace IndexSearchProgram  
  7. {  
  8.     class Program  
  9.     {  
  10.         ///<summary>  
  11. /// 索引项实体  
  12. ///</summary>  
  13.         class IndexItem  
  14.         {  
  15.             //对应主表的值  
  16.             public int index;  
  17.             //主表记录区间段的开始位置  
  18.             public int start;  
  19.             //主表记录区间段的长度  
  20.             public int length;  
  21.         }  
  22.   
  23.         static void Main(string[] args)  
  24.         {  
  25.             Console.WriteLine("原数据为：" + string.Join(",", students));  
  26.   
  27.   
  28.             int value = 205;  
  29.   
  30.             Console.WriteLine("\n插入数据" + value);  
  31.   
  32.             //将205插入集合中，过索引  
  33.             var index = insert(value);  
  34.   
  35.             //如果插入成功，获取205元素所在的位置  
  36.             if (index == 1)  
  37.             {  
  38.                 Console.WriteLine("\n插入后数据：" + string.Join(",", students));  
  39.                 Console.WriteLine("\n数据元素：205在数组中的位置为 " + indexSearch(205) + "位");  
  40.             }  
  41.   
  42.             Console.ReadLine();  
  43.         }  
  44.   
  45.         ///<summary>  
  46. /// 学生主表  
  47. ///</summary>  
  48.         static int[] students = {   
  49.                                    101,102,103,104,105,0,0,0,0,0,  
  50.                                    201,202,203,204,0,0,0,0,0,0,  
  51.                                    301,302,303,0,0,0,0,0,0,0  
  52.                                 };  
  53.         ///<summary>  
  54. ///学生索引表  
  55. ///</summary>  
  56.         static IndexItem[] indexItem = {   
  57.                                   new IndexItem(){ index=1, start=0, length=5},  
  58.                                   new IndexItem(){ index=2, start=10, length=4},  
  59.                                   new IndexItem(){ index=3, start=20, length=3},  
  60.                                 };  
  61.   
  62.         ///<summary>  
  63. /// 查找数据  
  64. ///</summary>  
  65. ///<param name="key"></param>  
  66. ///<returns></returns>  
  67.         public static int indexSearch(int key)  
  68.         {  
  69.             IndexItem item = null;  
  70.   
  71.             // 建立索引规则  
  72.             var index = key / 100;  
  73.   
  74.             //首先去索引找  
  75.             for (int i = 0; i < indexItem.Count(); i++)  
  76.             {  
  77.                 if (indexItem[i].index == index)  
  78.                 {  
  79.                     item = new IndexItem() { start = indexItem[i].start, length = indexItem[i].length };  
  80.                     break;  
  81.                 }  
  82.             }  
  83.   
  84.             //如果item为null，则说明在索引中查找失败  
  85.             if (item == null)  
  86.                 return -1;  
  87.   
  88.             for (int i = item.start; i < item.start + item.length; i++)  
  89.             {  
  90.                 if (students[i] == key)  
  91.                 {  
  92.                     return i;  
  93.                 }  
  94.             }  
  95.             return -1;  
  96.         }  
  97.   
  98.         ///<summary>  
  99. /// 插入数据  
  100. ///</summary>  
  101. ///<param name="key"></param>  
  102. ///<returns></returns>  
  103.         public static int insert(int key)  
  104.         {  
  105.             IndexItem item = null;  
  106.             //建立索引规则  
  107.             var index = key / 100;  
  108.             int i = 0;  
  109.             for (i = 0; i < indexItem.Count(); i++)  
  110.             {  
  111.                 //获取到了索引  
  112.                 if (indexItem[i].index == index)  
  113.                 {  
  114.                     item = new IndexItem()  
  115.                     {  
  116.                         start = indexItem[i].start,  
  117.                         length = indexItem[i].length  
  118.                     };  
  119.                     break;  
  120.                 }  
  121.             }  
  122.             if (item == null)  
  123.                 return -1;  
  124.             //更新主表  
  125.             students[item.start + item.length] = key;  
  126.             //更新索引表  
  127.             indexItem[i].length++;  
  128.             return 1;  
  129.         }  
  130.     }  
  131. }  


结果：

 

ps： 哈希查找时间复杂度O(1)。

       索引查找时间复杂度：就拿上面的Demo来说是等于O(n/3)+O(length)



”五大经典查找“中的最后一个”二叉排序树“。

 

1. 概念:

     <1> 其实很简单，若根节点有左子树，则左子树的所有节点都比根节点小。

                             若根节点有右子树，则右子树的所有节点都比根节点大。

     <2> 如图就是一个”二叉排序树“，然后对照概念一比较比较。

              

         

2.实际操作：

    我们都知道，对一个东西进行操作，无非就是增删查改，接下来我们就聊聊其中的基本操作。

    <1> 插入：相信大家对“排序树”的概念都清楚了吧，那么插入的原理就很简单了。

                    比如说我们插入一个20到这棵树中。

                                 首先：20跟50比，发现20是老小，不得已，得要归结到50的左子树中去比较。

                                 然后：20跟30比，发现20还是老小。

                              再然后：20跟10比，发现自己是老大，随即插入到10的右子树中。

                                 最后： 效果呈现图如下：

               

               

    <2>查找：相信懂得了插入，查找就跟容易理解了。

                    就拿上面一幅图来说，比如我想找到节点10.

                                     首先：10跟50比，发现10是老小，则在50的左子树中找。

                                     然后：10跟30比，发现还是老小，则在30的左子树中找。

                                  再然后:  10跟10比，发现一样，然后就返回找到的信号。

                

     <3>删除：删除节点在树中还是比较麻烦的，主要有三种情况。

                   《1》 删除的是“叶节点20“，这种情况还是比较简单的，删除20不会破坏树的结构。如图：

                    

                      

                   《2》删除”单孩子节点90“，这个情况相比第一种要麻烦一点点，需要把他的孩子顶上去。

                    

                       

                   《3》删除“左右孩子都有的节点50”，这个让我在代码编写上纠结了好长时间，问题很直白，

                           我把50删掉了，谁顶上去了问题，是左孩子呢？还是右孩子呢？还是另有蹊跷？这里我就

                           坦白吧，不知道大家可否知道“二叉树”的中序遍历，不过这个我会在后面讲的，现在可以当

                          公式记住吧，就是找到右节点的左子树最左孩子。

                          比如：首先 找到50的右孩子70。

                                  然后  找到70的最左孩子，发现没有，则返回自己。

                                  最后  原始图和最终图如下。 

  

 

3.说了这么多，上代码说话。

[java] view plaincopy
  1. using System;  
  2. using System.Collections.Generic;  
  3. using System.Linq;  
  4. using System.Text;  
  5. using System.Diagnostics;  
  6.   
  7. namespace TreeSearch  
  8. {  
  9.     class Program  
  10.     {  
  11.         static void Main(string[] args)  
  12.         {  
  13.             List<int> list = new List<int>() { 50, 30, 70, 10, 40, 90, 80 };  
  14.   
  15.             //创建二叉遍历树  
  16.             BSTree bsTree = CreateBST(list);  
  17.   
  18.             Console.Write("中序遍历的原始数据：");  
  19.   
  20.             //中序遍历  
  21.             LDR_BST(bsTree);  
  22.   
  23.             Console.WriteLine("\n---------------------------------------------------------------------------n");  
  24.   
  25.             //查找一个节点  
  26.             Console.WriteLine("\n10在二叉树中是否包含：" + SearchBST(bsTree, 10));  
  27.   
  28.             Console.WriteLine("\n---------------------------------------------------------------------------n");  
  29.   
  30.             bool isExcute = false;  
  31.   
  32.             //插入一个节点  
  33.             InsertBST(bsTree, 20, ref isExcute);  
  34.   
  35.             Console.WriteLine("\n20插入到二叉树，中序遍历后：");  
  36.   
  37.             //中序遍历  
  38.             LDR_BST(bsTree);  
  39.   
  40.             Console.WriteLine("\n---------------------------------------------------------------------------n");  
  41.   
  42.             Console.Write("删除叶子节点 20， \n中序遍历后：");  
  43.   
  44.             //删除一个节点(叶子节点)  
  45.             DeleteBST(ref bsTree, 20);  
  46.   
  47.             //再次中序遍历  
  48.             LDR_BST(bsTree);  
  49.   
  50.             Console.WriteLine("\n****************************************************************************\n");  
  51.   
  52.             Console.WriteLine("删除单孩子节点 90， \n中序遍历后：");  
  53.   
  54.             //删除单孩子节点  
  55.             DeleteBST(ref bsTree, 90);  
  56.   
  57.             //再次中序遍历  
  58.             LDR_BST(bsTree);  
  59.   
  60.             Console.WriteLine("\n****************************************************************************\n");  
  61.   
  62.             Console.WriteLine("删除根节点 50， \n中序遍历后：");  
  63.             //删除根节点  
  64.             DeleteBST(ref bsTree, 50);  
  65.   
  66.             LDR_BST(bsTree);  
  67.   
  68.         }  
  69.   
  70.         ///<summary>  
  71. /// 定义一个二叉排序树结构  
  72. ///</summary>  
  73.         public class BSTree  
  74.         {  
  75.             public int data;  
  76.             public BSTree left;  
  77.             public BSTree right;  
  78.         }  
  79.   
  80.         ///<summary>  
  81. /// 二叉排序树的插入操作  
  82. ///</summary>  
  83. ///<param name="bsTree">排序树</param>  
  84. ///<param name="key">插入数</param>  
  85. ///<param name="isExcute">是否执行了if语句</param>  
  86.         static void InsertBST(BSTree bsTree, int key, ref bool isExcute)  
  87.         {  
  88.             if (bsTree == null)  
  89.                 return;  
  90.   
  91.             //如果父节点大于key，则遍历左子树  
  92.             if (bsTree.data > key)  
  93.                 InsertBST(bsTree.left, key, ref isExcute);  
  94.             else  
  95.                 InsertBST(bsTree.right, key, ref isExcute);  
  96.   
  97.             if (!isExcute)  
  98.             {  
  99.                 //构建当前节点  
  100.                 BSTree current = new BSTree()  
  101.                   {  
  102.                       data = key,  
  103.                       left = null,  
  104.                       right = null  
  105.                   };  
  106.   
  107.                 //插入到父节点的当前元素  
  108.                 if (bsTree.data > key)  
  109.                     bsTree.left = current;  
  110.                 else  
  111.                     bsTree.right = current;  
  112.   
  113.                 isExcute = true;  
  114.             }  
  115.   
  116.         }  
  117.   
  118.         ///<summary>  
  119. /// 创建二叉排序树  
  120. ///</summary>  
  121. ///<param name="list"></param>  
  122.         static BSTree CreateBST(List<int> list)  
  123.         {  
  124.             //构建BST中的根节点  
  125.             BSTree bsTree = new BSTree()  
  126.             {  
  127.                 data = list[0],  
  128.                 left = null,  
  129.                 right = null  
  130.             };  
  131.   
  132.             for (int i = 1; i < list.Count; i++)  
  133.             {  
  134.                 bool isExcute = false;  
  135.                 InsertBST(bsTree, list[i], ref isExcute);  
  136.             }  
  137.             return bsTree;  
  138.         }  
  139.   
  140.         ///<summary>  
  141. /// 在排序二叉树中搜索指定节点  
  142. ///</summary>  
  143. ///<param name="bsTree"></param>  
  144. ///<param name="key"></param>  
  145. ///<returns></returns>  
  146.         static bool SearchBST(BSTree bsTree, int key)  
  147.         {  
  148.             //如果bsTree为空，说明已经遍历到头了  
  149.             if (bsTree == null)  
  150.                 return false;  
  151.   
  152.             if (bsTree.data == key)  
  153.                 return true;  
  154.   
  155.             if (bsTree.data > key)  
  156.                 return SearchBST(bsTree.left, key);  
  157.             else  
  158.                 return SearchBST(bsTree.right, key);  
  159.         }  
  160.   
  161.         ///<summary>  
  162. /// 中序遍历二叉排序树  
  163. ///</summary>  
  164. ///<param name="bsTree"></param>  
  165. ///<returns></returns>  
  166.         static void LDR_BST(BSTree bsTree)  
  167.         {  
  168.             if (bsTree != null)  
  169.             {  
  170.                 //遍历左子树  
  171.                 LDR_BST(bsTree.left);  
  172.   
  173.                 //输入节点数据  
  174.                 Console.Write(bsTree.data + "");  
  175.   
  176.                 //遍历右子树  
  177.                 LDR_BST(bsTree.right);  
  178.             }  
  179.         }  
  180.   
  181.         ///<summary>  
  182. /// 删除二叉排序树中指定key节点  
  183. ///</summary>  
  184. ///<param name="bsTree"></param>  
  185. ///<param name="key"></param>  
  186.         static void DeleteBST(ref BSTree bsTree, int key)  
  187.         {  
  188.             if (bsTree == null)  
  189.                 return;  
  190.   
  191.             if (bsTree.data == key)  
  192.             {  
  193.                 //第一种情况：叶子节点  
  194.                 if (bsTree.left == null && bsTree.right == null)  
  195.                 {  
  196.                     bsTree = null;  
  197.                     return;  
  198.                 }  
  199.                 //第二种情况：左子树不为空  
  200.                 if (bsTree.left != null && bsTree.right == null)  
  201.                 {  
  202.                     bsTree = bsTree.left;  
  203.                     return;  
  204.                 }  
  205.                 //第三种情况，右子树不为空  
  206.                 if (bsTree.left == null && bsTree.right != null)  
  207.                 {  
  208.                     bsTree = bsTree.right;  
  209.                     return;  
  210.                 }  
  211.                 //第四种情况，左右子树都不为空  
  212.                 if (bsTree.left != null && bsTree.right != null)  
  213.                 {  
  214.                     var node = bsTree.right;  
  215.   
  216.                     //找到右子树中的最左节点  
  217.                     while (node.left != null)  
  218.                     {  
  219.                         //遍历它的左子树  
  220.                         node = node.left;  
  221.                     }  
  222.   
  223.                     //交换左右孩子  
  224.                     node.left = bsTree.left;  
  225.   
  226.                     //判断是真正的叶子节点还是空左孩子的父节点  
  227.                     if (node.right == null)  
  228.                     {  
  229.                         //删除掉右子树最左节点  
  230.                         DeleteBST(ref bsTree, node.data);  
  231.   
  232.                         node.right = bsTree.right;  
  233.                     }  
  234.                     //重新赋值一下  
  235.                     bsTree = node;  
  236.   
  237.                 }  
  238.             }  
  239.   
  240.             if (bsTree.data > key)  
  241.             {  
  242.                 DeleteBST(ref bsTree.left, key);  
  243.             }  
  244.             else  
  245.             {  
  246.                 DeleteBST(ref bsTree.right, key);  
  247.             }  
  248.         }  
  249.     }  
  250. }  


运行结果：

 

值的注意的是：二叉排序树同样采用“空间换时间”的做法。

突然发现，二叉排序树的中序遍历同样可以排序数组，呵呵，不错！

 

PS:  插入操作：O(LogN)。

       删除操作：O(LogN)。

       查找操作：O(LogN）。

相关文章

最新文章