Niu Guest network left cheng Yun teacher’s algorithm introduction class
Find the successors of the nodes in the binary tree
The principle of
- If a node has a right subtree, the successor node is the first leftmost node of the right subtree
- If the node has no right child tree, if the node is the right child of the parent, keep looking up until you find a parent that is the parent of the node along the path, and the node along the path is its left child
Topic request
The new binary tree type is as follows
public class Node{ public int value; public Node left; public Node right; public Node parent; public Node(int val){ value = val; }}Copy the code- There is a parent pointer to the parent node compared to a traditional binary tree node
- The parent of the head node points to null
- A node with only one binary tree node, implement a successor function that returns the node. In a binary tree, the next node of a node is called its successor. Write a program to do this:
code
package class05; public class Code08_SuccessorNode { public static class Node { public int value; public Node left; public Node right; public Node parent; public Node(int data) { this.value = data; } } public static Node getSuccessorNode(Node node) { if (node == null) { return node; } if (node.right ! = null) { return getLeftMost(node.right); } else {// No right subtree Node parent = node.parent; while (parent ! = null && parent.left ! = node) {// The current node is its parent node's right child node = parent; parent = node.parent; } return parent; } } public static Node getLeftMost(Node node) { if (node == null) { return node; } while (node.left ! = null) { node = node.left; } return node; } public static void main(String[] args) { Node head = new Node(6); head.parent = null; head.left = new Node(3); head.left.parent = head; head.left.left = new Node(1); head.left.left.parent = head.left; head.left.left.right = new Node(2); head.left.left.right.parent = head.left.left; head.left.right = new Node(4); head.left.right.parent = head.left; head.left.right.right = new Node(5); head.left.right.right.parent = head.left.right; head.right = new Node(9); head.right.parent = head; head.right.left = new Node(8); head.right.left.parent = head.right; head.right.left.left = new Node(7); head.right.left.left.parent = head.right.left; head.right.right = new Node(10); head.right.right.parent = head.right; Node test = head.left.left; System.out.println(test.value + " next: " + getSuccessorNode(test).value); test = head.left.left.right; System.out.println(test.value + " next: " + getSuccessorNode(test).value); test = head.left; System.out.println(test.value + " next: " + getSuccessorNode(test).value); test = head.left.right; System.out.println(test.value + " next: " + getSuccessorNode(test).value); test = head.left.right.right; System.out.println(test.value + " next: " + getSuccessorNode(test).value); test = head; System.out.println(test.value + " next: " + getSuccessorNode(test).value); test = head.right.left.left; System.out.println(test.value + " next: " + getSuccessorNode(test).value); test = head.right.left; System.out.println(test.value + " next: " + getSuccessorNode(test).value); test = head.right; System.out.println(test.value + " next: " + getSuccessorNode(test).value); test = head.right.right; // 10's next is null System.out.println(test.value + " next: " + getSuccessorNode(test)); }}Copy the codeSerialization/deserialization of binary trees
- Use # to represent null
- For each output value, an _ is printed to isolate the elements
- The process from tree to string is called serialization, and the process from string to tree is deserialization
code
package class05;
import java.util.LinkedList;
import java.util.Queue;
public class Code09_SerializeAndReconstructTree {
public static class Node {
public int value;
public Node left;
public Node right;
public Node(int data) {
this.value = data;
}
}
// 以head为头的树，请序列化成字符串返回
public static String serialByPre(Node head) {
if (head == null) {
return "#_";
}
String res = head.value + "_";
res += serialByPre(head.left);
res += serialByPre(head.right);
return res;
}
public static Node reconByPreString(String preStr) {
String[] values = preStr.split("_");
Queue<String> queue = new LinkedList<String>();
for (int i = 0; i != values.length; i++) {
queue.add(values[i]);
}
return reconPreOrder(queue);
}
public static Node reconPreOrder(Queue<String> queue) {
String value = queue.poll();
if (value.equals("#")) {
return null;
}
Node head = new Node(Integer.valueOf(value));
head.left = reconPreOrder(queue);
head.right = reconPreOrder(queue);
return head;
}
public static String serialByLevel(Node head) {
if (head == null) {
return "#!";
}
String res = head.value + "_";
Queue<Node> queue = new LinkedList<Node>();
queue.add(head);
while (!queue.isEmpty()) {
head = queue.poll();
if (head.left != null) {
res += head.left.value + "_";
queue.add(head.left);
} else {
res += "#_";
}
if (head.right != null) {
res += head.right.value + "_";
queue.add(head.right);
} else {
res += "#_";
}
}
return res;
}
public static Node reconByLevelString(String levelStr) {
String[] values = levelStr.split("_");
int index = 0;
Node head = generateNodeByString(values[index++]);
Queue<Node> queue = new LinkedList<Node>();
if (head != null) {
queue.add(head);
}
Node node = null;
while (!queue.isEmpty()) {
node = queue.poll();
node.left = generateNodeByString(values[index++]);
node.right = generateNodeByString(values[index++]);
if (node.left != null) {
queue.add(node.left);
}
if (node.right != null) {
queue.add(node.right);
}
}
return head;
}
public static Node generateNodeByString(String val) {
if (val.equals("#")) {
return null;
}
return new Node(Integer.valueOf(val));
}
// for test -- print tree
public static void printTree(Node head) {
System.out.println("Binary Tree:");
printInOrder(head, 0, "H", 17);
System.out.println();
}
public static void printInOrder(Node head, int height, String to, int len) {
if (head == null) {
return;
}
printInOrder(head.right, height + 1, "v", len);
String val = to + head.value + to;
int lenM = val.length();
int lenL = (len - lenM) / 2;
int lenR = len - lenM - lenL;
val = getSpace(lenL) + val + getSpace(lenR);
System.out.println(getSpace(height * len) + val);
printInOrder(head.left, height + 1, "^", len);
}
public static String getSpace(int num) {
String space = " ";
StringBuffer buf = new StringBuffer("");
for (int i = 0; i < num; i++) {
buf.append(space);
}
return buf.toString();
}
public static void main(String[] args) {
Node head = null;
printTree(head);
String pre = serialByPre(head);
System.out.println("serialize tree by pre-order: " + pre);
head = reconByPreString(pre);
System.out.print("reconstruct tree by pre-order, ");
printTree(head);
String level = serialByLevel(head);
System.out.println("serialize tree by level: " + level);
head = reconByLevelString(level);
System.out.print("reconstruct tree by level, ");
printTree(head);
System.out.println("====================================");
head = new Node(1);
printTree(head);
pre = serialByPre(head);
System.out.println("serialize tree by pre-order: " + pre);
head = reconByPreString(pre);
System.out.print("reconstruct tree by pre-order, ");
printTree(head);
level = serialByLevel(head);
System.out.println("serialize tree by level: " + level);
head = reconByLevelString(level);
System.out.print("reconstruct tree by level, ");
printTree(head);
System.out.println("====================================");
head = new Node(1);
head.left = new Node(2);
head.right = new Node(3);
head.left.left = new Node(4);
head.right.right = new Node(5);
printTree(head);
pre = serialByPre(head);
System.out.println("serialize tree by pre-order: " + pre);
head = reconByPreString(pre);
System.out.print("reconstruct tree by pre-order, ");
printTree(head);
level = serialByLevel(head);
System.out.println("serialize tree by level: " + level);
head = reconByLevelString(level);
System.out.print("reconstruct tree by level, ");
printTree(head);
System.out.println("====================================");
head = new Node(100);
head.left = new Node(21);
head.left.left = new Node(37);
head.right = new Node(-42);
head.right.left = new Node(0);
head.right.right = new Node(666);
printTree(head);
pre = serialByPre(head);
System.out.println("serialize tree by pre-order: " + pre);
head = reconByPreString(pre);
System.out.print("reconstruct tree by pre-order, ");
printTree(head);
level = serialByLevel(head);
System.out.println("serialize tree by level: " + level);
head = reconByLevelString(level);
System.out.print("reconstruct tree by level, ");
printTree(head);
System.out.println("====================================");
}
}
Copy the codeHow can I tell if a subtree is a subtree of another binary tree
-
KMP algorithm
Origami problem
requirements
reference
code
package class05; public class Code10_PaperFolding { public static void printAllFolds(int N) { printProcess(1, N, true); } // I is the number of layers of the node, N is the total number of layers, Public static void printProcess(int I, int N, Boolean down) {if (I > N) {return; } printProcess(i + 1, N, true); System.out.println(down ? "Concave" : "convex "); printProcess(i + 1, N, false); } public static void main(String[] args) { int N = 3; printAllFolds(N); }}Copy the codeThe prefix tree
- It’s stored on the edge, not the node
- Node storage information :pass How many times the node is passed when the node is created. End: The end of how many strings the current node is
- Pass++ for nodes along the way; End++ for the end node;
example
Join node
- Add node AB so that p=3 after route A and p=2 and e=1 after route B;
- Add node BCS, so that after BC along the way, the node ++, such that P =2, e=2 of S;
Realize the function
- You can query the number of times ABC joins, and look at the value of e
- You can look up the number of times ab is prefixed by p
Remove nodes
- The p value of the nodes along the route is reduced by 1, and the p and E of the deleted nodes are reduced by 1. And memory is freed.
code
package class07; import java.util.HashSet; public class Code01_TrieTree { public static class TrieNode { public int pass; public int end; // HashMap<Char, Node> nexts; // TreeMap<Char, Node> nexts; public TrieNode[] nexts; public TrieNode() { pass = 0; end = 0; // nexts[0] == null No path to 'A' // nexts[0]! = null has a path to 'a' //... // nexts[25] ! = null nexts = new TrieNode[26]; } } public static class Trie { private TrieNode root; public Trie() { root = new TrieNode(); } public void insert(String word) { if (word == null) { return; } char[] chs = word.toCharArray(); TrieNode node = root; node.pass++; int index = 0; for (int i = 0; i < chs.length; I ++) {// traversal the character index = CHS [I] - 'a'; If (node.nexts[index] == null) {node.nexts[index] = new TrieNode(); } node = node.nexts[index]; node.pass++; } node.end++; } public void delete(String word) { if (search(word) ! Char [] CHS = word. ToCharArray (); char[] CHS = word. TrieNode node = root; node.pass--; int index = 0; for (int i = 0; i < chs.length; i++) { index = chs[i] - 'a'; If (--node.nexts[index].pass == 0) {// Java C++ to parse node.nexts[index] = null; / /... return; } node = node.nexts[index]; } node.end--; } } public void deleteCPP(String word) { if (search(word) ! Char [] CHS = word. ToCharArray (); char[] CHS = word. TrieNode node = root; node.pass--; int index = 0; TrieNode a = null; int deleteIndex = -1; HashSet<TrieNode> deleteSet = new HashSet<>(); for (int i = 0; i < chs.length; i++) { index = chs[i] - 'a'; if (--node.nexts[index].pass == 0) { a = a == null ? node : a; deleteIndex = deleteIndex == -1 ? index : deleteIndex; deleteSet.add(node.nexts[index]); } node = node.nexts[index]; } node.end--; a.nexts[deleteIndex] = null; // deleteSet ... Public int search(String word) {if (word == null) {return 0; } char[] chs = word.toCharArray(); TrieNode node = root; int index = 0; for (int i = 0; i < chs.length; i++) { index = chs[i] - 'a'; if (node.nexts[index] == null) { return 0; } node = node.nexts[index]; } return node.end; } public int prefixNumber(String pre) {if (pre == null) {return 0; } char[] chs = pre.toCharArray(); TrieNode node = root; int index = 0; for (int i = 0; i < chs.length; i++) { index = chs[i] - 'a'; if (node.nexts[index] == null) { return 0; } node = node.nexts[index]; } return node.pass; } } public static void main(String[] args) { Trie trie = new Trie(); System.out.println(trie.search("zuo")); trie.insert("zuo"); System.out.println(trie.search("zuo")); trie.delete("zuo"); System.out.println(trie.search("zuo")); trie.insert("zuo"); trie.insert("zuo"); trie.delete("zuo"); System.out.println(trie.search("zuo")); trie.delete("zuo"); System.out.println(trie.search("zuo")); trie.insert("zuoa"); trie.insert("zuoac"); trie.insert("zuoab"); trie.insert("zuoad"); trie.delete("zuoa"); System.out.println(trie.search("zuoa")); System.out.println(trie.prefixNumber("zuo")); }}Copy the code