Java implementation create binary tree traversal binary tree recursion non-recursion middle first order traversal width first depth first up ~

1. There is a manipulation of data

	String[] datas = new String[] { "A", "B", "D", "E", "F", "G", "H", "I", "J" };
Copy the code

Int datas = new int[] {1,2,3,4,5,6,7,8,9};Copy the code

Once the data is ready, it puts the data in the Linklist

2. The implemented tree structure is the following

        A
     B    C
   D   E F  G
 H  I J  
Copy the code

1, 2, 3, 4, 5, 6, 7, 8, 9, 10Copy the code

That’s what it looks like up there

3. Create a tree node class

// 节点类
	class Node {
		String var;// 节点值
		Node left;// 左子节点
		Node right;// 右子节点

		public Node(String var) {
			this.var = var;
			this.left = null;
			this.right = null;
		}

		public void setLeft(Node left) {
			this.left = left;
		}

		public void setRight(Node right) {
			this.right = right;
		}

		public String getVar() {
			return var;
		}

		public void setVar(String var) {
			this.var = var;
		}

		public Node getLeft() {
			return left;
		}

		public Node getRight() {
			return right;
		}

	}
Copy the code

One of these things is the current node
A current left child node
A current right child node
Mainly to implement a tree and then two branches
Add a tree as the root node and two forks
It’s kind of like an iterative subpattern, where you iterate or while looking for subforks

4. Java implements the LinkedList tree with array data

/ * * * *@paramDatas * implements an array of binary tree node values *@paramNodelist * binary tree list */
	private void creatBinaryTree(String[] datas, List<Node> nodelist) {
		// Turn the array into a node node
		for (int nodeindex = 0; nodeindex < datas.length; nodeindex++) {// Add data to linkList
			Node node = new Node(datas[nodeindex]);
			nodelist.add(node);
		}
		// Set child nodes for all parent nodes
		for (int index = 0; index < nodelist.size() / 2 - 1; index++) {// Set the parent node
			// The left child is numbered 2*n and the right child is numbered 2*n+1
			// the parent node has 1 (2,3),2 (4,5),3 (6,7), and 4 (8,9)
			nodelist.get(index).setLeft(nodelist.get(index * 2 + 1));
			nodelist.get(index).setRight(nodelist.get(index * 2 + 2));
		}
		// Process the last parent node separately because it may not have a right child
		int index = nodelist.size() / 2 - 1;// If the last node is odd, it will be pure on the right child
		nodelist.get(index).setLeft(nodelist.get(index * 2 + 1)); // Set the left child node first
		if (nodelist.size() % 2= =1) { // If there is an odd number of nodes, the last parent node has the right child node
			nodelist.get(index).setRight(nodelist.get(index * 2 + 2)); }}Copy the code

The creation of this thing is to put the data from the array into the LinkedList
Linkedlist as a tree
implementation
1. Add nodes to the LinkedList
2. Put the left and right children of the data into the node (not the last one this time)
3. Put the last one into the node (this operation has the most one, because the most one has two crosses if it is odd, even one cross)

Output the contents of the node and use this for both recursion and non-recursion

Public void checkCurrentNode(node node){system.out.print (node.getVar()+" "); }Copy the code

Get the current content of the node out

The recursive technique

Public void preOrderTraversal(Node Node){if (Node == null) Return must be added to stop traversal when a leaf node is encountered; checkCurrentNode(node); preOrderTraversal(node.getLeft()); preOrderTraversal(node.getRight()); } public void inOrderTraversal(Node Node){if (Node == null)} inOrderTraversal(node.getLeft()); checkCurrentNode(node); inOrderTraversal(node.getRight()); } public void postOrderTraversal(Node Node){if (Node == null) return; postOrderTraversal(node.getLeft()); postOrderTraversal(node.getRight()); checkCurrentNode(node); }Copy the code

Do something about the output
Change the content of the recursion node before and after to realize the method of traversal before, after and after

Flying recursion technique

Public void preOrderTraversalbyLoop(node node){Stack< node > Stack = new Stack(); Node p = node; while(p! =null || ! stack.isEmpty()){ while(p! If (p = 0 and p = 0){// if (p = 0 and p = 0); stack.push(p); P = p.goetleft (); } if(! stack.isEmpty()){ p = stack.pop(); p = p.getRight(); }}} public void inOrderTraversalbyLoop(node node){Stack< node > Stack = new Stack(); Node p = node; while(p! =null || ! stack.isEmpty()){ while(p! =null){ stack.push(p); p = p.getLeft(); } if(! stack.isEmpty()){ p = stack.pop(); checkCurrentNode(p); p = p.getRight(); }}} public void postOrderTraversalbyLoop(node node){Stack< node > Stack = new Stack<>();  Node p = node,prev = node; while(p! =null || ! stack.isEmpty()){ while(p! =null){ stack.push(p); p = p.getLeft(); } if(! stack.isEmpty()){ Node temp = stack.peek().getRight(); if(temp == null||temp == prev){ p = stack.pop(); checkCurrentNode(p); prev = p; p = null; }else{ p = temp; }}}}Copy the code

Breadth first, depth first

* @param root */ public void BFS (Node root){if(root == null) return; LinkedList<Node> queue = new LinkedList<Node>(); queue.offer(root); While (queue.size() > 0){node node = queue.peek(); // Queue () {node node = queue.peek(); queue.poll(); // Fetch the first element and print system.out. print(node.var+" "); if(node.left ! = null){// If there are left children, queue. Offer (node.left); } if(node.right ! = null){// If there are right children, queue. Offer (node.right); Public void DFS (node node, list < list <Integer>>) rst,List<Integer> list){ if(node == null) return; if(node.left == null && node.right == null){ list.add(node.var); /* Create a new list to save to RST * * Create a new list to save to RST */ rst.add(new ArrayList<>(list)); list.remove(list.size()-1); } list.add(node.var); dfs(node.left,rst,list); dfs(node.right,rst,list); list.remove(list.size()-1); }Copy the code

[A, B, E, I], [A, B, E, J], [A, B, F], [A, D, G], [A, D, H]]

6. Call

public static void main(String[] args) { RCSTest tree = new RCSTest(); String[] datas = new String[]{"A","B","D","E","F","G","H","I","J"}; List<Node> nodelist = new LinkedList<>(); tree.creatBinaryTree(datas, nodelist); Node root = nodelist.get(0); System.out.println(" recursion first traversal: "); tree.preOrderTraversal(root); System.out.println(); System.out.println(" non-recursive sequential traversal: "); tree.preOrderTraversalbyLoop(root); System.out.println(); System.out.println(" recursively traversal: "); tree.inOrderTraversal(root); System.out.println(); System.out.println(" non-recursive traversal: "); tree.inOrderTraversalbyLoop(root); System.out.println(); Println ("); system.out.println ("); tree.postOrderTraversal(root); System.out.println(); System.out.println(" non-recursive traversal: "); tree.postOrderTraversalbyLoop(root); System.out.println(); System.out.println(" breadth-first traversal: "); tree.bfs(root); System.out.println(); System.out.println(" depth-first traversal: "); List<List<String>> rst = new ArrayList<>(); List<String> list = new ArrayList<>(); tree.dfs(root,rst,list); System.out.println(rst); }Copy the code

7. Log:

A B E I J F D G H: A B E I J F A G G H: A B E I J F A G G H: I E J B F A G G H: I E J B F A G G H I J E F B G H D A I J E F B G H D  [[A, B, E, I], [A, B, E, J], [A, B, F], [A, D, G], [A, D, H]]Copy the code

Recursive traversal: 1 2 4 8 9 5 3 6 7 Non-recursive traversal: 1 2 4 8 9 5 3 6 7 Recursive traversal: 8 4 9 2 5 1 6 3 7 Recursive traversal: 8 4 9 2 5 1 6 3 7 recursive traversal: 8 4 9 2 5 1 6 3 7 recursive traversal: 8 9 4 5 2 6 7 3 1 Non-recursive order traversal: 8 9 4 5 2 6 7 3 1 breadth-first traversal: 1 2 3 4 5 6 7 8 9 depth-first traversal: [[1, 2, 4, 8], [1, 2, 4, 9], [1, 2, 5], [1, 3, 6], [1, 3, 7]]Copy the code

Cache data as String int

advantages

Is binary tree, binary tree at the time of big data, compared with traditional sequence of specification performance is good, because he doesn’t need all the query can obtain information or changes, too, so it can reduce the data retrieval and operation so as to greatly improve efficiency, but little meaning of data is not very easy to open out, for example, has 20 million 32-bit string data, What are we going to do if we do the traditional retrieval one by one, we can figure out the consumption.

Continuously updated