首頁(yè) > 學(xué)院 > 邏輯算法 > 正文

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

2020-10-08 16:14:35
字體:
來(lái)源:轉載
供稿:網(wǎng)友
大家是否感覺(jué)到,樹(shù)在數據結構中大行其道,什么領(lǐng)域都要沾一沾,碰一碰。
就拿我們前幾天學(xué)過(guò)的排序就用到了堆和今天講的”二叉排序樹(shù)“,所以偏激的說(shuō),掌握的樹(shù)你就是牛人了。

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

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

         

2.實(shí)際操作:

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

    <1> 插入:相信大家對“排序樹(shù)”的概念都清楚了吧,那么插入的原理就很簡(jiǎn)單了。

                    比如說(shuō)我們插入一個(gè)20到這棵樹(shù)中。

                                 首先:20跟50比,發(fā)現20是老小,不得已,得要歸結到50的左子樹(shù)中去比較。

                                 然后:20跟30比,發(fā)現20還是老小。

                              再然后:20跟10比,發(fā)現自己是老大,隨即插入到10的右子樹(shù)中。

                                 最后: 效果呈現圖如下:

               

               

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

                    就拿上面一幅圖來(lái)說(shuō),比如我想找到節點(diǎn)10.

                                     首先:10跟50比,發(fā)現10是老小,則在50的左子樹(shù)中找。

                                     然后:10跟30比,發(fā)現還是老小,則在30的左子樹(shù)中找。

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

                

     <3>刪除:刪除節點(diǎn)在樹(shù)中還是比較麻煩的,主要有三種情況。

                   《1》 刪除的是“葉節點(diǎn)20“,這種情況還是比較簡(jiǎn)單的,刪除20不會(huì )破壞樹(shù)的結構。如圖:

                    

                      

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

                    

                       

                   《3》刪除“左右孩子都有的節點(diǎn)50”,這個(gè)讓我在代碼編寫(xiě)上糾結了好長(cháng)時(shí)間,問(wèn)題很直白,

                           我把50刪掉了,誰(shuí)頂上去了問(wèn)題,是左孩子呢?還是右孩子呢?還是另有蹊蹺?這里我就

                           坦白吧,不知道大家可否知道“二叉樹(shù)”的中序遍歷,不過(guò)這個(gè)我會(huì )在后面講的,現在可以當

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

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

                                  然后  找到70的最左孩子,發(fā)現沒(méi)有,則返回自己。

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

  

 

3.說(shuō)了這么多,上代碼說(shuō)話(huà)。

復制代碼 代碼如下:

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 )建二叉遍歷樹(shù)
            BSTree bsTree = CreateBST(list);

            Console.Write("中序遍歷的原始數據:");

            //中序遍歷
            LDR_BST(bsTree);

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

            //查找一個(gè)節點(diǎn)
            Console.WriteLine("/n10在二叉樹(shù)中是否包含:" + SearchBST(bsTree, 10));

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

            bool isExcute = false;

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

            Console.WriteLine("/n20插入到二叉樹(shù),中序遍歷后:");

            //中序遍歷
            LDR_BST(bsTree);

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

            Console.Write("刪除葉子節點(diǎn) 20, /n中序遍歷后:");

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

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

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

            Console.WriteLine("刪除單孩子節點(diǎn) 90, /n中序遍歷后:");

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

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

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

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

            LDR_BST(bsTree);

        }

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

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

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

            if (!isExcute)
            {
                //構建當前節點(diǎn)
                BSTree current = new BSTree()
                  {
                      data = key,
                      left = null,
                      right = null
                  };

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

                isExcute = true;
            }

        }

        ///<summary>
/// 創(chuàng )建二叉排序樹(shù)
///</summary>
///<param name="list"></param>
        static BSTree CreateBST(List<int> list)
        {
            //構建BST中的根節點(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>
/// 在排序二叉樹(shù)中搜索指定節點(diǎn)
///</summary>
///<param name="bsTree"></param>
///<param name="key"></param>
///<returns></returns>
        static bool SearchBST(BSTree bsTree, int key)
        {
            //如果bsTree為空,說(shuō)明已經(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>
/// 中序遍歷二叉排序樹(shù)
///</summary>
///<param name="bsTree"></param>
///<returns></returns>
        static void LDR_BST(BSTree bsTree)
        {
            if (bsTree != null)
            {
                //遍歷左子樹(shù)
                LDR_BST(bsTree.left);

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

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

        ///<summary>
/// 刪除二叉排序樹(shù)中指定key節點(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)
            {
                //第一種情況:葉子節點(diǎn)
                if (bsTree.left == null && bsTree.right == null)
                {
                    bsTree = null;
                    return;
                }
                //第二種情況:左子樹(shù)不為空
                if (bsTree.left != null && bsTree.right == null)
                {
                    bsTree = bsTree.left;
                    return;
                }
                //第三種情況,右子樹(shù)不為空
                if (bsTree.left == null && bsTree.right != null)
                {
                    bsTree = bsTree.right;
                    return;
                }
                //第四種情況,左右子樹(shù)都不為空
                if (bsTree.left != null && bsTree.right != null)
                {
                    var node = bsTree.right;

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

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

                    //判斷是真正的葉子節點(diǎn)還是空左孩子的父節點(diǎn)
                    if (node.right == null)
                    {
                        //刪除掉右子樹(shù)最左節點(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);
            }
        }
    }
}

運行結果:

值的注意的是:二叉排序樹(shù)同樣采用“空間換時(shí)間”的做法。

突然發(fā)現,二叉排序樹(shù)的中序遍歷同樣可以排序數組,呵呵,不錯!

PS:  插入操作:O(LogN)。
       刪除操作:O(LogN)。
       查找操作:O(LogN)。

發(fā)表評論 共有條評論
用戶(hù)名: 密碼:
驗證碼: 匿名發(fā)表