算法系列15天速成 第六天 五大经典查找【下】

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.说了这么多，上代码说话。

复制代码 代码如下:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Diagnostics;

namespace TreeSearch
{
    class Program
    {
        static void Main(string[] args)
        {
            List<int> list = new List<int>() { 50, 30, 70, 10, 40, 90, 80 };

//创建二叉遍历树
            BSTree bsTree = CreateBST(list);

Console.Write("中序遍历的原始数据：");

//中序遍历
            LDR_BST(bsTree);

Console.WriteLine("n---------------------------------------------------------------------------n");

//查找一个节点
            Console.WriteLine("n10在二叉树中是否包含：" + SearchBST(bsTree, 10));

Console.WriteLine("n---------------------------------------------------------------------------n");

bool isExcute = false;

//插入一个节点
            InsertBST(bsTree, 20, ref isExcute);

Console.WriteLine("n20插入到二叉树，中序遍历后：");

//中序遍历
            LDR_BST(bsTree);

Console.WriteLine("n---------------------------------------------------------------------------n");

Console.Write("删除叶子节点 20， n中序遍历后：");

//删除一个节点(叶子节点)
            DeleteBST(ref bsTree, 20);

//再次中序遍历
            LDR_BST(bsTree);

Console.WriteLine("n****************************************************************************n");

Console.WriteLine("删除单孩子节点 90， n中序遍历后：");

//删除单孩子节点
            DeleteBST(ref bsTree, 90);

//再次中序遍历
            LDR_BST(bsTree);

Console.WriteLine("n****************************************************************************n");

（编辑：焦作站长网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!