<em id="hanht"></em>

    <dd id="hanht"></dd>

    <em id="hanht"><acronym id="hanht"></acronym></em>
    
    <button id="hanht"></button>
    <rp id="hanht"><object id="hanht"><blockquote id="hanht"></blockquote></object></rp><em id="hanht"></em>

    首頁 > 學院 > 邏輯算法 > 正文

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

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

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

    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.說了這么多,上代碼說話。

    復制代碼 代碼如下:

    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");

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

                LDR_BST(bsTree);

            }

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

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

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

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

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

                    isExcute = true;
                }

            }

            ///<summary>
    /// 創建二叉排序樹
    ///</summary>
    ///<param name="list"></param>
            static BSTree CreateBST(List<int> list)
            {
                //構建BST中的根節點
                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>
    /// 在排序二叉樹中搜索指定節點
    ///</summary>
    ///<param name="bsTree"></param>
    ///<param name="key"></param>
    ///<returns></returns>
            static bool SearchBST(BSTree bsTree, int key)
            {
                //如果bsTree為空,說明已經遍歷到頭了
                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);

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

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

            ///<summary>
    /// 刪除二叉排序樹中指定key節點
    ///</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)
                {
                    //第一種情況:葉子節點
                    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;

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

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

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

    運行結果:

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

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

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

    發表評論 共有條評論
    用戶名: 密碼:
    驗證碼: 匿名發表
    一级特黄大片欧美久久久久_一本一道久久综合狠狠老_JLZZ日本人年轻护士_欧美男男作爱VIDEOS可播放
      <em id="hanht"></em>

      <dd id="hanht"></dd>

      <em id="hanht"><acronym id="hanht"></acronym></em>
      
      <button id="hanht"></button>
      <rp id="hanht"><object id="hanht"><blockquote id="hanht"></blockquote></object></rp><em id="hanht"></em>