Binary sorting tree is also called binary search tree. It is either an empty tree or a binary tree with the following properties:
① If the left subtree is not empty, then the values of all nodes on the left subtree are smaller than the values of its root node;
②If the right subtree is not empty, then the values of all nodes on the right subtree are greater than the values of its root node;
③The left and right subtrees are also binary sorting trees respectively.
The following code implements:
import java.util.LinkedList;import java.util.Queue;class Node{ public int data; public Node left; public Node right; public int leftMaxDistance; public int rightMaxDistance; public Node(int data){ this.data=data; this.left=null; this.right=null; }}/** * @author TY * Implementing a binary sorting tree, including insertion, in-order traversal, preorder traversal, post-order traversal, and calculating the maximum distance of all nodes*/public class BinaryTree { private Node root; public BinaryTree(){ root=null; } public void insert(int data){ Node newNode=new Node(data); if(root==null) root=newNode; else{ Node current=root; Node parent; while (true) {//Find insert position 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; } } } } } } } //Input numerical values to build a binary tree public void buildTree(int[] data){ for (int i = 0; i < data.length; i++) { insert(data[i]); } } } //In-order traversal method recursively implements public void inOrder(Node localRoot){ if(localRoot!=null){ inOrder(localRoot.left); System.out.print(localRoot.data+" "); inOrder(localRoot.right); } } public void inOrder(){ this.inOrder(this.root); } //The preorder traversal method recursively implements public void preOrder(Node localRoot){ if(localRoot!=null){ System.out.print(localRoot.data+" "); preOrder(localRoot.left); preOrder(localRoot.right); } } public void preOrder(){ this.preOrder(this.root); } //The postorder traversal method recursively implements public void postOrder(Node localRoot){ if(localRoot!=null){ postOrder(localRoot.left); postOrder(localRoot.right); System.out.print(localRoot.data+" "); } } public void postOrder(){ this.postOrder(this.root); } /** * Layer-sequence traversal binary tree: Now put the root node into the queue, and then take a node from the queue every time to print the value of the node. * If this node has a child node, put its child node into the tail of the queue until the queue is empty*/ public void layerTranverse(){ if(this.root==null) return; Queue<Node> q=new LinkedList<Node>(); q.add(this.root); while(!q.isEmpty()){ Node n=q.poll(); System.out.print(n.data+" "); if(n.left!=null) q.add(n.left); if(n.right!=null) q.add(n.right); } } private int maxLen=0; private int max(int a,int b){ return a>b?a:b; } public void findMaxDistance(Node root){ if(root==null) return; if(root.left==null) root.leftMaxDistance=0; if(root.right==null) root.rightMaxDistance=0; if(root.left!=null) findMaxDistance(root.left); if(root.right!=null) findMaxDistance(root.right); //Calculate the maximum distance from the root node in the left word tree if(root.left!=null) root.leftMaxDistance=max(root.left.leftMaxDistance, root.left.rightMaxDistance)+1; //Calculate the maximum distance from the root node in the right word tree if(root.right!=null) root.rightMaxDistance=max(root.right.leftMaxDistance, root.right.rightMaxDistance)+1; //Get the maximum distance of all nodes of the binary tree if(root.leftMaxDistance+root.rightMaxDistance>maxLen){maxLen=root.leftMaxDistance+root.rightMaxDistance; } } 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.print("In-order traversal of binary tree: "); biTree.inOrder(); System.out.println(); System.out.print("Pre-order traversal of binary tree: "); biTree.preOrder(); System.out.println(); System.out.println(); System.out.println(); System.out.print("Post-order traversal of binary tree: "); biTree.postOrder(); System.out.println(); System.out.print("Layer-order traversal of binary tree: "); biTree.layerTranverse(); System.out.println(); biTree.findMaxDistance(biTree.root); System.out.println("Maximum distance of nodes in the binary tree: "+biTree.maxLen); }}The above is all the content of this article. I hope that the content of this article will be of some help to everyone’s study or work. I also hope to support Wulin.com more!