Tree traversal:

1. Pre-order traversal

Pre-order traversal (DLR, Lchild,data, Rchild), is a kind of binary tree traversal, also known as pre-root traversal, pre-order traversal, pre-order tour, can be remembered as root left and right. A front-order traversal first visits the root, then the left subtree, and finally the right subtree.

A front-order traversal first visits the root, then the left subtree, and finally the right subtree. When traversing the left and right subtrees, we still visit the root first, then the left subtree, and finally the right subtree. If the binary tree is empty, end the return, otherwise:

  • Access the root.
  • Preemptively traverses the left subtree.
  • Preemptively traverses the right subtree.

Note that the forward traversal method is still used when traversing the left and right subtrees. The binary tree is shown

 

Fore-order traversal result: ABDECF

Anteorder ergodic can be determined if postorder ergodic and middle order ergodic are known.

There are actually three traversals of a binary tree, such as:

Sequential traversal: – > D – A – > B > D (D left child node and returns to the D) – > D (D) and return to the right child node D – > – > E B – > E (l) – > E (r) – > – – > A – > B > C – > F – > F (l) – > F (r) – > C – > C (right), so you can use the stack structure, pressed to traverse the node into the stack, stack again when there is no child node. You can also recursively output the current node, recursively output the left child, and recursively output the right child. It’s better to look directly at the code:

import java.util.Stack; Public class Test {public static void main(String[] args) {TreeNode[] node = new TreeNode[10]; for (int i = 0; i < 10; i++) { node[i] = new TreeNode(i); } for (int i = 0; i < 10; i++) { if (i * 2 + 1 < 10) node[i].left = node[i * 2 + 1]; if (i * 2 + 2 < 10) node[i].right = node[i * 2 + 2]; } preOrderRe(node[0]); } public static void preOrderRe(TreeNode biTree) {system.out.println (bitree.value); TreeNode leftTree = biTree.left; if (leftTree ! = null) { preOrderRe(leftTree); } TreeNode rightTree = biTree.right; if (rightTree ! = null) { preOrderRe(rightTree); Public static void preOrder(TreeNode biTree) {Stack<TreeNode> Stack = new Stack<TreeNode>(); while (biTree ! = null || ! stack.isEmpty()) { while (biTree ! = null) { System.out.println(biTree.value); stack.push(biTree); biTree = biTree.left; } if (! stack.isEmpty()) { biTree = stack.pop(); biTree = biTree.right; }}}} // Node structure class TreeNode {int value; TreeNode left; TreeNode right; TreeNode(int value) { this.value = value; }}Copy the code

2. Middle order traversal

Middle order traversal (LDR) is a kind of binary tree traversal, also known as middle root traversal, middle order tour. In binary trees, first left, then root, then right. Remember: left root right. A middle-order traversal first traverses the left subtree, then the root, and finally the right subtree. If the binary tree is empty, end the return, otherwise:

  • Middle order traverses the left subtree
  • Accessing the root
  • Middle order traverses the right subtree

The binary tree is shown

Middle order traversal result: DBEAFC

Public class Test {public static void main(String[] args) {// Generate a full binary tree TreeNode[] node = new TreeNode[10]; for (int i = 0; i < 10; i++) { node[i] = new TreeNode(i); } for (int i = 0; i < 10; i++) { if (i * 2 + 1 < 10) node[i].left = node[i * 2 + 1]; if (i * 2 + 2 < 10) node[i].right = node[i * 2 + 2]; } midOrderRe(node[0]); System.out.println(); midOrder(node[0]); } public static void midOrderRe(TreeNode biTree) {if (biTree == null) return; else { midOrderRe(biTree.left); System.out.println(biTree.value); midOrderRe(biTree.right); Public static void midOrder(TreeNode biTree) {Stack<TreeNode> Stack = new Stack<TreeNode>(); while (biTree ! = null || ! stack.isEmpty()) { while (biTree ! = null) { stack.push(biTree); biTree = biTree.left; } if (! stack.isEmpty()) { biTree = stack.pop(); System.out.println(biTree.value); biTree = biTree.right; }}}} // Node structure class TreeNode {int value; TreeNode left; TreeNode right; TreeNode(int value) { this.value = value; }}Copy the code

3. Post-order traversal (difficult points)

Post-order traversal (LRD) is a kind of binary tree traversal, also known as post-root traversal, post-order tour, can be remembered as left and right roots. There are two kinds of post-order traversal: recursive algorithm and non-recursive algorithm. In a binary tree, the root is left, then right. Remember: left and right root.

Back-order traversal first traverses the left subtree, then the right subtree, and finally the root. When traversing the left and right subtrees, the left subtree is traversed first, then the right subtree, and finally the root. That is, if the binary tree is empty, the end return,

Otherwise:

  • The left subtree is traversed sequentially
  • The right subtree is traversed sequentially
  • Accessing the root

The binary tree is shown

Subsequent traversal result: DEBFCA

Postorder ergodic can be determined if preorder ergodic and middle order ergodic are known.

Core ideas of the algorithm:

First of all, we need to understand what the sequential, middle-order and back-order non-recursive algorithms have in common: the stack is used to store the previous path, so that after accessing the subtree, we can use the information in the stack to go back to the parent node of the current node for the next operation.

After sequence traversal of non-recursive algorithm is the most complicated in three kinds of order, the reason is that after the sequence traversal is to access to the left and right subtrees first, then access to the root node, and in non-recursive algorithm, using the stack back by that time, did not know from left subtree is back to the root node, or from the right subtree is back to the root node, if left subtree is back to the root node, at this time you should visit right subtree, If you go back from the right subtree to the root node, you should access the root node. So, in contrast to pre and post, you have to add information when you push the stack so that when you push the stack you know whether you’re going back from the left subtree or the right subtree to decide what to do next.

Public class Test {public static void main(String[] args) {// Generate a full binary tree TreeNode[] node = new TreeNode[10]; for (int i = 0; i < 10; i++) { node[i] = new TreeNode(i); } for (int i = 0; i < 10; i++) { if (i * 2 + 1 < 10) node[i].left = node[i * 2 + 1]; if (i * 2 + 2 < 10) node[i].right = node[i * 2 + 2]; } postOrderRe(node[0]); System.out.println("***"); postOrder(node[0]); } public static void postOrderRe(TreeNode biTree) {if (biTree == null) return; else { postOrderRe(biTree.left); postOrderRe(biTree.right); System.out.println(biTree.value); }} public static void postOrder(TreeNode biTree) {public static void postOrder(TreeNode biTree); Int right = 2; Stack<TreeNode> stack = new Stack<TreeNode>(); // Secondary stack, used to determine whether the child node returns to the parent node on the left or right node. Stack<Integer> stack2 = new Stack<Integer>(); // Push the node onto stack 1 and mark the node as the left node on stack 2 while (biTree! = null || ! stack.empty()) { while (biTree ! = null) { stack.push(biTree); stack2.push(left); biTree = biTree.left; } // If the parent node is returned from the right child node, then the task is complete, pop the top of both stacks while (! stack.empty() && stack2.peek() == right) { stack2.pop(); System.out.println(stack.pop().value); } // If the parent is returned from the left child, change the flag to the right child if (! stack.empty() && stack2.peek() == left) { stack2.pop(); stack2.push(right); biTree = stack.peek().right; }}}} // Node structure class TreeNode {int value; TreeNode left; TreeNode right; TreeNode(int value) { this.value = value; }}Copy the code

Hierarchy traversal

Different from DFS, hierarchy traversal uses BFS. While DFS is implemented recursively (or on a stack), BFS is implemented in queues.

The steps of hierarchical traversal are:

  • **** For nodes that are not empty, add the node to the queue first
  • Take the node from the queue, and if the left and right nodes of the node are not empty, add the left and right nodes to the queue
  • Repeat until the queue is empty
Public static void levelOrder(TreeNode biTree) {if(biTree == null) return; LinkedList<TreeNode> list = new LinkedList<TreeNode>(); list.add(biTree); TreeNode currentNode; while(! list.isEmpty()) { currentNode = list.poll(); System.out.println(currentNode.value); if(currentNode.left ! = null) list.add(currentNode.left); if(currentNode.right ! = null) list.add(currentNode.right); }}Copy the code