二叉查找树(Binary Search Tree),又被称为二叉搜索树,它是特殊的二叉树,左子树的节点值小于右子树的节点值。
定义二叉查找树
定义二叉树BSTree,它保护了二叉树的根节点BSTNode类型的mRoot,定义内部类BSTNode
包含二叉树的几个基本信息:
key——关键字用来对二叉查找树的节点进行排序
left——指向当前节点的左孩子
right——指向当前节点的右孩子
parent——指向当前节点的父节点
定义插入节点方法insert(T key),参数:T key要插入的对象
创建节点对象,实例化BSTNode对象,构造参数:T对象
定义重载方法insert(BSTree bsTree,BSTNode bstNode)方法,参数:BSTree树对象,BSTNode节点对象
插入节点,分两步,
1.找到节点的父节点位置
2.插入节点到父节点的左位置或者右位置
public class BSTree<T extends Comparable<T>> {
private BSTNode<T> mRoot;
/**
* 定义二叉树
*
* @author taoshihan
* @param <T>
*
*/
public class BSTNode<T extends Comparable<T>> {
public T key;
public BSTNode parent, left, right;
public BSTNode(T key, BSTNode parent, BSTNode left, BSTNode right) {
this.key = key;
this.parent = parent;
this.left = left;
this.right = right;
}
}
public void insert(BSTree bsTree, BSTNode bstNode) {
BSTNode parent = null;
BSTNode x = bsTree.mRoot;
// 查找bstNode的插入位置,x的指针指对
while (x != null) {
parent = x;// 把x的位置作为节点的父类
int flag = bstNode.key.compareTo(x.key);
if (flag < 0) {
x = x.left;
}else{
x=x.right;
}
}
// 插入
bstNode.parent = parent;
if(parent==null){
bsTree.mRoot=bstNode;
}else{
int flag = bstNode.key.compareTo(parent.key);
if (flag < 0) {
parent.left = bstNode;
} else {
parent.right = bstNode;
}
}
}
/**
* 插入根节点
*
* @param key
*/
public void insert(T key) {
BSTNode<T> z = new BSTNode<T>(key, null, null, null);
// 如果新建结点失败,则返回。
if (z != null)
insert(this, z);
}
/*
* 打印"二叉查找树"
*
* key -- 节点的键值
* direction -- 0,表示该节点是根节点;
* -1,表示该节点是它的父结点的左孩子;
* 1,表示该节点是它的父结点的右孩子。
*/
private void print(BSTNode<T> tree, T key, int direction) {
if(tree != null) {
if(direction==0) // tree是根节点
System.out.printf("%2d is root\n", tree.key);
else // tree是分支节点
System.out.printf("%2d is %2d's %6s child\n", tree.key, key, direction==1?"right" : "left");
print(tree.left, tree.key, -1);
print(tree.right,tree.key, 1);
}
}
public void print(BSTree<T> tree) {
if (tree.mRoot != null){
print(tree.mRoot, tree.mRoot.key, 0);
}
}
/**
* @param args
*/
public static void main(String[] args) {
BSTree tree = new BSTree();
tree.insert(3);
tree.insert(1);
tree.insert(2);
tree.insert(5);
tree.insert(4);
tree.insert(6);
tree.print(tree);
}
}
输出:
3 is root 1 is 3's left child 2 is 1's right child 5 is 3's right child 4 is 5's left child 6 is 5's right child