Annihilation 2018-12-11
二叉查找树(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。