package BinaryTree;
public class BinarySearchTree {
public TreeNode root;
public BinarySearchTree(){
//root=new TreeNode(1,"A");
//root=null;
}
private class TreeNode{
private int key;
private String data;
private TreeNode leftChild;
private TreeNode rightChild;
public TreeNode(int key,String data){
this.key=key;
this.data=data;
this.leftChild=null;
this.rightChild=null;
}
}
public TreeNode getTreeNode(int key,String data){
return new TreeNode(key,data);
}
private void insert(TreeNode node){
root=insert(root,node);
}
public TreeNode insert(TreeNode subTree,TreeNode node){
if(node==null){ //不可插入null
return null;
}
if(subTree==null){ //根节点为空，插入
subTree=node;
}else{
if(node.key<subTree.key){//比根节点小？ 插左边
subTree.leftChild=insert(subTree.leftChild,node);
}else{ //否则，插右边
subTree.rightChild=insert(subTree.rightChild,node);
}
}
return subTree;
}
/**
* 前序遍历
* 先访问根节点，再分别访问其左、右子树
* @param subTree
*/
public void preOrder(){
preOrder(root);
}
private void preOrder(TreeNode subTree){
if(subTree!=null){
System.out.println("key:"+subTree.key+"--name:"+subTree.data);
preOrder(subTree.leftChild);
preOrder(subTree.rightChild);
}
}
/**
* 中序遍历
* 根节点的遍历在其左、右子树之间
* @param subTree
*/
public void inOrder(){
inOrder(root);
}
public void inOrder(TreeNode subTree){
if(subTree!=null){
inOrder(subTree.leftChild);
System.out.println("key:"+subTree.key+"--name:"+subTree.data);
inOrder(subTree.rightChild);
}
}
/**
* 后序遍历
* 访问根节点在遍历其左右子树之后
* @param subTree
*/
public void postOrder(){
postOrder(root);
}
public void postOrder(TreeNode subTree){
if(subTree!=null){
postOrder(subTree.leftChild);
postOrder(subTree.rightChild);
System.out.println("key:"+subTree.key+"--name:"+subTree.data);
}
}
public static void main(String[] args) {
BinarySearchTree bst=new BinarySearchTree();
bst.insert(bst.getTreeNode(4, "D"));
bst.insert(bst.getTreeNode(1, "A"));
bst.insert(bst.getTreeNode(2, "B"));
bst.insert(bst.getTreeNode(5, "E"));
bst.insert(bst.getTreeNode(3, "C"));
sop("前序遍历");
bst.preOrder();
sop("中序遍历：结果为从小到大");
bst.inOrder();
sop("后序遍历");
bst.postOrder();
}
public static void sop(Object o){
System.out.println(o);
}
}
转载请注明原文地址: https://ju.6miu.com/read-32637.html
