算法系列15天速成——第六天 五大经典查找【下】
大家是否感觉到，树在数据结构中大行其道，什么领域都要沾一沾，碰一碰。
就拿我们前几天学过的排序就用到了堆和今天讲的”二叉排序树“，所以偏激的说，掌握的树你就是牛人了。
今天就聊聊这个”五大经典查找“中的最后一个”二叉排序树“。
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.说了这么多，上代码说话。
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 //中序遍历
补充：软件开发 , 其他 ,
