# 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 code``

# Serialization/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.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;
}
}

public static String serialByPre(Node head) {
return "#_";
}
String res = head.value + "_";
return res;
}

public static Node reconByPreString(String preStr) {
String[] values = preStr.split("_");
for (int i = 0; i != values.length; i++) {
}
return reconPreOrder(queue);
}

public static Node reconPreOrder(Queue<String> queue) {
String value = queue.poll();
if (value.equals("#")) {
return null;
}
}

public static String serialByLevel(Node head) {
return "#!";
}
String res = head.value + "_";
while (!queue.isEmpty()) {
} else {
res += "#_";
}
} else {
res += "#_";
}
}
return res;
}

public static Node reconByLevelString(String levelStr) {
String[] values = levelStr.split("_");
int index = 0;
}
Node node = null;
while (!queue.isEmpty()) {
node = queue.poll();
node.left = generateNodeByString(values[index++]);
node.right = generateNodeByString(values[index++]);
if (node.left != null) {
}
if (node.right != null) {
}
}
}

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:");
System.out.println();
}

public static void printInOrder(Node head, int height, String to, int len) {
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) {

System.out.println("serialize tree by pre-order: " + pre);
System.out.print("reconstruct tree by pre-order, ");

System.out.println("serialize tree by level: " + level);
System.out.print("reconstruct tree by level, ");

System.out.println("====================================");

System.out.println("serialize tree by pre-order: " + pre);
System.out.print("reconstruct tree by pre-order, ");

System.out.println("serialize tree by level: " + level);
System.out.print("reconstruct tree by level, ");

System.out.println("====================================");

System.out.println("serialize tree by pre-order: " + pre);
System.out.print("reconstruct tree by pre-order, ");

System.out.println("serialize tree by level: " + level);
System.out.print("reconstruct tree by level, ");

System.out.println("====================================");

System.out.println("serialize tree by pre-order: " + pre);
System.out.print("reconstruct tree by pre-order, ");

System.out.println("serialize tree by level: " + level);
System.out.print("reconstruct tree by level, ");

System.out.println("====================================");

}
}
Copy the code``````

# Origami problem

## 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 code``

# The 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;

# ​

### 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``