算法系列15天速成 第六天 五大經典查找【下】
就拿我們前幾天學過的排序就用到了堆和今天講的”二叉排序樹“，所以偏激的說，掌握的樹你就是牛人了。
今天就聊聊這個”五大經典查找“中的最后一個”二叉排序樹“。
1. 概念:
<1> 其實很簡單，若根節(jié)點有左子樹，則左子樹的所有節(jié)點都比根節(jié)點小。
若根節(jié)點有右子樹，則右子樹的所有節(jié)點都比根節(jié)點大。
<2> 如圖就是一個”二叉排序樹“，然后對照概念一比較比較。
2.實際操作：
我們都知道，對一個東西進行操作，無非就是增刪查改，接下來我們就聊聊其中的基本操作。
<1> 插入：相信大家對“排序樹”的概念都清楚了吧，那么插入的原理就很簡單了。
比如說我們插入一個20到這棵樹中。
首先：20跟50比，發(fā)現(xiàn)20是老小，不得已，得要歸結到50的左子樹中去比較。
然后：20跟30比，發(fā)現(xiàn)20還是老小。
再然后：20跟10比，發(fā)現(xiàn)自己是老大，隨即插入到10的右子樹中。
最后： 效果呈現(xiàn)圖如下：
<2>查找：相信懂得了插入，查找就跟容易理解了。
就拿上面一幅圖來說，比如我想找到節(jié)點10.
首先：10跟50比，發(fā)現(xiàn)10是老小，則在50的左子樹中找。
然后：10跟30比，發(fā)現(xiàn)還是老小，則在30的左子樹中找。
再然后: 10跟10比，發(fā)現(xiàn)一樣，然后就返回找到的信號。
<3>刪除：刪除節(jié)點在樹中還是比較麻煩的，主要有三種情況。
《1》 刪除的是“葉節(jié)點20“，這種情況還是比較簡單的，刪除20不會破壞樹的結構。如圖：
《2》刪除”單孩子節(jié)點90“，這個情況相比第一種要麻煩一點點，需要把他的孩子頂上去。
《3》刪除“左右孩子都有的節(jié)點50”，這個讓我在代碼編寫上糾結了好長時間，問題很直白，
我把50刪掉了，誰頂上去了問題，是左孩子呢？還是右孩子呢？還是另有蹊蹺？這里我就
坦白吧，不知道大家可否知道“二叉樹”的中序遍歷，不過這個我會在后面講的，現(xiàn)在可以當
公式記住吧，就是找到右節(jié)點的左子樹最左孩子。
比如：首先 找到50的右孩子70。
然后 找到70的最左孩子，發(fā)現(xiàn)沒有，則返回自己。
最后 原始圖和最終圖如下。
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 };
//創(chuàng)建二叉遍歷樹
BSTree bsTree = CreateBST(list);
Console.Write("中序遍歷的原始數(shù)據(jù)：");
//中序遍歷
LDR_BST(bsTree);
Console.WriteLine("\n---------------------------------------------------------------------------n");
//查找一個節(jié)點
Console.WriteLine("\n10在二叉樹中是否包含：" + SearchBST(bsTree, 10));
Console.WriteLine("\n---------------------------------------------------------------------------n");
bool isExcute = false;
//插入一個節(jié)點
InsertBST(bsTree, 20, ref isExcute);
Console.WriteLine("\n20插入到二叉樹，中序遍歷后：");
//中序遍歷
LDR_BST(bsTree);
Console.WriteLine("\n---------------------------------------------------------------------------n");
Console.Write("刪除葉子節(jié)點 20， \n中序遍歷后：");
//刪除一個節(jié)點(葉子節(jié)點)
DeleteBST(ref bsTree, 20);
//再次中序遍歷
LDR_BST(bsTree);
Console.WriteLine("\n****************************************************************************\n");
Console.WriteLine("刪除單孩子節(jié)點 90， \n中序遍歷后：");
//刪除單孩子節(jié)點
DeleteBST(ref bsTree, 90);
//再次中序遍歷
LDR_BST(bsTree);
Console.WriteLine("\n****************************************************************************\n");
Console.WriteLine("刪除根節(jié)點 50， \n中序遍歷后：");
//刪除根節(jié)點
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">插入數(shù)</param>
///<param name="isExcute">是否執(zhí)行了if語句</param>
static void InsertBST(BSTree bsTree, int key, ref bool isExcute)
{
if (bsTree == null)
return;
//如果父節(jié)點大于key，則遍歷左子樹
if (bsTree.data > key)
InsertBST(bsTree.left, key, ref isExcute);
else
InsertBST(bsTree.right, key, ref isExcute);
if (!isExcute)
{
//構建當前節(jié)點
BSTree current = new BSTree()
{
data = key,
left = null,
right = null
};
//插入到父節(jié)點的當前元素
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)
{
//構建BST中的根節(jié)點
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é)點
///</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);
//輸入節(jié)點數(shù)據(jù)
Console.Write(bsTree.data + "");
//遍歷右子樹
LDR_BST(bsTree.right);
}
}
///<summary>
/// 刪除二叉排序樹中指定key節(jié)點
///</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é)點
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é)點
while (node.left != null)
{
//遍歷它的左子樹
node = node.left;
}
//交換左右孩子
node.left = bsTree.left;
//判斷是真正的葉子節(jié)點還是空左孩子的父節(jié)點
if (node.right == null)
{
//刪除掉右子樹最左節(jié)點
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);
}
}
}
}
運行結果：
值的注意的是：二叉排序樹同樣采用“空間換時間”的做法。
突然發(fā)現(xiàn)，二叉排序樹的中序遍歷同樣可以排序數(shù)組，呵呵，不錯！
PS: 插入操作：O(LogN)。
刪除操作：O(LogN)。
查找操作：O(LogN）。
相關文章
這篇文章主要介紹了Git的三大分區(qū),分別是工作區(qū)、暫存區(qū)和版本庫,并詳細描述了提交、推送、拉取代碼和合并分支的流程,文中通過代碼介紹的非常詳解,需要的朋友可以參考下2025-02-02
本文主要介紹了Git撤銷操作、刪除文件和恢復文件的方法。具有很好的參考價值，下面跟著小編一起來看下吧2017-02-02
這篇文章主要介紹了如何使用clion中配置ROS工程,本文給大家介紹的非常詳細，對大家的學習或工作具有一定的參考借鑒價值，需要的朋友可以參考下2020-08-08
Clion、IEDA、pycharm的一些簡單設置步驟（設置中文菜單、輸出中文、字體大小、背景顏色主題）
這篇文章主要介紹了Clion、IEDA、pycharm的一些簡單設置步驟（設置中文菜單、輸出中文、字體大小、背景顏色主題）,本文通過圖文并茂的形式給大家介紹的非常詳細，具有一定的參考借鑒價值，需要的朋友可以參考下2020-08-08
WEB性能測試工具主要分為三種，一種是測試頁面資源加載速度的，一種是測試頁面加載完畢后頁面呈現(xiàn)、JS操作速度的，還有一種是總體上對頁面進行評價分析，下面分別對這些工具進行介紹，如果誰有更好的工具也請一起分享下。2010-05-05
這篇文章主要為大家介紹了整理超全的visual?studio快捷鍵使用技巧，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進步，早日升職加薪2022-02-02
git通過內網(wǎng)代理訪問外網(wǎng)的相關配置方法
這篇文章主要介紹了git通過內網(wǎng)代理，訪問外網(wǎng)的相關配置,配置git代理以http代理為例，給大家詳細講解，需要的朋友可以參考下2023-05-05
git我每天幾乎都在使用，但是很多命令還是記不住，下面小編給大家分享了Git 常用命令清單，感興趣的朋友一起看看吧2017-10-10
這篇文章主要介紹了Git可視化教程之Git Gui的使用,文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2020-07-07
在使用vscode編輯器的時候,如果我們不設置默認瀏覽器,那么直接打開的是IE瀏覽器,在進行頁面調試的時候無疑是有點麻煩的,這篇文章主要給大家介紹了關于VSCode設置默認瀏覽器打開的兩種方式,需要的朋友可以參考下2023-09-09