# Implementation of binary sort (search) tree

Binary tree sort tree is also called binary search number. It is either an empty number or a binary tree with the following properties:

① If the left subtree is not empty, the values of all nodes on the left subtree are smaller than the values of its root nodes;

② If the right subtree is not empty, the values of all nodes on the right subtree are greater than the values of their root nodes;

③ The left and right subtrees are also binary sorting trees

Implementation method:

```package com.tongtong.tree;

import java.util.Queue;

/**
* Implementation of binary sort (search) tree
*/
public class BinaryTree {

private Node root;
public BinaryTree(){
root = null;
}
//Insert data into the sort binary tree
public void insert(int data){
Node newNode = new Node(data);
if(root == null){
root = newNode;
}else{
Node current = root;
Node parent; //Each master node
while(true){ //Find where to insert
parent = current;
if(data < current.data){
current = current.left;
if(current == null){
parent.left = newNode;
return;
}
}else{
current = current.right;
if(current == null){
parent.right = newNode;
return;
}
}
}
}
}

//Building a binary tree with numerical input
public void buildTree(int[] data){
for(int i=0;i<data.length;i++){
insert(data[i]);
}
}

//Recursive implementation of middle order traversal method -- > left root right
public void inOrder(Node localRoot){
if(localRoot != null){
inOrder(localRoot.left);
System.out.print(localRoot.data + " ");
inOrder(localRoot.right);
}
}

public void inOrder(){
inOrder(this.root);
}

//Recursive implementation of preorder traversal method
public void preOrder(Node localRoot){
if(localRoot != null){
System.out.print(localRoot.data + " ");
preOrder(localRoot.left);
preOrder(localRoot.right);
}
}

public void preOrder(){
preOrder(this.root);
}

//Recursive implementation of postorder traversal method -- > left and right roots
public void postOrder(Node localRoot){
if(localRoot != null){
postOrder(localRoot.left);
postOrder(localRoot.right);
System.out.print(localRoot.data + " ");
}
}

public void postOrder(){
postOrder(this.root);
}

//level traversal
public void layerTranverse(){
if(this.root == null){
return;
}

while(!q.isEmpty()){
Node n = q.poll();
System.out.print(n.data);
System.out.print(" ");
}
}

public static void main(String[] args) {
BinaryTree biTree = new BinaryTree();
int[] data = {2,8,7,4,9,3,1,6,7,5};
biTree.buildTree(data);

System.out.println("Middle order traversal of binary trees========");
biTree.inOrder();
System.out.println();
System.out.println("Preorder traversal of binary trees========");
biTree.preOrder();
System.out.println();
System.out.println("Binary Tree Postorder Traversal ========");
biTree.postOrder();
System.out.println();
System.out.println("level traversal============");
biTree.layerTranverse();
}
}
```

Keywords: Java

Added by scottchr226 on Thu, 19 Dec 2019 18:42:30 +0200