对于普通数组,也可以使用范围for,因为底层也用迭代器实现了
特点:
根�����뻧,��������节点的左子树都小于根,根节点的右子树都大于根;
每颗子树也都是二叉搜索树;
对二叉搜索树进行中序遍历得到的就是有序的数据。
二叉搜索树中没有重复的节点值。
二叉搜索树的删除非常恶心,得注意:
大致分为4点,
1、删除的为叶子节点
2、删除的节点左孩子为空
3、删除的节点的右孩子为空
4、删除的节点的左右孩子都不为空
另外1可以和2或者3合并。
二叉搜索树的应用
主要是2各方面的应用
1、key模型:找key在不在
2、key——value模型:主要是中英字典,或者统计次数。
key——value模型中,节点存储了4个值,分别为左孩子地址,右孩子地址,key的值,value的值。
并且注意二叉搜索树中,key的值不可以改变,value的值可以改变。
二叉搜索树的性能分析:
二叉搜索树的性能主要由二叉树的高度决定。
最好情况为O(lonN)
最坏情况为O(N)