二叉查找树（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
原标题：[javaSE] 数据结构（二叉查找树
关键词：JAVA
我知道了 