算法连串15天速成

我们是或不是感到到,树在数据结构中流行,什么领域都要沾一沾,碰一碰。

我们是或不是觉获得,树在数据结构中流行,什么领域都要沾一沾,碰一碰。

就拿大家后天学过的排序就用到了堆和明日讲的”二叉排序树“,所以偏激的说,了解的树你正是牛人了。

就拿大家前天学过的排序就用到了堆和今日讲的”二叉排序树“,所以偏激的说,精通的树你就是牛人了。

 

 

明天就推搡那几个”中国共产党第五次全国代表大会经典查找“中的最终二个”二叉排序树“。

前些天就推来推去那几个”中国共产党第五次全国代表大会经典查找“中的最终二个”二叉排序树“。

 

 

  1. 概念:
  1. 概念:

     <1>
其实很简短,若根节点有左子树,则左子树的兼具节点都比根节点小。

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

                           
 若根节点有右子树,则右子树的有着节点都比根节点大。

                           
 若根节点有右子树,则右子树的全体节点都比根节点大。

     <2> 如图就是1个”二叉排序树“,然后相比较概念一比较比较。

     <2> 如图正是多个”二叉排序树“,然后比较概念一相比较比较。

              

              

         葡京投注开户 1

         葡京投注开户 2

2.实操:

2.实操:

   
大家都清楚,对2个东西进行操作,无非正是增加和删除查改,接下去大家就推搡当中的基本操作。

   
大家都了解,对贰个事物进行操作,无非就是增加和删除查改,接下去大家就拉扯个中的基本操作。

    <1>
插入:相信我们对“排序树”的定义都明白了啊,那么插入的法则就非常的粗略了。

    <1>
插入:相信我们对“排序树”的定义都晓得了呢,那么插入的法则就很简短了。

                    比如说大家插入一个20到那棵树中。

                    比如说我们插入二个20到那棵树中。

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

                               
 首先:20跟50比,发现20是老小,不得已,得要归咎到50的左子树中去相比较。

                                 然后:20跟30比,发现20或许家人。

                                 然后:20跟30比,发现20照旧亲戚。

                             
再然后:20跟10比,发现自身是万分,随即插入到10的右子树中。

                             
再然后:20跟10比,发现自个儿是老大,随即插入到10的右子树中。

                                 最终: 效果表现图如下:

                                 最终: 效果表现图如下:

               

               

               葡京投注开户 3

               葡京投注开户 4

    <2>查找:相信精晓了插入,查找就跟简单了解了。

    <2>查找:相信领会了插入,查找就跟简单了然了。

                    就拿位置一幅图来说,比如作者想找到节点10.

                    就拿地点一幅图来说,比如小编想找到节点10.

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

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

                                   
 然后:10跟30比,发现照旧亲朋好友,则在30的左子树中找。

                                   
 然后:10跟30比,发现依然亲朋好友,则在30的左子树中找。

                                  再接下来:
 10跟10比,发现同样,然后就回到找到的信号。

                                  再然后:
 10跟10比,发现同样,然后就回到找到的信号。

                

                

     <3>删除:删除节点在树中依旧相比较麻烦的,首要有三种情景。

     <3>删除:删除节点在树中依旧比较费心的,主要有三种情景。

                   《1》
删除的是“叶节点20“,这种状态依旧比较简单的,删除20不会破坏树的结构。如图:

                   《1》
删除的是“叶节点20“,这种意况依旧比较不难的,删除20不会破坏树的构造。如图:

葡京投注开户,                    

                    

                      葡京投注开户 5

                      葡京投注开户 6

                 
 《2》删除”单孩子节点90“,那个情状相比较第壹种要麻烦一丝丝,须要把他的男女顶上去。

                 
 《2》删除”单孩子节点90“,这几个情况比较第③种要麻烦一丢丢,须求把他的孩子顶上去。

                    

                    

                       葡京投注开户 7

                       葡京投注开户 8

                 
 《3》删除“左右孩子都有个别节点50”,那一个让小编在代码编写上纠结了好长期,难题很直接,

                 
 《3》删除“左右亲骨肉都有的节点50”,这几个让自个儿在代码编写上纠结了好长期,难点很直白,

                         
 我把50删掉了,哪个人顶上去了难题,是左孩子呢?照旧右孩子呢?照旧另有蹊跷?那里本人就

                         
 作者把50删掉了,何人顶上去了难题,是左孩子吗?照旧右孩子呢?依旧另有好奇?那里自个儿就

                         
 坦白吧,不亮堂大家是不是知道“二叉树”的中序遍历,但是这几个笔者会在后头讲的,今后能够当

                         
 坦白吧,不晓得大家是不是知道“二叉树”的中序遍历,然而那些作者会在背后讲的,今后得以当

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

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

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

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

                                  然后
 找到70的最左孩子,发现并未,则赶回本人。

                                  然后
 找到70的最左孩子,发现没有,则赶回本人。

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

                                  最后  原始图和结尾图如下。 

 葡京投注开户 9 葡京投注开户 10

 葡京投注开户 11 葡京投注开户 12

 

 

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

3.说了那般多,上代码说话。

  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 }

葡京投注开户 13

运作结果:

  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 }

葡京投注开户 14

葡京投注开户 15

 

运营结果:

值的令人瞩目标是:二叉排序树同样使用“空间换时间”的做法。

葡京投注开户 16

突然意识,二叉排序树的中序遍历同样能够排序数组,呵呵,不错!

 

 

值的小心的是:二叉排序树同样利用“空间换时间”的做法。

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

忽然意识,二叉排序树的中序遍历同样能够排序数组,呵呵,不错!

       删除操作:O(LogN)。

 

       查找操作:O(LogN)。

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

       删除操作:O(LogN)。

       查找操作:O(LogN)。

相关文章