二叉查找树（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.插入节点到父节点的左位置或者右位置
@H_301_91@public class BSTree<T extends Comparable<T>> {
private BSTNode<T> mRoot;
/**
* 定义二叉树
*
* @author taoshihan
* @param <T>
*
*/
class BSTNode<T {
public T key;
BSTNode parent,left,right;
BSTNode(T key,BSTNode parent,BSTNode left,BSTNode right) {
this.key = key;
this.parent = parent;
this.left = left;
this.right = right;
}
}
void insert(BSTree bsTree,BSTNode bstNode) {
BSTNode parent = null;
BSTNode x = bsTree.mRoot;
// 查找bstNode的插入位置，x的指针指对
while (x != ) {
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==){
bsTree.mRoot=bstNode;
}{
bstNode.key.compareTo(parent.key);
) {
parent.left = bstNode;
} {
parent.right = bstNode;
}
}
}
* 插入根节点
*
* key
insert(T key) {
BSTNode<T> z = new BSTNode<T>(key,null,1)">);
如果新建结点失败，则返回。
if (z != )
insert(this,z);
}
/*
* 打印"二叉查找树"
*
* key -- 节点的键值
* direction -- 0，表示该节点是根节点;
* -1，表示该节点是它的父结点的左孩子;
* 1，表示该节点是它的父结点的右孩子。
private void print(BSTNode<T> tree,T key,1)">int direction) {
if(tree != ) {
if(direction==0) tree是根节点
System.out.printf("%2d is root\n"else tree是分支节点
System.out.printf("%2d is %2d's %6s child\n",tree.key,key,direction==1?"right" : "left");
print(tree.left,-1);
print(tree.right,1);
}
}
void print(BSTree<T> tree) {
if (tree.mRoot != ){
print(tree.mRoot,tree.mRoot.key,0);
}
}
* args
static 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