A binary tree is traversed to access every node in the tree (only once). However, since the tree structure is different from the previous linear storage, binary trees can have a variety of access order choices, starting at the root. According to our usual left-to-right habit, there are three common traversal orders: preorder, middle order and subsequent order.

What is preorder, middle order and post order

For the sake of illustration, let’s think of accessing a node as printing out information about that node. So how to distinguish between the front, middle and back is also based on the order of output.

  • Pre-order traversal: Prints the parent node, traverses the left subtree, and then traverses the right subtree
  • Middle-order traversal: First traverses the left subtree, then outputs the parent node, then traverses the right subtree
  • Subsequent traversal: First traverses the left subtree, then the right subtree, and finally outputs the parent node



As shown in the figure, the output sequence of the binary tree is as follows:

1 Foreword: 1 Master Yi, 2 Ice Archer, 3 Blind Monk, 4 Galen

2 Middle preface: 2 Ice Archer, 1 Master Yi, 3 Blind Monk, 4 Galen

Postsequence: 2 Ice Shooter, 4 Galen, 3 Blind Monk, 1 Master Yi

Two, the code to achieve before, in, after order traversal

The implementation idea is very simple:

  1. Create the hero node and write the traversal method here
  2. Create a binary tree and call the traversal method
  3. The main method is used to test
package tree; Public class BinaryTreeDemo {public static void main(String[] args) {// Test BinaryTree traversal BinaryTree = new BinaryTree(); // Create node HeroNode hero1 = new HeroNode(1, "Master "); HeroNode Hero2 = new HeroNode(2, "Ice Archer "); HeroNode Hero3 = new HeroNode(3, "Blind monk "); HeroNode Hero4 = new HeroNode(4, "Galen "); Hero1.setleft (hero2); hero1.setLeft(hero2); hero1.setRight(hero3); hero3.setRight(hero4); binaryTree.setRoot(hero1); / / as a root node / / test preorder traversal System. Out. The println (" preorder traversal test -- -- -- -- -- -- -- -- -- "); binaryTree.preOrder(); System.out.println(" ---------"); // System.out.println(" ---------"); binaryTree.infixOrder(); System.out.println(" ---------"); // System.out.println(" ---------"); binaryTree.postOrder(); }} // 2. Class BinaryTree {private HeroNode root; Public void setRoot(HeroNode root) {this.root = root; } public void preOrder() {if (this.root! = null) { this.root.preOrder(); } else {system.out.println (" Binary tree is empty, cannot be traversed "); Public void infixOrder() {if (this.root! = null) { this.root.infixOrder(); } else {system.out.println (" Binary tree is empty, cannot be traversed "); Public void postOrder() {if (this.root! = null) { this.root.postOrder(); } else {system.out.println (" Binary tree is empty, cannot be traversed "); Class HeroNode {private int No; private String name; private HeroNode left; private HeroNode right; public int getNo() { return No; } public void setNo(int no) { No = no; } public String getName() { return name; } public void setName(String name) { this.name = name; } public HeroNode getLeft() { return left; } public void setLeft(HeroNode left) { this.left = left; } public HeroNode getRight() { return right; } public void setRight(HeroNode right) { this.right = right; } public HeroNode(int no, String name) { this.No = no; this.name = name; } @Override public String toString() { return "HeroNode{" + "No=" + No + ", name='" + name + '\'' + '}'; Public void preOrder() {system.out.println (this); If (this.left! = this.left! = null) { this.left.preOrder(); } // If (this.right! = null) { this.right.preOrder(); }} public void infixOrder() {if (this.left! = null) { this.left.infixOrder(); } // Output parent system.out.println (this); // if (this.right! = null) { this.right.infixOrder(); }} public void postOrder() {if (this.left! = null) { this.left.postOrder(); } // If (this.right! = null) { this.right.postOrder(); } // Output parent system.out.println (this); }}Copy the code

Run the test

--------- HeroNode{No=1, name=' Master '} HeroNode{No=2, name=' Ice Shooter '} HeroNode{No=3, name=' blind monk '} HeroNode{No=4, Name = 'galen'} sequence traversal test -- -- -- -- -- -- -- -- -- HeroNode {No = 2, name = 'ice striker'} HeroNode {No = 1, name = 'easy to master'} HeroNode {No = 3, HeroNode name = 'blind monk'} {No = 4, name = 'galen'} sequence traversal test -- -- -- -- -- -- -- -- -- HeroNode {No = 2, name = 'ice striker'} HeroNode {No = 4, Name =' Galen '} HeroNode{No=3, name=' blind Monk '} HeroNode{No=1, name=' Master '} Process finished with exit code 0Copy the code

The traversal order is consistent with the prediction above. If you’re not familiar with recursion, you can go to this one. After listening to python recursion for the first time, you’ll get the idea.

In this chapter we know how to traverse a binary tree, but if I want to find a node in a binary tree, what are the three ways to find it? So let’s continue.