快捷導(dǎo)航

算法系列15天速成第六天五大經(jīng)典查找【下】

更新時間：2013年11月10日 10:30:55 作者：

大家是否感覺到，樹在數(shù)據(jù)結(jié)構(gòu)中大行其道，什么領(lǐng)域都要沾一沾，碰一碰

大家是否感覺到，樹在數(shù)據(jù)結(jié)構(gòu)中大行其道，什么領(lǐng)域都要沾一沾，碰一碰。
就拿我們前幾天學(xué)過的排序就用到了堆和今天講的”二叉排序樹“，所以偏激的說，掌握的樹你就是牛人了。

今天就聊聊這個”五大經(jīng)典查找“中的最后一個”二叉排序樹“。

1. 概念:
     <1> 其實很簡單，若根節(jié)點(diǎn)有左子樹，則左子樹的所有節(jié)點(diǎn)都比根節(jié)點(diǎn)小。
                             若根節(jié)點(diǎn)有右子樹，則右子樹的所有節(jié)點(diǎn)都比根節(jié)點(diǎn)大。
     <2> 如圖就是一個”二叉排序樹“，然后對照概念一比較比較。

2.實際操作：

我們都知道，對一個東西進(jìn)行操作，無非就是增刪查改，接下來我們就聊聊其中的基本操作。

<1> 插入：相信大家對“排序樹”的概念都清楚了吧，那么插入的原理就很簡單了。

比如說我們插入一個20到這棵樹中。

首先：20跟50比，發(fā)現(xiàn)20是老小，不得已，得要?dú)w結(jié)到50的左子樹中去比較。

然后：20跟30比，發(fā)現(xiàn)20還是老小。

再然后：20跟10比，發(fā)現(xiàn)自己是老大，隨即插入到10的右子樹中。

最后：效果呈現(xiàn)圖如下：

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

就拿上面一幅圖來說，比如我想找到節(jié)點(diǎn)10.

首先：10跟50比，發(fā)現(xiàn)10是老小，則在50的左子樹中找。

然后：10跟30比，發(fā)現(xiàn)還是老小，則在30的左子樹中找。

再然后: 10跟10比，發(fā)現(xiàn)一樣，然后就返回找到的信號。

<3>刪除：刪除節(jié)點(diǎn)在樹中還是比較麻煩的，主要有三種情況。

《1》刪除的是“葉節(jié)點(diǎn)20“，這種情況還是比較簡單的，刪除20不會破壞樹的結(jié)構(gòu)。如圖：

《2》刪除”單孩子節(jié)點(diǎn)90“，這個情況相比第一種要麻煩一點(diǎn)點(diǎn)，需要把他的孩子頂上去。

《3》刪除“左右孩子都有的節(jié)點(diǎn)50”，這個讓我在代碼編寫上糾結(jié)了好長時間，問題很直白，

我把50刪掉了，誰頂上去了問題，是左孩子呢？還是右孩子呢？還是另有蹊蹺？這里我就

坦白吧，不知道大家可否知道“二叉樹”的中序遍歷，不過這個我會在后面講的，現(xiàn)在可以當(dāng)

公式記住吧，就是找到右節(jié)點(diǎn)的左子樹最左孩子。

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

然后找到70的最左孩子，發(fā)現(xiàn)沒有，則返回自己。

最后原始圖和最終圖如下。

3.說了這么多，上代碼說話。

復(fù)制代碼代碼如下:

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 };

//創(chuàng)建二叉遍歷樹
BSTree bsTree = CreateBST(list);

Console.Write("中序遍歷的原始數(shù)據(jù)：");

//中序遍歷
LDR_BST(bsTree);

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

//查找一個節(jié)點(diǎn)
Console.WriteLine("\n10在二叉樹中是否包含：" + SearchBST(bsTree, 10));

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

bool isExcute = false;

//插入一個節(jié)點(diǎn)
InsertBST(bsTree, 20, ref isExcute);

Console.WriteLine("\n20插入到二叉樹，中序遍歷后：");

//中序遍歷
LDR_BST(bsTree);

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

Console.Write("刪除葉子節(jié)點(diǎn) 20， \n中序遍歷后：");

//刪除一個節(jié)點(diǎn)(葉子節(jié)點(diǎn))
DeleteBST(ref bsTree, 20);

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

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

Console.WriteLine("刪除單孩子節(jié)點(diǎn) 90， \n中序遍歷后：");

//刪除單孩子節(jié)點(diǎn)
DeleteBST(ref bsTree, 90);

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

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

            Console.WriteLine("刪除根節(jié)點(diǎn) 50， \n中序遍歷后：");
            //刪除根節(jié)點(diǎn)
            DeleteBST(ref bsTree, 50);

LDR_BST(bsTree);

}

        ///<summary>
/// 定義一個二叉排序樹結(jié)構(gòu)
///</summary>
        public class BSTree
        {
            public int data;
            public BSTree left;
            public BSTree right;
        }

        ///<summary>
/// 二叉排序樹的插入操作
///</summary>
///<param name="bsTree">排序樹</param>
///<param name="key">插入數(shù)</param>
///<param name="isExcute">是否執(zhí)行了if語句</param>
        static void InsertBST(BSTree bsTree, int key, ref bool isExcute)
        {
            if (bsTree == null)
                return;

            //如果父節(jié)點(diǎn)大于key，則遍歷左子樹
            if (bsTree.data > key)
                InsertBST(bsTree.left, key, ref isExcute);
            else
                InsertBST(bsTree.right, key, ref isExcute);

            if (!isExcute)
            {
                //構(gòu)建當(dāng)前節(jié)點(diǎn)
                BSTree current = new BSTree()
                  {
                      data = key,
                      left = null,
                      right = null
                  };

                //插入到父節(jié)點(diǎn)的當(dāng)前元素
                if (bsTree.data > key)
                    bsTree.left = current;
                else
                    bsTree.right = current;

isExcute = true;
}

}

        ///<summary>
/// 創(chuàng)建二叉排序樹
///</summary>
///<param name="list"></param>
        static BSTree CreateBST(List<int> list)
        {
            //構(gòu)建BST中的根節(jié)點(diǎn)
            BSTree bsTree = new BSTree()
            {
                data = list[0],
                left = null,
                right = null
            };

            for (int i = 1; i < list.Count; i++)
            {
                bool isExcute = false;
                InsertBST(bsTree, list[i], ref isExcute);
            }
            return bsTree;
        }

        ///<summary>
/// 在排序二叉樹中搜索指定節(jié)點(diǎn)
///</summary>
///<param name="bsTree"></param>
///<param name="key"></param>
///<returns></returns>
        static bool SearchBST(BSTree bsTree, int key)
        {
            //如果bsTree為空，說明已經(jīng)遍歷到頭了
            if (bsTree == null)
                return false;

if (bsTree.data == key)
return true;

            if (bsTree.data > key)
                return SearchBST(bsTree.left, key);
            else
                return SearchBST(bsTree.right, key);
        }

        ///<summary>
/// 中序遍歷二叉排序樹
///</summary>
///<param name="bsTree"></param>
///<returns></returns>
        static void LDR_BST(BSTree bsTree)
        {
            if (bsTree != null)
            {
                //遍歷左子樹
                LDR_BST(bsTree.left);

//輸入節(jié)點(diǎn)數(shù)據(jù)
Console.Write(bsTree.data + "");

                //遍歷右子樹
                LDR_BST(bsTree.right);
            }
        }

        ///<summary>
/// 刪除二叉排序樹中指定key節(jié)點(diǎn)
///</summary>
///<param name="bsTree"></param>
///<param name="key"></param>
        static void DeleteBST(ref BSTree bsTree, int key)
        {
            if (bsTree == null)
                return;

            if (bsTree.data == key)
            {
                //第一種情況：葉子節(jié)點(diǎn)
                if (bsTree.left == null && bsTree.right == null)
                {
                    bsTree = null;
                    return;
                }
                //第二種情況：左子樹不為空
                if (bsTree.left != null && bsTree.right == null)
                {
                    bsTree = bsTree.left;
                    return;
                }
                //第三種情況，右子樹不為空
                if (bsTree.left == null && bsTree.right != null)
                {
                    bsTree = bsTree.right;
                    return;
                }
                //第四種情況，左右子樹都不為空
                if (bsTree.left != null && bsTree.right != null)
                {
                    var node = bsTree.right;

                    //找到右子樹中的最左節(jié)點(diǎn)
                    while (node.left != null)
                    {
                        //遍歷它的左子樹
                        node = node.left;
                    }

//交換左右孩子
node.left = bsTree.left;

                    //判斷是真正的葉子節(jié)點(diǎn)還是空左孩子的父節(jié)點(diǎn)
                    if (node.right == null)
                    {
                        //刪除掉右子樹最左節(jié)點(diǎn)
                        DeleteBST(ref bsTree, node.data);

                        node.right = bsTree.right;
                    }
                    //重新賦值一下
                    bsTree = node;

}
}

            if (bsTree.data > key)
            {
                DeleteBST(ref bsTree.left, key);
            }
            else
            {
                DeleteBST(ref bsTree.right, key);
            }
        }
    }
}

運(yùn)行結(jié)果：