一、采用存储结构
1、顺序存储：采用数组，顺序存储适配于完全二叉树，对于非完全二叉树并不合适，主要体现在空间上的浪费，所以我们需要用到另一种存储方式——链式存储。
2、链式存储：数据data用键值对的形式表示
二、建立二叉树
//自己建一个Node类,树有Node对象组成
private class Node{
private Key key; //键
private Value val; //值
private Node left,right; //左右子树
private int N; //结点计数器
public Node(Key key,Value val,int N) {
this.key = key;
this.val = val;
this.N = N;
}
}
变量N给出了以该节点为根的子树的结点总数
三、二叉查找树的查、插、删、遍历
package BSTree;
public class BST_1 <Key extends Comparable<Key>,Value>{
private Node root;//二叉查找树的根
private class Node{
private Key key;
private Value value;
private Node lchild,rchild;
private int N; //以该节点为根的子树中的结点个数
//构造方法
public Node(Key key,Value value,int N) {
this.key = key;
this.value =value;
this.N = N;
}
@Override
public String toString() {
return "Node [key=" + key + ", value=" + value + ", N=" + N + "]";
}
}
//获取节点个数N
public int size() {
return size(root);
}
private int size(Node x) {
if(x==null) return 0;
return x.N;
}
//通过Key查找Value
public Value search(Key key) {
return search(root,key);
}
private Value search(Node x,Key key) {
//找不到，返回null
if(x==null) return null;
//如果不为空，用待查找的值与当前根节点的值进行比较
int result = key.compareTo(x.key);//返回一个整数，大于或小于或等于0
if(result>0)
return search(x.rchild, key);//大于，往右子树递归查
else if(result<0)
return search(x.lchild, key);
else
return x.value;
}
//插入
public void insert(Key key,Value value){
root = insert(root,key,value);
}
private Node insert(Node x, Key key, Value value) {
//如果key已经存在，则修改value为新的value值，不存在，则创建一个新的结点
if(x==null) return new Node(key, value, 1);
int result = key.compareTo(x.key);
if(result>0)
x.rchild = insert(x.rchild, key, value);
else if(result<0)
x.lchild = insert(x.lchild, key, value);
else
x.value = value;
x.N = size(x.rchild)+size(x.rchild)+1;
return x;
}
//查找最小键
public Key min() {
return min(root).key;
}
private Node min(Node x) {
if(x.lchild==null) return x;
else return min(x.lchild);
}
//二叉查找树中最难的就是删除，先从删最简单的最小结点开始
public void deleteMin() {
root = deleteMin(root);
}
//返回已经删了最小结点的根节点
private Node deleteMin(Node x) {
//在找到最小结点时x时，x=x.right
if(x.lchild==null) return x.rchild;
x.lchild = deleteMin(x.lchild);
x.N = size(x.rchild)+size(x.rchild)+1;
return x;
}
/**删除任意节点
* 1.如果树为null或者找不到key，返回null
* 2.否则,通过比较找到键Key的结点:
* 如果该结点没有右子树 ,只有左子树 x = x.left
* 如果该结点没有左子树 ,只有有子树x = x.right
* 该结点左右子树都有,先用Node t = x 存x结点，
* 找到以t.right为根节点的树的最小键， 赋予x: x = min(x.right)，及替换x结点
* 然后把这个最小键删了，把t结点的左子树赋予x.left
* 3.返回 返回已经删了结点的根节点
*
*/
public void delete(Key key) {
root = delete(root,key);
}
private Node delete(Node x, Key key) {
if(x==null) return null;
int result = key.compareTo(x.key);
if(result>0) x.rchild = delete(x.rchild, key);
else if(result<0) x.lchild = delete(x.lchild, key);
else {
if(x.rchild==null) return x.lchild;
if(x.lchild==null) return x.rchild;
Node t = x;
x = min(t.rchild);
x.rchild = deleteMin(t.rchild);
x.lchild = t.lchild;
}
x.N = size(x.lchild)+size(x.rchild)+1;
return x;
}
//前序遍历：根--左子树--右子树
public void preOrder() {
preOrder(root);
}
private void preOrder(Node x) {
if(x!=null) {
System.out.print("["+x.key+":"+x.value+"]"+" ");
preOrder(x.lchild);
preOrder(x.rchild);
}
}
//中序遍历:左子树--根节点--右子树
public void inOrder() {
inOrder(root);
}
private void inOrder(Node x) {
if(x!=null) {
inOrder(x.lchild);
System.out.print("["+x.key+":"+x.value+"]"+" ");
inOrder(x.rchild);
}
}
//后序遍历:左子树--右子树--根节点
public void postOrder() {
postOrder(root);
}
private void postOrder(Node x) {
if(x!=null) {
postOrder(x.lchild);
postOrder(x.rchild);
System.out.print("["+x.key+":"+x.value+"]"+" ");
}
}
}