Overview
-
Ordinary binary tree, with left and right child nodes, as shown below
- For a leaf node, its left and right child nodes are empty, and some non-leaf nodes may have only one child node, and each node will occupy a space, which will waste the created space.
- Threaded binary tree, exploiting these spaces
Threaded Binary Tree
-
Threaded Binary Tree
- If the node's left child is empty, point to the node's predecessor
- If the node's right child is empty, point to the node's successor
-
Precursor and Successor:
- predecessor: the predecessor of a node
- successor: a node's successor
- A binary linked list of n nodes contains n+1 empty spaces
- According to the different traversal order (that is, the clues are different), the clue binary tree can be divided into: pre-order clue binary tree, in-order clue binary tree and post-order clue binary tree
- For example, thread the ordinary binary tree in the above figure, as shown in the following figure:
According to the result of preorder traversal, the predecessor node of 16 is 20, so the left child node of 16 points to 20, the successor node of 16 is 42, so the right child node of 16 points to 42, and so on
create
-
The basic idea:
- The in-order threading method is adopted, first threading the left subtree, then threading the current node, and finally threading the right subtree
- 1) Threaded left subtree
- 2) Process the predecessor node of the current node: determine whether the left child node of the current node is empty, if it is empty, point the left child node of the current node to the previous node
- 3) Process the successor node of the current node: determine whether the predecessor node of the current node is empty, if the previous node is not empty and the right child node of the previous node is empty, then point the right child node of the previous node to the current node
- 4) Let the predecessor node point to the current node
- 5) Threaded right subtree
- Note: Each recursion can only judge the left child node of the current node and the right child node of the predecessor node, because there is no way to know the next node of the current node, only the previous node
traverse
-
The basic idea:
- First find the clued node from the left subtree in a loop, and then from the found node, loop to find her clued right child node
- Finally, let the current node point to the successor node
- Note: Since we are an inorder threaded binary tree, the first node must be a leaf node of a left subtree
code show as below
data structure:
package Tree;
public class TreeNode {
private Integer val;//serial number
private TreeNode left;//left child
private TreeNode right;//right child
//leftType: 0 means the left subtree pointed to, if 1 means pointing to the predecessor node
private int leftType;
//rightType: 0 means it points to the right subtree, if 1 means it points to the successor node
private int rightType;
public TreeNode(int val){
this.val = val;
}
public Integer getVal() {
return val;
}
public void setVal(Integer val) {
this.val = val;
}
public TreeNode getLeft() {
return left;
}
public void setLeft(TreeNode left) {
this.left = left;
}
public TreeNode getRight() {
return right;
}
public void setRight(TreeNode right) {
this.right = right;
}
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;
}
@Override
public String toString() {
return "TreeNode{" +
"val=" + val +
'}';
}
}Specific algorithm:
package Tree;
public class ThreadedBinaryTree {
//The previous node of the current node
private static TreeNode pre = null;
//root node
private static TreeNode root;
private static final int IS_LEFT_CHILD = 0; //0 means that the left child of the current node points to the left subtree
private static final int IS_RIGHT_CHILD = 0; //0 means that the right child of the current node points to the right subtree
private static final int IS_PRE_NODE = 1; //1 means that the left child node of the current node points to the predecessor node
private static final int IS_AFTER_NODE = 1; //1 means that the right child of the current node points to the successor node
public static void setRoot(TreeNode root) {
ThreadedBinaryTree.root = root;
}
//Threaded traversal of binary tree
public static void threadedList(){
//set current node
TreeNode node = root;
if (node == null) return;
while (node != null){
//Find nodes with leftType == 1
while (node.getLeftType() == IS_LEFT_CHILD){
node = node.getLeft();
}
//print current node
System.out.println(node.getVal());
//If the right child node of the current node points to the successor node, it will be output consistently
while (node.getRightType() == IS_AFTER_NODE){
node = node.getRight();
System.out.println(node.getVal());
}
//replace this traversed node
node = node.getRight();
}
}
//A method for inorder threading of binary tree
public static void threadedNodes(TreeNode node){
if (node == null) return;
//1. Thread the left subtree first
threadedNodes(node.getLeft());
//2. Thread the current node
//2.1 Process the predecessor node of the current node
if (node.getLeft() == null){
//Modify the left child node of the current node to point to the predecessor node
node.setLeft(pre);
node.setLeftType(IS_PRE_NODE);
}
//2.2 Process the successor nodes of the current node
if (pre != null && pre.getRight() == null){
//Make the right child of the predecessor node point to the current node
pre.setRight(node);
pre.setRightType(IS_AFTER_NODE);
}
//After each node is processed, let the predecessor node of the next node point to the current node
pre = node;
//3. Threaded right subtree
threadedNodes(node.getRight());
}
public static void main(String[] args) {
TreeNode node1 = new TreeNode(1);
TreeNode node2 = new TreeNode(3);
TreeNode node3 = new TreeNode(6);
TreeNode node4 = new TreeNode(8);
TreeNode node5 = new TreeNode(10);
TreeNode node6 = new TreeNode(14);
node1.setLeft(node2);
node1.setRight(node3);
node2.setLeft(node4);
node2.setRight(node5);
node3.setLeft(node6);
setRoot(node1);
threadedNodes(node1);
// TreeNode right = node3.getRight();
// TreeNode preNode = node5.getLeft();
// TreeNode afterNode = node5.getRight();
// System.out.println(right);
// System.out.println(preNode);
// System.out.println(afterNode);
//
threadedList();
}
}Because the algorithm may not be clear if the number of words is used, it is recommended to go through the process by combining the code and pictures