en造数据结构与算法C# 二叉排序树 泛型类的基本构成

前置知识：二叉树 

en造数据结构与算法C# 二叉树的顺序存储和前中后序遍历-CSDN博客 

二叉排序树基本规则

二叉排序树的特点就是有序，其基本规则分为两个点

1.按照顺序去存储节点(下图绿色的顺序)

2.其次，在第一点的基础上，比当前节点小的值放在左子节点，比当前节点大的值放在右子节点

也就是下图这样子

代码实现分析

首先是不是应该有一个节点类，作为链式存储的必要条件

在节点类之中可以有三个基本字段

本体值 =>数字 Eg：50，86，36......

左子节点和右子节点：

这里我采用泛型的方式，这样做的好处是可以方便多类型存储

缺点是后续要比较本体值的时候，需要继承一个接口才能比较其大小

(泛型类型不能直接进行比较，需要用一些方法，比如Equels或者这里的Icomparable接口的方法)

where T : IComparable<T> 

namespace System {public interface IComparable<in T> {int CompareTo(T other);}
}

你可以将T改为int类型

// 节点类
public class Node<T> where T : IComparable<T> {// 包括了左右子节点和一个数据本体，和一个构造方法public T data;public Node<T> LeftNode;public Node<T> RightNode;public Node(T data) {this.data = data;LeftNode = null;RightNode = null;}
}

为什么不能用顺序存储呢？

因为需要存入的时候就要进行一个排序，顺序存储就一股脑存进去了，虽然可以后续通过中序遍历的方式进行重新排序，但是，这样做后续的增删查改会很不方便，且这样做增大了空间复杂度

然后就是二叉排序树的本体类

其基本的字段只需要有一个即可，就是定义一个根节点

public class BinarySortTree<T> where T : IComparable<T> {public Node<T> root; // 定义根节点}

这就是基本组成，增删查改我们后续细细分析