PS: This article is a reprint of the article. It will be more readable to read the original text. There is a link to the original text at the end of the article
catalogue
1. Cued binary tree
1. Cued binary tree
Before introducing the clue binary tree, let's take a look at a case. I'll draw a binary tree first, as shown in Figure 1:
picture
If we traverse the binary tree in Figure 1, the result is: 425136. When we carefully observe the binary tree in Figure 1, we find that the left and right pointers of node 456 are not used, and the left pointers of node 3 are not used; If we want to use the left and right pointers of each node so that each node can point to its own front and back nodes, we use the threaded binary tree.
Basic introduction of cued binary tree;
(1) Precursor node: traverses the binary tree in the way of medium order traversal. The previous node of a node, such as node 5 in Figure 1, looks at the medium order traversal result in Figure 1: 4 2 5 1 3 6, the precursor node of node 5 is node 2, so the precursor node of node 5 is node 2; The premise that a node has a precursor node is that the left child node of the node is empty and the node has a previous node. For example, when the left child node of node 5 is empty and traversed in the middle order, node 5 has a previous node, while node 4 has no previous node, so there is no precursor node; Usually, the precursor node is the parent node of the node or the parent node of the parent node, and so on.
(2) Successor node: traverses the binary tree in the way of middle order traversal. The next node of a node, such as node 5 in Figure 1, looks at the middle order traversal result in Figure 1: node 4 2 5 1 3 6, node 5 is followed by node 1, so the successor node of node 5 is node 1; The premise that a node has a successor node is that the right child node of the node is empty and there is a node behind the node. For example, when the right child node of node 5 is empty and traversed in the middle order, node 5 has a subsequent node, while the right child node of node 6 is empty but there is no node behind it, so node 6 has no successor node; Usually, the successor node is the parent node of the node or the parent node of the parent node, and so on.
(3) The binary linked list of N nodes contains n+1 (formula 2n-(n-1)=n+1) empty finger needle fields; The null pointer field in the binary linked list is used to store pointers to the precursor and successor nodes of the node in a certain traversal order (this additional pointer is called "clue").
(4) This binary linked list with clues is called the clue linked list, and the corresponding binary tree is called the clue binary tree. According to the different properties of clues, the clue binary tree can be divided into pre order clue binary tree, middle order clue binary tree and post order clue binary tree.
OK, we add the pointer to the predecessor node and the pointer to the successor node to the binary tree in Figure 1, and then we get the middle order clue binary tree as shown in Figure 2 below;
picture
Note: the black arrow indicates the pointer to the predecessor node, and the orange arrow indicates the pointer to the successor node.
Well, now we use the code to implement a binary tree of middle order clues in Figure 2, and print out the successor nodes of 4 nodes, precursor nodes and successor nodes of 5 nodes, precursor nodes of 3 nodes and precursor nodes of 6 nodes to see if it is the same as that in Figure 2.
(1) Write a Node class Node:
public class Node {
private int no;
private Node left;
private Node right;
//If it is 0, it indicates the left subtree; If it is 1, it indicates the precursor node
private int leftType;
//If it is 0, it indicates the right subtree; If it is 1, it indicates the successor node
private int rightType;
public int getLeftType() {
return leftType;
}
public void setLeftType(int leftType) {
this.leftType = leftType;
}
public int getRightType() {
return rightType;
}
public void setRightType(int rightType) {
this.rightType = rightType;
}
public Node(int no) {
super(); this.no = no;
}
public Node getLeft() {
return left;
}
public void setLeft(Node left) {
this.left = left;
}
public Node getRight() {
return right;
}
public void setRight(Node right) {
this.right = right;
}
public int getNo() {
return no;
}
}
(2) Write a Test class for middle order cueing of binary tree:
public class Test {
private Node root;
static Node[] nodes;
//Creates a pointer to the predecessor node of the current node
private Node pre;
public static void main(String[] args) {
}
//Print the precursor node of the current node
private void printPreNode(Node node) {
if (node == null) {
System.out.println("This node is empty, so there is no precursor node");
} else {
if (node.getLeft() != null && node.getLeftType() == 1) {
Node left = node.getLeft();
System.out.println(node.getNo() + "The precursor nodes of the node are:" + left.getNo()
+ "node");
} else {
System.out.println("No precursor node");
}
}}
//Print the successor nodes of the current node
private void printPostNode(Node node) {
if (node == null) {
System.out.println("The node is empty, so there is no successor node");
} else {
if (node.getRight() != null && node.getRightType() == 1) {
Node right = node.getRight();
System.out.println(node.getNo() + "The successor nodes of the node are:" + right.getNo()
+ "node");
} else {
System.out.println("No successor nodes");
}
}}
private void threadedNodes() {
if (root != null) {
threadedNodes(root);
} else {
System.out.println("The root node is empty, so the binary tree cannot be cued");
}}
//Create a binary tree in Figure 1
private void createBinaryTree() {
nodes = new Node[6];
for (int i = 0; i < nodes.length; i++) {
nodes[i] = new Node(i + 1);
}
root = nodes[0];
root.setLeft(nodes[1]);// The left child node of the root node is 2
root.setRight(nodes[2]);// The right child node of the root node is 3
nodes[1].setLeft(nodes[3]);// The left child node of node 2 is 4
nodes[1].setRight(nodes[4]);// The right child node of node 2 is 5
nodes[2].setRight(nodes[5]);// The right child node of node 3 is 6}
//Middle order cueing of binary tree
private void threadedNodes(Node node) {
// No cueing
if (node == null) {
return;
}
// Cued left subtree
threadedNodes(node.getLeft());
//Cue current node
threadedCurrentNodes(node);
// Cued right subtree
threadedNodes(node.getRight());}
//Cue current node
private void threadedCurrentNodes(Node node) {
// Process the current left child node and set the current left child node as the precursor node (if pre is not empty)
if (node.getLeft() == null) {
node.setLeft(pre);
node.setLeftType(1);
}
// Subsequent node processing
if (pre != null && pre.getRight() == null) {
// Let the right child node of the predecessor node point to the current node
pre.setRight(node);
pre.setRightType(1);
}
pre = node;}
}
Find the successor node of 4 nodes, and the program call is as follows:
public static void main(String[] args) {
Test test = new Test(); //Create a binary tree in Figure 2 test.createBinaryTree(); //Middle order cueing of binary tree test.threadedNodes(); //Find successor nodes of 4 nodes test.printPostNode(nodes[3]);
}
Print the log of the following node, as shown in Figure 4:
picture
Find the precursor node and successor node of 5 nodes. The program call is as follows:
public static void main(String[] args) {
Test test = new Test(); //Create a binary tree in Figure 2 test.createBinaryTree(); //Middle order cueing of binary tree test.threadedNodes(); //Find the precursor node of 5 nodes test.printPreNode(nodes[4]); //Find successor nodes of 5 nodes test.printPostNode(nodes[4]);
}
Find the precursor node and successor node of 5 nodes. The log print is as follows:
picture
Find the precursor node of 3 nodes, and the program call is as follows:
public static void main(String[] args) {
Test test = new Test(); //Create a binary tree in Figure 2 test.createBinaryTree(); //Middle order cueing of binary tree test.threadedNodes(); //Find the precursor node of 3 nodes test.printPreNode(nodes[2]);
}
Find the precursor node of 3 nodes and print the log as follows:
picture
Find the precursor node of 6 nodes, and the program call is as follows:
public static void main(String[] args) {
Test test = new Test(); //Create a binary tree in Figure 2 test.createBinaryTree(); //Middle order cueing of binary tree test.threadedNodes(); //Find the precursor node of 6 nodes test.printPreNode(nodes[5]);
}
Find the precursor node of 6 nodes and print the log as follows:
picture