二叉搜索树
二叉搜索树/二叉查找树/二叉排序树
特点：
- 树节点增加key属性，用来比较谁大谁小，key不可以重复
- 对于任意一个树节点，它的key比左子树的key都大，同时也比右子树的key都大
/**
* 二叉搜索树
*/
public class BSTree1 {
public TreeNode root;
public static class TreeNode {
int key; //节点的健
Object value; //节点的值
TreeNode left;
TreeNode right;
public TreeNode(int key) {
this.key = key;
}
public TreeNode(int key, Object value) {
this.key = key;
this.value = value;
}
public TreeNode(int key, Object value, TreeNode left, TreeNode right) {
this.key = key;
this.value = value;
this.left = left;
this.right = right;
}
}
}
查找元素 - 递归实现
public class BSTree1 {
...
public Object get(int key) {
return doGet(root, key);
}
private Object doGet(TreeNode node, int key) {
if (node == null) { //没找到结束递归
return null;
}
if (key < node.key) { //向左找
return doGet(node.left, key);
} else if (key > node.key) { //向右找
return doGet(node.right, key);
} else { //找到了
return node.value;
}
}
}
查找元素 - 非递归实现
public class BSTree1 {
...
public Object get(int key){
TreeNode node = root;
while(node != null){
if (key < node.key){ //向左
node = node.left;
}else if (key > node.key){ //向右
node = node.right;
}else{
return node.value;
}
}
return null;
}
}