首先：20跟50比，發(fā)現(xiàn)20是老小，不得已，得要?dú)w結(jié)到50的左子樹中去比較。
就拿上面一幅圖來說，比如我想找到節(jié)點(diǎn)10.
《1》 刪除的是“葉節(jié)點(diǎn)20“，這種情況還是比較簡(jiǎn)單的，刪除20不會(huì)破壞樹的結(jié)構(gòu)。如圖：
《2》刪除”單孩子節(jié)點(diǎn)90“，這個(gè)情況相比第一種要麻煩一點(diǎn)點(diǎn)，需要把他的孩子頂上去。
《3》刪除“左右孩子都有的節(jié)點(diǎn)50”，這個(gè)讓我在代碼編寫上糾結(jié)了好長(zhǎng)時(shí)間，問題很直白，
坦白吧，不知道大家可否知道“二叉樹”的中序遍歷，不過這個(gè)我會(huì)在后面講的，現(xiàn)在可以當(dāng)
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Diagnostics;
namespace TreeSearch
{
class Program
{
static void Main(string[] args)
{
Listint> list = new Listint>() { 50, 30, 70, 10, 40, 90, 80 };
//創(chuàng)建二叉遍歷樹
BSTree bsTree = CreateBST(list);
Console.Write("中序遍歷的原始數(shù)據(jù)：");
//中序遍歷
LDR_BST(bsTree);
Console.WriteLine("\n---------------------------------------------------------------------------n");
//查找一個(gè)節(jié)點(diǎn)
Console.WriteLine("\n10在二叉樹中是否包含：" + SearchBST(bsTree, 10));
Console.WriteLine("\n---------------------------------------------------------------------------n");
bool isExcute = false;
//插入一個(gè)節(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中序遍歷后：");
//刪除一個(gè)節(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>
/// 定義一個(gè)二叉排序樹結(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(Listint> 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);
}
}
}
}
