directory
1. There is a manipulation of data
2. The tree structure
3. Create a tree node class
4. Java implements the LinkedList tree with array data
Output the contents of the node and use this for both recursion and non-recursion
The recursive technique
Flying recursion technique
Breadth first, depth first
6. Call
7. Log:
advantages
1. There is a manipulation of data
String[] datas = new String[] { "A", "B", "D", "E", "F", "G", "H", "I", "J" };
Copy the codeor
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 codeor
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 codeBreadth 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 codeor
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.
ok
Continuously updated