数据结构二叉查找树 [复制链接]

二叉查找树：即BST，也叫二叉搜索树，二叉排序树，在二叉树的基础上，它拥有如下性质，每个节点的值都大于其左子树中的任意节点的值，而小于右子树的任意节点

图例

数据结构

　　节点数据结构如下

privateclassNode{privateValuevalue;//该节点的值privateNodeleft,right;//该节点的左右子树publicNode(Valuevalue){this.value=value;}}

查找过程

　　递归可以使查找过程清晰易懂

//在树中查找节点publicNodeget(Valuevalue){returnget(root,value);//从根节点开始查找}privateNodeget(Nodex,Valuevalue){if(x==null){returnnull;}intcmp=value.
　　比如要在上图查找结点值为4的节点，从根节点开始→4小于8，则查找左子树→4大于3，则查找右子树→4小于6，则查找左子树→查找成功

插入过程

　　插入过程和查找过程极其相似，只是在最后多了一步添加结点的操作

//插入节点publicvoidput(Valuevalue){//查找节点位置root=put(root,value);}privateNodeput(Nodex,Valuevalue){if(x==null){returnnewNode(value);}intcmp=value.
　　二叉查找树的优势：这里借用算法4书上的一张表

　　对比二分查找，在查找性能下降些许的情况下，却可以将插入复杂度下降一个等级的复杂度，是非常不错的。

注意：

　　1.同一集合，由于插入的顺序不同，可能有多种不同的树结构

　　2.在最好的情况下，二叉查找树的N个节点是平衡的（即叶子节点的深度差不超过1），最差时，二叉查找树退化为链表

延伸：

　这里的实现只是简单实现了树的构造和查找，有以下可以深入了解的点：

　　1.将节点元素值换为键值对，以方便存储符号表

　　2.二叉查找树的最大、最小、删除、范围查找等

最后给出一个完整代码

publicclassBSTValueextendsComparableValue{privateNoderoot;privateclassNode{privateValuevalue;//该节点的值privateNodeleft,right;//该节点的左右子树publicNode(Valuevalue){this.value=value;}}//在树中查找节点publicNodeget(Valuevalue){returnget(root,value);//从根节点开始查找}privateNodeget(Nodex,Valuevalue){if(x==null){returnnull;}intcmp=value.