This is the ninth day of my participation in the First Challenge 2022. For details: First Challenge 2022.

Everybody to the tree and the traversal of the complex data structure, we traverse the tree, for example, today to take everyone to have a look at how we should to traverse a tree, different ways of traverse what characteristic, we use daily way traversal is depth first and breadth-first algorithm, we study together.

preface

Depth First Search (DFS) and Breath First Search (Breath First Search) are two very important algorithms in graph theory. They can often be used for tree and graph traversal. In production, they can generally be used for topology sorting, pathfinding (maze running), Search engine, etc. Crawlers and so on, they are also frequently tested in algorithmic interviews.

Depth-first traversal (DFS)

The main idea is to start at an unvisited vertex V in the graph, or at the root of the tree, follow a path to the end (for example, in a tree structure, the tree ends at the leftmost node), then back up from the node at the end of the path to the previous node, and start the other way to the end… , recursively repeat this process until all vertices have been traversed. It is characterized by not hitting the south wall and not turning back. It first goes one way and then moves on another way.

Depth-first traversal generally has two ways: recursion and stack

As shown, the traversal order for depth-first traversal is 12,5,1,6,19,13

This is also a classic pre-order traversal. Similarly, middle-order traversal and post-order traversal can be traversed through the depth-first idea

The following is a recursive depth-first traversal

/** */ public class BinaryTree {// private TreeNode root; / * -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- traversing binary tree 1 2 3 4 5 6 7 recursive thinking: preorder traversal: 1, 2, four, five, sequence traversal in 3, 6, 4,2,5, 1, 6,3,7 sequence traversal after: Public void frontShow() {system.out.println (" frontShow: "); if (root! =null) { root.frontShow(); } else {system.out.println (" empty tree "); } System.out.println(); } public void midShow() {system.out.println (" "); if (root! =null) { root.midShow(); } else {system.out.println (" empty tree "); } System.out.println(); } public void rearShow() {system.out.println (" "); if (root! =null) { root.rearShow(); } else {system.out.println (" empty tree "); } System.out.println(); }}Copy the code
/** * @data public class TreeNode {private int value; private Byte data; // TreeNode leftNode; // TreeNode rightNode; / * -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- traversing binary tree 1 2 3 4 5 6 7 recursive thinking: preorder traversal: 1, 2, four, five, sequence traversal in 3, 6, 4,2,5, 1, 6,3,7 sequence traversal after: Public void frontShow() {system.out.print (value + "\t"); // If (leftNode! =null) { leftNode.frontShow(); } // rightNode if(rightNode! =null) { rightNode.frontShow(); }} public void midShow() {// if(leftNode! =null) { leftNode.midShow(); } system.out. print(value + "\t"); // rightNode if(rightNode! =null) { rightNode.midShow(); }} public void rearShow() {// if(leftNode! =null) { leftNode.rearShow(); } // rightNode if(rightNode! =null) { rightNode.rearShow(); } system.out. print(value + "\t"); }}Copy the code

Traversal through the stack

Public void dfsWithStack(TreeNode root) {if (root == null) {return; } Stack<TreeNode> stack = new Stack<>(); // First push the root node stack.push(root); while (! stack.isEmpty()) { TreeNode treeNode = stack.pop(); System.out.print(treenode. value + "\t"); If (treenode.right! = null) { stack.push(treeNode.right); } // press left if (treenode.left! = null) { stack.push(treeNode.left); }}}Copy the code

Breadth-first traversal (BFS)

Breadth-first traversal refers to starting from an untraversed node V of the graph, or from the root of the tree, traversing the adjacent nodes of that node first, and then the adjacent nodes of each adjacent node in turn. From the tree’s point of view it’s a layer by layer walk from the root node.

Breadth-first traversal is usually done through queues

@param root */ private static void bfsWithQueue(TreeNode root) {if (root == null) {return; } Queue<TreeNode> queue = new LinkedList<>(); queue.add(root); while (! queue.isEmpty()) { TreeNode node = queue.poll(); System.out.println("value = " + node.value); TreeNode left = node.left; if (left ! = null) { queue.add(left); } TreeNode right = node.right; if (right ! = null) { queue.add(right); }}}Copy the code

The instance

DFS instance

Given a set of department data (including department ID, parent department ID, and department name), we need to print it hierarchally according to the upper and lower departments. In this case, we can use the idea of depth-first traversal to find the first-level department, which is the root node of the tree, and then go all the way to its sub-departments. Until all subdivisions of a department (including subdivisions of subdivisions…) Once we’re done, we get our department tree.

package com.zhj.interview; import java.util.ArrayList; import java.util.Arrays; import java.util.List; /** * @author zhj */ public class Test05 { static class Node { int id; int parentId; String name; public Node(int id, int parentId, String name) { this.id = id; this.parentId = parentId; this.name = name; } } public static void main(String[] args) { List<Node> nodeList = Arrays.asList( new Node(1, 0, "AA"), new Node(2, 1, "BB"), new Node(3, 1, "CC"), new Node(4, 3, "DD"), new Node(5, 3, "EE"), new Node(6, 2, "FF"), new Node(7, 2, "GG"), new Node(8, 4, "HH"), new Node(9, 5, "II"), new Node(10, 0, "JJ"), new Node(11, 10, "KK"), new Node(12, 10, "LL"), new Node(13, 12, "MM"), new Node(14, 13, "NN"), new Node(15, 14, "OO") ); print(nodeList); } public static void print(List<Node> nodeList) { //todo List<Node> rootList = findRoot(nodeList); for (Node node : rootList) { System.out.println(node.name); getSon(nodeList, node.id, 1); @param nodeList @return */ public static List<Node> findRoot(List<Node> nodeList) {List<Node> rootList = new ArrayList<>(); for (Node node : nodeList) { boolean isNotRoot = false; for (Node n : nodeList) { if (node.parentId == n.id) { isNotRoot = true; break; } } if (! isNotRoot) { rootList.add(node); } } return rootList; } @param nodeList @param id @param level @return */ public static Node getSon(List<Node>) nodeList,Integer id, int level) { for (Node node : nodeList) { if (node.parentId == id) { for (int i = 0; i < level; i++) { System.out.print("\t"); } System.out.println(node.name); getSon(nodeList, node.id, level+1); } } return null; }}Copy the code

Print result:

AA
    BB
        FF
        GG
    CC
        DD
            HH
        EE
            II
JJ
    KK
    LL
        MM
            NN
                OO
Copy the code

BFS instance

Force buckle 107 binary tree sequence traversal, like DFS can also use BFS to solve, but their respective characteristics are not the same, BFS is layer traversal, DFS is a way to go to the end, the desperate will return to another way, we should give full play to the advantages of the algorithm.

package com.zhj.leetcode; import java.util.ArrayList; import java.util.LinkedList; import java.util.List; import java.util.Queue; Public class Test107 {public static void main(String[] args) {TreeNode root = new TreeNode(10); root.left = new TreeNode(5); root.right = new TreeNode(15); root.left.left = new TreeNode(3); root.left.right = new TreeNode(7); root.right.right = new TreeNode(18); List<List<Integer>> res = bfs(root); for (List<Integer> re : res) { for (Integer i : re) { System.out.print(i + "\t"); } System.out.println(); } } public static List<List<Integer>> bfs(TreeNode root) { LinkedList<List<Integer>> result = new LinkedList<>(); if (root == null) { return result; } Queue<TreeNode> queue = new LinkedList<>(); queue.add(root); while (! queue.isEmpty()) { int size = queue.size(); List<Integer> subset = new ArrayList<>(); while (size > 0) { TreeNode cur = queue.poll(); subset.add(cur.val); if (cur.left ! = null) { queue.add(cur.left); } if (cur.right ! = null) { queue.add(cur.right); } size--; } result.addFirst(new ArrayList<>(subset)); } return result; }}Copy the code