二叉排序树介绍
二叉排序树，又称为二叉查找树。它或者是一棵空树，或者是具有下列性质的二叉树。
若它的左子树不为空，则左子树上所有的结点的值均小于根结构的值；
若它的右子树不为空，则右字数上所有结点的值均大于它的根结点的值；
它的左右子树也分别为二叉排序树。
1，排序方便
2，方便查找
3，方便插入和删除
二叉排序树最终实现：所有的左子树的值都小于父节点的值，所有的右子树的值都大于父节点的值
二叉排序树实现
二叉数：
遍历：
【删除】分为四种情况：
1. 删除的结点，左右孩子都为空
2. 删除的结点,左孩子不为空，右孩子为空
3. 删除的结点,左孩子为空，右孩子不为空
4. 删除的结点,左右孩子都不为空
更新：先删除再更新，要保持二叉排序树始终是排好序的！
代码实现：
using System;
using System.Text;namespace cchoop
{class Program{public static void Main(){BinSortTree tree = new BinSortTree();int[] arr = { 62, 58, 88, 47, 73, 99, 35, 51, 93, 37 };for (int i = 0; i < arr.Length; i++){tree.Add(arr[i]);}Console.Write("中序遍历：");tree.MidTraversal();Console.Write("\n前序遍历：");tree.PreTraversal();Console.Write("\n后序遍历：");tree.AfterTraversal();Console.WriteLine("\n");//查找Console.WriteLine("查找50：" + tree.Find(50));Console.WriteLine("查找58：" + tree.Find(58));Console.WriteLine();//更新Console.WriteLine("更新108 To 8888：" + tree.Update(108, 8888));Console.WriteLine("更新58 To 8888：" + tree.Update(58, 8888));Console.Write("中序遍历：");tree.MidTraversal();Console.WriteLine("\n");//删除Console.WriteLine("删除58：" + tree.Delete(58));Console.WriteLine("删除88：" + tree.Delete(88));Console.Write("中序遍历：");tree.MidTraversal();Console.WriteLine("\n");}}/// <summary>/// 二叉排序树-链式存储/// </summary>class BinSortTree{private BinSortNode root;//添加public void Add(int item){BinSortNode node = new BinSortNode(item);//根结点为空if (root == null){root = node;return;}//根节点不为空BinSortNode tempNode = root;while (true){if (node.Data < tempNode.Data) //放在左边{if (tempNode.LeftChild == null){node.Parent = tempNode;tempNode.LeftChild = node;break;}else{tempNode = tempNode.LeftChild;}}else //放在右边{if (tempNode.RightChild == null){node.Parent = tempNode;tempNode.RightChild = node;break;}else{tempNode = tempNode.RightChild;}}}}//删除public bool Delete(int item){bool flag = false;if (root == null){return false;}BinSortNode tempNode = root;while (true){if (tempNode == null){break;}if (tempNode.Data == item){Delete(tempNode);flag = true;break;}else if (tempNode.Data > item){tempNode = tempNode.LeftChild;}else{tempNode = tempNode.RightChild;}}return flag;}private void Delete(BinSortNode node){//四种情况：1.删除的结点，左右孩子都为空//2.删除的结点,左孩子不为空，右孩子为空//3.删除的结点,左孩子为空，右孩子不为空//4.删除的结点,左右孩子都不为空if (node.LeftChild == null && node.RightChild == null){if (node == root) //头结点{root = null;}else{if (node.Parent.LeftChild == node){node.Parent.LeftChild = null;}else if (node.Parent.RightChild == node){node.Parent.RightChild = null;}}return;}if (node.LeftChild != null && node.RightChild == null){if (node == root) //头结点{root = node.LeftChild;}else{if (node.Parent.LeftChild == node){node.Parent.LeftChild = node.LeftChild;}else if (node.Parent.RightChild == node){node.Parent.RightChild = node.LeftChild;}node.LeftChild.Parent = node.Parent;}return;}if (node.LeftChild == null && node.RightChild != null){if (node == root) //头结点{root = node.RightChild;}else{if (node.Parent.LeftChild == node){node.Parent.LeftChild = node.RightChild;}else if (node.Parent.RightChild == node){node.Parent.RightChild = node.RightChild;}node.RightChild.Parent = node.Parent;}return;}//递归删除if (node.LeftChild != null && node.RightChild != null){BinSortNode tempNode = node.RightChild;while (tempNode.LeftChild != null){tempNode = tempNode.LeftChild;}node.Data = tempNode.Data;this.Delete(tempNode);}}//更新结点public bool Update(int oldValue, int newValue){bool flag = false;if (root == null){return false;}BinSortNode tempNode = root;while (true){if (tempNode == null){break;}if (tempNode.Data == oldValue){//如果这样更新将会破坏“排序”这个特点，所以更新，应该先删除再添加，这棵树仍然是二叉排序树//tempNode.Data = newValue; Delete(tempNode);this.Add(newValue);flag = true;break;}else if (tempNode.Data > oldValue){tempNode = tempNode.LeftChild;}else{tempNode = tempNode.RightChild;}}return flag;}//查找public bool Find(int item){return Find(item, root);}private bool Find(int item, BinSortNode node){if (node == null){return false;}if (item == node.Data){return true;}else if (item > node.Data){return Find(item, node.RightChild);}else{return Find(item, node.LeftChild);}}//前序遍历public void PreTraversal(){PreTraversal(root);}private void PreTraversal(BinSortNode node){if (node == null){return;}Console.Write(node.Data + " ");PreTraversal(node.LeftChild);PreTraversal(node.RightChild);}//中序遍历public void MidTraversal(){MidTraversal(root);}private void MidTraversal(BinSortNode node){if (node == null){return;}MidTraversal(node.LeftChild);Console.Write(node.Data + " ");MidTraversal(node.RightChild);}//后序遍历public void AfterTraversal(){AfterTraversal(root);}private void AfterTraversal(BinSortNode node){if (node == null){return;}AfterTraversal(node.LeftChild);AfterTraversal(node.RightChild);Console.Write(node.Data + " ");}}class BinSortNode{public BinSortNode Parent { get; set; } //父节点public BinSortNode LeftChild { get; set; } //左孩子public BinSortNode RightChild { get; set; } //右孩子public int Data { get; set; }public BinSortNode(int data){this.Data = data;}}
}打印结果：
