Java Binary tree for chain storage

The definition of binary tree ：

Binary tree (BinaryTree) yes n(n≥0) A finite set of nodes , It’s either an empty set (n=0), Or by a root node and two disjoint 、 A binary tree called the left subtree and the right subtree of this root respectively .
The traversal ways of binary tree mainly include ： The first sequence traversal (NLR), In the sequence traversal (LNR), After the sequence traversal (LRN), And level traversal .

Be careful ：

A binary tree can be uniquely determined by the preorder sequence and the middle order sequence of the binary tree ;

A binary tree can be uniquely determined by the post order sequence and the middle order sequence of the binary tree ;

A binary tree can be uniquely determined by the sequence sequence and meso sequence of the binary tree ;

but , It is impossible to uniquely determine a binary tree from the preorder sequence and the postorder sequence of a binary tree .

Java Realize the binary tree of chain storage and its various traversal algorithms ：

Tree node ：

public class TreeNode<E> {
private E data; // Data fields
private TreeNode<E> lchild; // Left the child
private TreeNode<E> rchild; // The right child
TreeNode(){}
TreeNode(E e){
this.data = e;
}
TreeNode(E data,TreeNode<E> lchild, TreeNode<E> rchild){
this.data = data;
this.lchild = lchild;
this.rchild = rchild;
}
public void setData(E data){
this.data = data;
}
public E getData(){
return this.data;
}
public void setLchild(TreeNode<E> lchild){
this.lchild = lchild;
}
public TreeNode<E> getLchild(){
return this.lchild;
}
public void setRchild(TreeNode<E> rchild){
this.rchild = rchild;
}
public TreeNode<E> getRchild(){
return this.rchild;
}
}

  Binary tree Java Realization ：

import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Stack;
/**
* @author Cherish
* The chain storage structure of binary tree
* @param <E>
*/
public class BinaryTree<E> {
private TreeNode<E> root; // The root node
private List<TreeNode> nodeList = null; // The chain structure of binary tree nodes
public BinaryTree(){
}
public BinaryTree(TreeNode<E> root){
this.root = root;
}
// Convert an array into a complete binary tree
public TreeNode<E> buildTree(E[] array){
nodeList = new LinkedList<TreeNode>();
// Convert the elements in the array to TreeNode node , Store in the list
for(int i=0; i< array.length; i++){
nodeList.add(new TreeNode(array[i]));
}
// To the front （array.length / 2 - 1） Parent nodes , Establish a complete binary tree according to the digital relationship between the parent node and the child node
// For a complete binary tree , Press from top to bottom , Number from left to right 0,1,2,3....N, be i>0 The node of , The left child is （2*i+1）,
// The right child is （2*i+2）
for(int j=0; j < (array.length/2-1);j++){
// Left the child
nodeList.get(j).setLchild(nodeList.get(j*2+1));
// The right child
nodeList.get(j).setRchild(nodeList.get(j*2+2));
}
// The last parent node ： Because the last parent node may not have a right child , So deal with it alone
int index = array.length/2 -1;
// Left the child
nodeList.get(index).setLchild(nodeList.get(index*2+1));
// The right child ： If the length of the array is odd, there will be right children
if(array.length % 2 == 1){
nodeList.get(index).setRchild(nodeList.get(index*2+2));
}
root=nodeList.get(0); // Set the root node
return root;
}
// Get the height of the tree
public int height(TreeNode<E> node){
if(node == null){
return 0;
}else{
int i = height(node.getLchild());
int j = height(node.getRchild());
return (i<j)?(j+1):(i+1);
}
}
// Get the number of nodes
public int size(TreeNode<E> node){
if(node == null){
return 0;
}else{
return 1+ size(node.getLchild())+size(node.getRchild());
}
}
// Recursive implementation of first order traversal NLR
public void preOrder(TreeNode<E> node){
if(node != null){
System.out.print(node.getData() + " ");
preOrder(node.getLchild());
preOrder(node.getRchild());
}
}
// Non recursive implementation of first order traversal NLR
public void nonRecPreOrder(TreeNode<E> node){
Stack<TreeNode<E>> nodeStack = new Stack<TreeNode<E>>();
TreeNode<E> nodeTemp = node; //nodeTemp As traversal pointer
while(nodeTemp != null || !nodeStack.isEmpty()){ // When nodeTemp Non empty or stack non empty cycle
if(nodeTemp != null){ // Root pointer is not null , Traverse left subtree
nodeStack.push(nodeTemp); // The root pointer goes into the stack
System.out.print(nodeStack.peek().getData() + " "); // Backstack the root pointer , Access the root node
nodeTemp = nodeTemp.getLchild(); // Every time I meet a non empty binary tree, I will go to the left first
}else{ // Then go to the right sub tree
nodeTemp = nodeStack.pop();
nodeTemp = nodeTemp.getRchild();
}
}
}
// Recursive implementation of middle order traversal LNR
public void inOrder(TreeNode<E> node){
if(node != null){
inOrder(node.getLchild());
System.out.print(node.getData() + " ");
inOrder(node.getRchild());
}
}
// Non recursive implementation of middle order traversal LNR
public void nonRecInOrder(TreeNode<E> node){
Stack<TreeNode<E>> nodeStack = new Stack<TreeNode<E>>();
TreeNode<E> nodeTemp = node; //nodeTemp As traversal pointer
while(nodeTemp != null || !nodeStack.isEmpty()){ // When nodeTemp Non empty or stack non empty cycle
if(nodeTemp != null){ // Root pointer is not null , Traverse left subtree
nodeStack.push(nodeTemp); // The root pointer goes into the stack
nodeTemp = nodeTemp.getLchild(); // Every time I meet a non empty binary tree, I will go to the left first
}else{
nodeTemp = nodeStack.pop(); // Backstack the root pointer , Access the root node
System.out.print(nodeTemp.getData() +" ");
nodeTemp = nodeTemp.getRchild(); // Then go to the right sub tree
}
}
}
// Recursive implementation of post order traversal LNR
public void postOrder(TreeNode<E> node){
if(node != null){
postOrder(node.getLchild());
postOrder(node.getRchild());
System.out.print(node.getData() + " ");
}
}
// Non recursive implementation of post order traversal LNR
public void nonRecPostOrder(TreeNode<E> node){
Stack<TreeNode<E>> nodeStack = new Stack<TreeNode<E>>();
TreeNode<E> nodeTemp = node; //nodeTemp As traversal pointer
TreeNode<E> preNode = null; // Represents the last visited node
while(nodeTemp != null || !nodeStack.isEmpty()){ // When nodeTemp Non empty or stack non empty cycle
while(nodeTemp != null){ // Go all the way to the left , Traverse left subtree
nodeStack.push(nodeTemp);
nodeTemp = nodeTemp.getLchild();
}
nodeTemp = nodeStack.peek();
if(nodeTemp.getRchild()==null || nodeTemp.getRchild() == preNode){ // When the right subtree is empty or has been accessed , This node is out of the stack
nodeTemp = nodeStack.pop();
System.out.print(nodeTemp.getData()+" ");
preNode = nodeTemp; // Assign this node to the last access node
nodeTemp = null; // It's important here , Set the just out of stack node to null , Corresponding to while One of the conditions of the cycle , Otherwise, it will fall into a dead cycle
}else{
nodeTemp = nodeTemp.getRchild(); // Traversal right subtree
}
}
}
// Level traversal
public void levelOrder(TreeNode<E> root){
Queue<TreeNode<E>> nodeQueue = new LinkedList<TreeNode<E>>();
TreeNode<E> node = null;
nodeQueue.add(root); // Put the root node in the team
while(!nodeQueue.isEmpty()){ // The queue is not empty
node = nodeQueue.peek();
System.out.print(node.getData()+" ");
nodeQueue.poll(); // Team leader element out of the team
if(node.getLchild() != null){ // Zuozi tree is not empty , Then the left subtree enters the queue
nodeQueue.add(node.getLchild());
}
if(node.getRchild() != null){ // Right subtree is not empty , Then the right subtree enters the queue
nodeQueue.add(node.getRchild());
}
}
}
public static void main(String args[]){
// Convert an array into a complete binary tree
Object[] array = {1,2,3,4,5,6,7,8};
BinaryTree bt = new BinaryTree();
TreeNode root = bt.buildTree(array);
System.out.print(" The height of the tree ：");
System.out.println(bt.height(root));
System.out.print(" Number of nodes ：");
System.out.println(bt.size(root));
System.out.println(" The first sequence traversal ：");
bt.preOrder(root);
System.out.println("\n"+" Non recursive preorder traversal ：");
bt.nonRecPreOrder(root);
System.out.println();
System.out.println(" In the sequence traversal ：");
bt.inOrder(root);
System.out.println("\n"+" Non recursive middle order traversal ：");
bt.nonRecInOrder(root);
System.out.println();
System.out.println(" After the sequence traversal ：");
bt.postOrder(root);
System.out.println("\n"+" Non recursive postorder traversal ：");
bt.nonRecPostOrder(root);
System.out.println();
System.out.println(" Level traversal ：");
bt.levelOrder(root);
// Build a binary tree by hand
TreeNode nodeA = new TreeNode("A");
TreeNode nodeB = new TreeNode("B");
TreeNode nodeC = new TreeNode("C");
TreeNode nodeD = new TreeNode("D");
TreeNode nodeE = new TreeNode("E");
TreeNode nodeF = new TreeNode("F");
TreeNode nodeG = new TreeNode("G");
TreeNode nodeH = new TreeNode("H");
TreeNode nodeI = new TreeNode("I");
nodeA.setLchild(nodeB);
nodeA.setRchild(nodeD);
nodeB.setRchild(nodeC);
nodeD.setLchild(nodeE);
nodeD.setRchild(nodeF);
nodeF.setLchild(nodeG);
nodeF.setRchild(nodeI);
nodeG.setRchild(nodeH);
System.out.println("\n\n"+"*****************");
System.out.print(" The height of the tree ：");
System.out.println(bt.height(nodeA));
System.out.print(" Number of nodes ：");
System.out.println(bt.size(nodeA));
System.out.println(" The first sequence traversal ：");
bt.preOrder(nodeA);
System.out.println();
System.out.println(" In the sequence traversal ：");
bt.inOrder(nodeA);
System.out.println();
System.out.println(" After the sequence traversal ：");
bt.postOrder(nodeA);
System.out.println();
System.out.println(" Level traversal ：");
bt.levelOrder(nodeA);
}
}

  The running result of the above program ：

Reference blog ：

https://www.cnblogs.com/CherishFX/p/4617105.html