二叉查找树
定义:树是n(n>=0)个节点的有限集。二叉树是另一种树型结构,特点是每个节点最多有2个子节点,并且二叉树的子树有左右之分。
看上图,比如添加2节点的时候,发现2比3小,所以放到左侧树中,又发现比1大,所以最终在1的右节点处。
创建一个二叉查找树的类:
/// <summary> /// 二叉查找树类 /// IComparable:使用此进行限制是为了实现 两个实体类之间按>,=,<进行比较 /// </summary> /// <typeparam name="E"></typeparam> class BST<E> where E : IComparable<E> { /// <summary> /// 节点类 /// </summary> private class Node { public E e; public Node left; public Node right; public Node(E e) { this.e = e; left = null; right = null; } } private Node root; private int N; public BST() { root = null; N = 0; } public int Count { get { return N; } } public bool IsEmpty { get { return N == 0; } } }
看下图,需要添加一个节点的时候,