二叉查找树（Binary Search Tree），（又：二叉搜索树，二叉排序树）它或者是一棵空树，或者是具有下列性质的二叉树： 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值； 它的左、右子树也分别为二叉排序树。以下是楼主用java写的一个二叉搜索树类的，包含创建，添加新元素，以及常用的四种遍历方式。
//首先定义一个BNode节点，里面包含left、right初始化为null，以及int型数组data。class BNode{ BNode left=null; BNode right=null; int data; public BNode(int data){ this.data=data; }}public class BinaryTree{ BNode root=null;//插入新的元素 public void insert(int data) { BNode newBNode=new BNode(data); if(root==null) { root=newBNode; }else {
//定义一个Node型父亲节点parsent BNode parent=root;
//循环至找到节点存放的合适位置
//如果节点数值小于当前位置所指向值，判断当前节点左孩子是否存在？若当前节点左孩子不存在，将新的节点插入到前节点左方并返回结束循环，若当前节点左孩子存在，则parsent指向自身的左孩子 while(true) { if(data<parent.data) { if(parent.left==null) { parent.left=newBNode; return; }else { parent=parent.left; } }
//如果节点数值大于当前位置所指向值，判断当前节点右孩子是否存在？若当前节点右孩子不存在，将新的节点插入到前节点右方并返回结束循环，若当前节点右孩子存在，则parsent指向自身的右孩子
else if(data>parent.data) { if(parent.right==null) { parent.right=newBNode; return; }else { parent=parent.right; } } } } }
//递归思想遍历二叉树，很容易理解这里就不啰嗦了
//中序遍历（左-根-右） public void inOrder(BNode root) { if(root!=null) { inOrder(root.left); System.out.print(root.data+" "); inOrder(root.right); } } public void inOrder() { this.inOrder(this.root); } //先序遍历（根-左-右） public void preOrder(BNode root) { if(root!=null) { System.out.print(root.data+" "); preOrder(root.left); preOrder(root.right); } } public void preOrder() { this.preOrder(this.root); } //后续遍历（左-右-根） public void posOrder(BNode root) { if(root!=null) { posOrder(root.left); posOrder(root.right); System.out.print(root.data+" "); } } public void posOrder() { this.posOrder(this.root); }
//层次遍历可以利用队列的性质完成，其主要思路如下：先将根节点放入队列中，然后每次都从队列中取出一个节点打印该节点的值，若这个节点有子节点，则将它的子节点放入队列尾，直到队列为空。 public void layerOrder() { if(this.root==null) { return; } Queue<BNode> queue=new LinkedList<>(); queue.add(this.root); while(!queue.isEmpty()) { BNode p=queue.poll(); System.out.print(p.data+" "); if(p.left!=null) { queue.add(p.left); } if(p.right!=null) { queue.add(p.right); } } } public static void main(String[] args) { BinaryTree test=new BinaryTree(); test.insert(3); test.insert(2); test.insert(1); test.insert(4); test.insert(5); //test.inOrder(); //test.preOrder(); test.posOrder(); }}总结：上诉测试结构test.inOrder()打印输出1 2 3 4 5，test.preOrder()打印输出3 2 1 4 5， test.posOrder()打印输出1 2 5 4 3，test.layerOrder()打印输出3 2 1 4 5。
转载于:https://www.cnblogs.com/a5137/p/9735966.html
