二叉排序树的链式存储结构
在C#当中，链式存储结构主要靠引用，所以通过创建一个新的类作为结点类，通过对结点类的链式引用，以此来实现我们需要的链式存储结构。
节点类 BSNode：
class BSNode
{
public BSNode RightNode { get; set; }
public BSNode LeftNode { get; set; }
public BSNode Parent { get; set; }
public int Data { get; set; }
public BSNode(){}
public BSNode(int temp)
{
this.Data = temp;
}
}
节点类中存储对应的左右结点、父结点、数据以及相应的构造方法。
在其他类当中使用到该结点类的时候，通过建立两个结点的父子关系，就能实现链式存储，例如：
BSNode Node1 = new BSNode(10);
BSNode Node2 = new BSNode(11);
//建立两个结点的父子关系
Node1.LeftNode = Node2;//将Node2作为Node1的左结点
Node2.Parent = Node1;//将Node1的父结点设为Node2
二叉排序树的增加操作
增加操作则需要注意一下两点：
- 当前的树为空，
- 添加进去的数据结点是作为父结点的左子树还是右子数。
第一种情况则可以通过判断根节点是否为空来验证改树是否为空，为空则将根节点设为当前数据结点，否则进行第二种情况判断。代码示例如下：
if(root == null)
{
root = Node;
}
else
{
......
}
根据二叉排序树的特点，小的数据在左边，大的数据在右边，在第二种情况下则需要通过判断该数据结点与当前结点所存储的数据的大小来进行判断。
- 当该数据结点比当前结点所存储的数据大的时候，判断右子树是否存在，如果存在便将当前结点的引用则指向右子树，否则将该数据结点设为当前节点的右子树，确定结点之间的父子关系。
- 当该数据结点比当前结点所存储的数据小的时候，判断左子树是否存在，如果存在便将当前结点的引用则指向左子树，否则将该数据结点设为当前节点的左子树，确定结点之间的父子关系。
在上述两种情况中，便实现了二叉排序树的增加操作，完整代码如下：
BSNode root = null;
public void Add(int temp)
{
BSNode Node = new BSNode(temp);//创建一个节点
if(root == null)
{
root = Node;
}
else
{
//为了能够遍历二叉树，同时保留根节点的引用，我们需要创建一个新的结点来遍历整个二叉树
BSNode tempNode = root;
while (true)
{
if (tempNode.Data >= temp)
{
if (tempNode.RightNode == null)
{
tempNode.RightNode = Node;
Node.Parent = tempNode;
break;
}
else
{
tempNode = tempNode.RightNode;
}
}
else
{
if(tempNode.LeftNode == null)
{
tempNode.LeftNode = Node;
Node.Parent = tempNode;
break;
}
else
{
tempNode = tempNode.LeftNode;
}
}
}
}
}
二叉排序树的查找操作
查找操作是比较简单的，整体思路便是判断需要查找的数据是否与当前结点的数据相等，相等就返回true，否则进行一次判断，比较当前结点的数与需要查找数据的大小。
- 需要查找的数据比当前结点大的时候，遍历右子树，
- 需要查找的数据比当前结点小的时候，遍历左子树。
private bool Find(int data,BSNode Node)
{
//递归结束条件
if(Node == null)
{
return false;
}
if(Node.Data == data)
{
return true;
}
else
{
if(Node.Data >= data)
{
//递归遍历
return Find(data, Node.RightNode);
}
else
{
return Find(data, Node.LeftNode);
}
}
}
二叉排序树的删除操作
删除一个结点就需要找到当前结点，我们可以通过使用上述的查找操作的方法来找到我们需要删除的结点，删除结点有三种情况：
- 需要删除的结点没有左右子树
- 需要删除的结点为根节点
- 需要删除的结点为左子树结点
- 需要删除的结点为右子树结点
- 需要删除的结点只有有左子树或者右子树
- 需要删除的结点同时拥有左右子树
面对情况一的解决方案：
if(Node.LeftNode == null && Node.RightNode == null)
{
//为根节点的情况
if(Node.Parent == null)
{
root = null;
}
else if (Node.Parent.LeftNode == Node)
{
Node.Parent.LeftNode = null;
}
else if(Node.Parent.RightNode == Node)
{
Node.Parent.RightNode = null;
}
return;
}
面对情况二的解决方案：
通过修改对于结点的引用，将父结点的引用直接引用到被删除的结点的子结点
if (Node.LeftNode != null && Node.RightNode == null)
{
if(Node.Parent.LeftNode == Node)//判断是被删除的结点位于父节点的位置。
{
Node.Parent.LeftNode = Node.LeftNode;
Node.LeftNode = null;
}
else
{
Node.Parent.RightNode = Node.LeftNode;
Node.LeftNode = null;
}
return;
}else if(Node.RightNode != null && Node.LeftNode == null)
{
if (Node.Parent.LeftNode == Node)
{
Node.Parent.LeftNode = Node.RightNode;
Node.RightNode = null;
}
else
{
Node.Parent.RightNode = Node.RightNode;
Node.RightNode = null;
}
return;
}
面对情况三的解决方案：
通过寻找左子树的最大值或者右子树的最小值，将该结点的内容替换到被删除的结点上，下列代码是通过查找右子树最小值的方式来替换被删除的结点进行的删除操作，找到右子树的最小值后，将最小值替换到需要被删除的结点的数据，最后删除右子树最小值的结点，此时右子树结点的情况只会存在情况一或者情况二中只有左子树的情况，通过递归方式就能达成删除操作。
BSNode bsNode = Node.LeftNode;
while (true)
{
if(bsNode.RightNode != null)
{
bsNode = bsNode.RightNode;
}
else
{
break;
}
}
Node.Data = bsNode.Data;
Delete(bsNode);
整体代码展示
BSNode类：
class BSNode
{
public BSNode RightNode { get; set; }
public BSNode LeftNode { get; set; }
public BSNode Parent { get; set; }
public int Data { get; set; }
public BSNode(){}
public BSNode(int temp)
{
this.Data = temp;
}
}
BSTree类：
class BSTree
{
BSNode root = null;
public void Add(int temp)
{
BSNode Node = new BSNode(temp);//创建一个节点
if(root == null)
{
root = Node;
}
else
{
BSNode tempNode = root;
while (true)
{
if (tempNode.Data >= temp)
{
if (tempNode.RightNode == null)
{
tempNode.RightNode = Node;
Node.Parent = tempNode;
break;
}
else
{
tempNode = tempNode.RightNode;
}
}
else
{
if(tempNode.LeftNode == null)
{
tempNode.LeftNode = Node;
Node.Parent = tempNode;
break;
}
else
{
tempNode = tempNode.LeftNode;
}
}
}
}
}
public bool Find(int data)
{
return Find(data, root);
}
private bool Find(int data,BSNode Node)
{
if(Node == null)
{
return false;
}
if(Node.Data == data)
{
return true;
}
else
{
if(Node.Data >= data)
{
return Find(data, Node.RightNode);
}
else
{
return Find(data, Node.LeftNode);
}
}
}
public void InorderTraveral()
{
InorderTraveral(root);
}
private void InorderTraveral(BSNode Node)
{
if(Node == null)
{
return;
}
InorderTraveral(Node.RightNode);
Console.Write(Node.Data + " ");
InorderTraveral(Node.LeftNode);
}
public bool Delete(int data)
{
BSNode Node = root;
while (true)
{
if (Node == null)
{
return false;
}
if (Node.Data == data)
{
Delete(Node);
return true;
}
if(Node.Data >= data)
{
Node = Node.RightNode;
}
else
{
Node = Node.LeftNode;
}
}
}
private void Delete(BSNode Node)
{
//删除叶子节点的情况
if(Node.LeftNode == null && Node.RightNode == null)
{
//为根节点的情况
if(Node.Parent == null)
{
root = null;
}
else if (Node.Parent.LeftNode == Node)
{
Node.Parent.LeftNode = null;
}
else if(Node.Parent.RightNode == Node)
{
Node.Parent.RightNode = null;
}
return;
}
if (Node.LeftNode != null && Node.RightNode == null)
{
if(Node.Parent.LeftNode == Node)
{
Node.Parent.LeftNode = Node.LeftNode;
Node.LeftNode = null;
}
else
{
Node.Parent.RightNode = Node.LeftNode;
Node.LeftNode = null;
}
return;
}else if(Node.RightNode != null && Node.LeftNode == null)
{
if (Node.Parent.LeftNode == Node)
{
Node.Parent.LeftNode = Node.RightNode;
Node.RightNode = null;
}
else
{
Node.Parent.RightNode = Node.RightNode;
Node.RightNode = null;
}
return;
}
BSNode bsNode = Node.LeftNode;
while (true)
{
if(bsNode.RightNode != null)
{
bsNode = bsNode.RightNode;
}
else
{
break;
}
}
Node.Data = bsNode.Data;
Delete(bsNode);
}
}
Program类：
class Program
{
static void Main(string[] args)
{
BSTree Tree = new BSTree();
//int[] data = { 62, 58, 88, 47, 73, 99, 35, 51, 93, 37 };
int[] data = { 62, 58, 47, 35, 51, 37 };
foreach (var s in data)
{
Tree.Add(s);
}
Tree.InorderTraveral();
Console.WriteLine();
//Console.WriteLine(Tree.Find(35));
//Console.WriteLine(Tree.Find(34));
Tree.Delete(58);
Tree.InorderTraveral();
Console.WriteLine();
}
}