This article describes the depth-first traversal and breadth-first traversal algorithms that implement binary tree in Java. Share it for your reference, as follows:
1. Analysis
The common practice of non-recursiveness of depth-first traversal of binary trees is to adopt a stack, and the common practice of non-recursiveness of breadth-first traversal is to adopt a queue.
Depth-first traversal : Each possible branch path can be penetrated until it can't be further deep, and each node can only be accessed once. It should be noted that the depth-first traversal of the binary tree is quite special and can be subdivided into preorder traversal, intermediate traversal, and subsequent traversal. The specific description is as follows:
First order traversal : For any subtree, first access the root, then traverse its left subtree, and finally traverse its right subtree.
Middle order traversal : For any subtree, first traverse its left subtree, then access the root, and finally traverse its right subtree.
Post-order traversal : For any subtree, first traverse its left subtree, then traverse its right subtree, and finally access the root.
Breadth-first traversal : also known as hierarchy, accessing each layer from top to bottom in turn. In each layer, access nodes from left to right (or from right to left). After accessing one layer, you will enter the next layer until there are no nodes that can be accessed.
2. Give examples
The binary sorting tree shown in the figure below requires the use of preorder traversal (recursive, non-recursive), in-order traversal (recursive, non-recursive), postorder traversal (recursive, non-recursive), and breadth-first traversal.
① Reference code
package BinaryTreeTraverseTest;import java.util.LinkedList;import java.util.Queue;/** * Depth priority traversal and breadth priority traversal of binary trees* @author Fantasy * @version 1.0 2016/10/05 - 2016/10/07 */public class BinaryTreeTraverseTest { public static void main(String[] args) { BinarySortTree<Integer> tree = new BinarySortTree<Integer>(); tree.insertNode(35); tree.insertNode(20); tree.insertNode(15); tree.insertNode(16); tree.insertNode(29); tree.insertNode(28); tree.insertNode(30); tree.insertNode(40); tree.insertNode(50); tree.insertNode(45); tree.insertNode(55); System.out.print("Preorder traversal (recursive):"); tree.preOrderTraverse(tree.getRoot()); System.out.println(); System.out.print("In-order traversal (recursive):"); tree.inOrderTraverse(tree.getRoot()); System.out.println(); System.out.println(); System.out.print("Post-order traversal (recursive):"); tree.postOrderTraverse(tree.getRoot()); System.out.println(); System.out.print("Precursive traversal (non-recursive):"); tree.preOrderTraverseNoRecursion(tree.getRoot()); System.out.println(); System.out.print("In-order traversal (non-recursive):"); tree.inOrderTraverseNoRecursion(tree.getRoot()); System.out.println(); System.out.println(); System.out.print("Post-order traversal (non-recursive):"); tree.postOrderTraverseNoRecursion(tree.getRoot()); System.out.println(); System.out.print("BreadthPriority Traversal:"); tree.breadthFirstTraverse(tree.getRoot()); }}/** * Node*/class Node<E extends Comparable<E>> { E value; Node<E> left; Node<E> right; Node(E value) { this.value = value; left = null; right = null; }}/** * Use a precedent sequence to build a binary sorting tree (also known as a binary search tree) */class BinarySortTree<E extends Comparable<E>> { private Node<E> root; BinarySortTree() { root = null; } public void insertNode(E value) { if (root == null) { root = new Node<E>(value); return; } Node<E> currentNode = root; while (true) { if (value.compareTo(currentNode.value) > 0) { if (currentNode.right == null) { currentNode.right = new Node<E>(value); break; } currentNode = currentNode.right; } else { if (currentNode.left == null) { currentNode.left = new Node<E>(value); break; } currentNode = currentNode.left; } } } public Node<E> getRoot(){ return root; } /** * Pre-order traversal of the binary tree (recursive) * @param node */ public void preOrderTraverse(Node<E> node) { System.out.print(node.value + " "); if (node.left != null) preOrderTraverse(node.left); if (node.right != null) preOrderTraverse(node.right); } /** * In-order traversal of the binary tree (recursive) * @param node */ public void inOrderTraverse(Node<E> node) { if (node.left != null) inOrderTraverse(node.left); System.out.print(node.value + " "); if (node.right != null) inOrderTraverse(node.right); } /** * Post-order traversal of binary tree (recursive) * @param node */ public void postOrderTraverse(Node<E> node) { if (node.left != null) postOrderTraverse(node.left); if (node.right != null) postOrderTraverse(node.right); System.out.print(node.value + " "); } /** * Pre-order traversal of the binary tree (non-recursive) * @param root */ public void preOrderTraverseNoRecursion(Node<E> root) { LinkedList<Node<E>> stack = new LinkedList<Node<E>>(); Node<E> currentNode = null; stack.push(root); while (!stack.isEmpty()) { currentNode = stack.pop(); System.out.print(currentNode.value + " "); if (currentNode.right != null) stack.push(currentNode.right); if (currentNode.left != null) stack.push(currentNode.left); } } /** * In-order traversal of binary tree (non-recursive) * @param root */ public void inOrderTraverseNoRecursion(Node<E> root) { LinkedList<Node<E>> stack = new LinkedList<Node<E>>(); Node<E> currentNode = root; while (currentNode != null || !stack.isEmpty()) { // Loop until the leftmost leaf node at the binary sorting tree (currentNode is null) while (currentNode != null) { stack.push(currentNode); currentNode = currentNode.left; } currentNode = stack.pop(); System.out.print(currentNode.value + " "); currentNode = currentNode.right; } } /** * Post-order traversal of the binary tree (non-recursive) * @param root */ public void postOrderTraverseNoRecursion(Node<E> root) { LinkedList<Node<E>> stack = new LinkedList<Node<E>>(); Node<E> currentNode = root; Node<E> rightNode = null; while (currentNode != null || !stack.isEmpty()) { // Loop until the leaf node at the leftmost end of the binary sorting tree (currentNode is null) while (currentNode != null) { stack.push(currentNode); currentNode = currentNode.left; } currentNode = stack.pop(); // The current node has no right node or the previous node (the node that has been output) is the right node of the current node, then the current node is output while (currentNode.right == null || currentNode.right == rightNode) { System.out.print(currentNode.value + " "); rightNode = currentNode; if (stack.isEmpty()) { return; //root outputs, the traversal ends} currentNode = stack.pop(); } stack.push(currentNode); //There is still the right node that does not traverse currentNode = currentNode.right; } } /** * Breadth-first traverse binary tree, also known as hierarchical traversal binary tree* @param node */ public void breadthFirstTraverse(Node<E> root) { Queue<Node<E>> queue = new LinkedList<Node<E>>(); Node<E> currentNode = null; queue.offer(root); while (!queue.isEmpty()) { currentNode = queue.poll(); System.out.print(currentNode.value + " "); if (currentNode.left != null) queue.offer(currentNode.left); if (currentNode.right != null) queue.offer(currentNode.right); } }}② Output result
Preorder traversal (recursive): 35 20 15 16 29 28 30 40 50 45 55
In-order traversal (recursion): 15 16 20 28 29 30 35 40 45 50 55
Postorder traversal (recursion): 16 15 28 30 29 20 45 55 50 40 35
Preorder traversal (non-recursive): 35 20 15 16 29 28 30 40 50 45 55
In-order traversal (non-recursive): 15 16 20 28 29 30 35 40 45 50 55
Postorder traversal (non-recursive): 16 15 28 30 29 20 45 55 50 40 35
Breadth priority traversal: 35 20 40 15 29 50 16 28 30 45 55
For more information about Java algorithms, readers who are interested in this site can view the topics: "Java Data Structure and Algorithm Tutorial", "Summary of Java Operation DOM Node Tips", "Summary of Java File and Directory Operation Tips" and "Summary of Java Cache Operation Tips"
I hope this article will be helpful to everyone's Java programming.