Establishment of binary trees and various traversal instance codes in Java

This is a common interview question, such as obtaining the hierarchical traversal of the binary tree through the preorder and in-order traversal of the binary tree, etc.

Preorder + middle order ->Build

Suppose there is now a binary tree, as follows:

At this time, the traversal order is:

 PreOrder: GDAFEMHZ InOrder: ADEFGHMZ PostOrder: AEFDHZMG

Now give preOrder and in-order (InOrder), create a binary tree or give in-order (InOrder) and post-order (PostOrder), create a binary tree, it is actually the same

Definition of tree node:

 class Tree{char val;Tree left;Tree right;Tree(char val, Tree left, Tree right){this.val = val;this.left = left;this.right = right;}Tree(){}Tree(char val){this.val = val;this.left = null;this.right = null;}}

Make achievements:

 public static Tree buildTree(char[] preOrder, char[] inOrder){//preOrder is the preorder sequence//inOrder is the middle sequence if(preOrder == null || preOrder.length == 0){return null;}Tree root = new Tree(preOrder[0]);//Find the position of root in inOrder int inOrderIndex = 0; for (char i = 0; i < inOrder.length; i++){if(inOrder[i] == root.val){inOrderIndex = i;}}//The left subtree and right subtree part of preOrder char[] preOrderLeft = Arrays.copyOfRange(preOrder, 1, 1+inOrderIndex);char[] preOrderRight = Arrays.copyOfRange(preOrder, 1+inOrderIndex, preOrder.length);//The left subtree and right subtree part of inOrder char[] inOrderLeft = Arrays.copyOfRange(inOrder, 0, inOrderIndex);char[] inOrderRight = Arrays.copyOfRange(inOrder, inOrderIndex+1, inOrder.length);//Recursively build the left subtree and the right subtree Tree leftChild = buildTree(preOrderLeft, inOrderLeft);Tree rightChild = buildTree(preOrderRight, inOrderRight);root.left = leftChild;root.right = rightChild;return root;}

It is actually the same to create a middle order + post-order. I won't write it here

Various traversals

Post-order traversal

 public static void postOrderPrint(Tree root){ //Subsequent traversal//Left left and right roots if(root.left != null){ postOrderPrint(root.left); } if(root.right != null){ postOrderPrint(root.right); } System.out.print(root.val + " "); }

Learn from one example and the order is the same as the order in the middle. I will not write it here

Layer sequence traversal

You can use a queue queue Queue to first add the root node to the queue. When the queue is not empty, take the node node of the queue head and print the node value of the node. If the node's left and right children are not empty, add the left and right children to the queue.

 public static void layerOrderPrint(Tree root){ if(root == null){ return; } //Layer sequence traversal Queue<Tree> qe = new LinkedList<Tree>(); qe.add(root); while(!qe.isEmpty()){ Tree node = qe.poll(); System.out.print(node.val + " "); if(node.left != null){ qe.add(node.left); } if(node.right != null){ qe.add(node.right); } } }

Depth and breadth priority

In fact, it's just a different saying. Depth priority is pre-order traversal, breadth priority is layer-order traversal.

 public static void deepFirstPrint(Tree root){ //Deep priority traversal is equivalent to preorder traversal//So you can directly use preorder traversal if(root == null){ return; } System.out.print(root.val + " "); if(root.left != null){ deepFirstPrint(root.left); } if(root.right != null){ deepFirstPrint(root.right); } } public static void deepFirstPrintNoneRec(Tree root){ //The non-recursive form of depth priority traversal if(root == null){ return; } Stack<Tree> st = new Stack<Tree>(); st.add(root); while(!st.isEmpty()){ Tree node = st.pop(); System.out.print(node.val + " "); //The stack is back in and first out //Add the right child first and then the left child if(node.right != null){ st.add(node.right); } if(node.left != null){ st.add(node.left); } } }

Main function:

 public static void main(String[] args) { char[] preOrder = "GDAFEMHZ".toCharArray(); char[] inOrder = "ADEFGHMZ".toCharArray(); Tree root = Main.buildTree(preOrder, inOrder);// Main.postOrderPrint(root); //Postorder traversal// Main.layerOrderPrint(root); //Layer sequence traversal// Main.deepFirstPrint(root); //Deep priority traversal// Main.deepFirstPrintNoneRec(root); //The non-recursive version of depth-first traversal}

Summarize

The above is all about the establishment of binary trees and various traversal instance codes in Java. I hope it will be helpful to everyone. Interested friends can continue to refer to this site:

" Introduction to Two Methods of Mirroring in Java Programming Binary Trees "

" Java Language Describes the Depth and Width of Binary Tree "

Java Binary Tree Path and Code Example

If there are any shortcomings, please leave a message to point it out. Thank you friends for your support for this site!