“This is the 19th day of my participation in the Gwen Challenge in November. See details: The Last Gwen Challenge in 2021”.
This paper introduces the concept of clue binary tree and Java implementation of clue binary tree. If the binary tree is traversed frequently or some kind of traversal of the precursors and successors in the sequence is required to find nodes, the storage structure of the cued binary linked list is a good choice.
1 Overview of cueing binary tree
If you are not familiar with the concept of binary trees, you can read this article: introduction to binary trees and Java implementation case study. The concept of binary trees will not be described here.
For a binary list with n nodes, each node has two reference fields pointing to the left and right children, so there are 2n reference fields. However, the binary tree with n nodes has a total of N-1 branch lines, that is to say, there are 2n-(n-1)=n+1 empty reference fields. These Spaces don’t store anything, wasting memory resources.
The diagram below:
The traversal of binary tree is essentially to transform a complex nonlinear structure into a linear structure, so that each node has a unique precursor and successor (the first node has no precursor and the last node has no successor). For a node in a binary tree, it is convenient to find its left and right children, and its precursor and successor can only be obtained in traversal. To make it easy to find a precursor and successor, there are two ways. One is to add forward and backward references to the node structure, which increases the storage overhead and is not desirable. The other is to use empty chain reference of binary tree.
We can consider using those empty addresses to store the addresses of the precursor and successor nodes that point to the node in some traversal order, with empty left to store the precursor and empty right to store the successor. A Threaded Binary Tree is a Threaded Binary Tree. A Threaded Binary Tree is a Threaded Binary Tree.
The process of turning a binary tree into a cued binary tree by traversing it in a certain way (such as pre-order, mid-order, post-order or hierarchical order) is called cueing binary tree. According to the different nature of cue, the binary tree of cue can be divided into three kinds: the binary tree of preorder cue, the binary tree of middle order cue and the binary tree of postorder cue.
The data structure after cueing by middle-order traversal is as follows:
As you can see, it takes full advantage of the empty reference field (which equals space savings) and ensures that a single traversal at creation time can be used for life (which means time savings). Therefore, in practical problems, if the binary tree used needs to be traversed frequently or some kind of traversal sequence of the precursor and successor is needed when looking for nodes, then the storage structure of the cued binary linked list is a very good choice.
2 Node Design
The clue in the binary tree can record the precursor and successor information of each node. To distinguish cue references from child references, two flags, LTAG and Rtag, are set in each node.
When tag and Rtag are 0, left and right refer to the left and right child Pointers respectively. Otherwise, left is the cue leading to the node (pre) and right is the cue leading to the node (SUC). Since flags occupy only one binary bit, the storage space required by each node is greatly reduced.
The node structure of binary tree is redefined as follows:
| left | ltag | data | rtag | right |
Where: when ltag=0, left refers to the left son; When ltag=1, left points to the precursor. If rtag=0, right points to the right son; Rtag =1 right refers to the successor.
3. Construction of binary tree of middle order clue
Is to provide the complete Java code for the construction of the binary tree of the order, the construction of the binary tree of the order, the following clue and the construction of the order are basically the same, are improved on the basis of the method of the first, middle, after the order traversal, if you do not understand the four kinds of traversal on the binary tree, you can see this article: Binary tree traversal of the four ways in detail and Java code complete demonstration.
public class ThreadedBinaryTree<E> {
/** * Externally holds a reference to the root node */
private BinaryTreeNode<E> root;
/** * Saves the precursor node */ that was just visited when the cue is initialized
private BinaryTreeNode<E> pre;
/** * The number of nodes in the tree */
private int size;
/** * Internal node object **@param<E> Data type */
public static class BinaryTreeNode<E> {
/ / data domain
E data;
// Left child node/precursor
BinaryTreeNode<E> left;
// Right child node/successor
BinaryTreeNode<E> right;
boolean ltag; // False: indicates the left child node, true: indicates the precursor clue
boolean rtag; //false: pointing to the right child node, true: subsequent clue
public BinaryTreeNode(E data) {
this.data = data;
}
@Override
public String toString(a) {
returndata.toString(); }}/** * empty constructor */
public ThreadedBinaryTree(a) {}/** * constructor to initialize the root node **@paramRoot Root node data */
public ThreadedBinaryTree(E root) {
checkNullData(root);
this.root = new BinaryTreeNode<>(root);
size++;
}
/** * Add child node **@paramParent A reference to the parent node@paramData Node data *@paramLeft is the left child node. False no * /
public BinaryTreeNode<E> addChild(BinaryTreeNode<E> parent, E data, boolean left) {
checkNullParent(parent);
checkNullData(data);
BinaryTreeNode<E> node = new BinaryTreeNode<>(data);
if (left) {
if(parent.left ! =null) {
throw new IllegalStateException("The parent node already has a left child, adding failed");
}
parent.left = node;
} else {
if(parent.right ! =null) {
throw new IllegalStateException("The parent node already has a right child, adding failed");
}
parent.right = node;
}
size++;
return node;
}
/** * is an empty tree **@returnIs true; False no * /
public boolean isEmpty(a) {
return size == 0;
}
/** * returns the number of nodes **@returnNode number * /
public int size(a) {
return size;
}
/** * get the root node **@returnThe root node. Or null-- an empty tree */
public BinaryTreeNode<E> getRoot(a) {
return root;
}
/** * gets the left child node **@paramParent Parent node reference *@returnLeft child or NULL -- there is no left child */
public BinaryTreeNode<E> getLeft(BinaryTreeNode<E> parent) {
return parent == null ? null : parent.left;
}
/** * get the right child node **@paramParent Parent node reference *@returnRight child or NULL -- there is no right child */
public BinaryTreeNode<E> getRight(BinaryTreeNode<E> parent) {
return parent == null ? null : parent.right;
}
/** * data is null **@paramData Indicates the added data */
private void checkNullData(E data) {
if (data == null) {
throw new NullPointerException("Data cannot be null"); }}/** * Check whether the parent node is null **@paramParent Parent node references */
private void checkNullParent(BinaryTreeNode<E> parent) {
if (parent == null) {
throw new NoSuchElementException("The parent node cannot be null"); }}/** * will use root as the root node of the binary tree cue in order **@returnTrue Cueing success; False Cue failure */
public boolean inThread(a) {
if (isEmpty()) {
return false;
}
inThread(getRoot());
return true;
}
/** * will use root as the root node of the binary tree cue in order **@paramRoot node, starting from the root node */
private void inThread(BinaryTreeNode<E> root) {
BinaryTreeNode<E> left = getLeft(root);
if(left ! =null) {
// If the left child node is not null, the left child node is recursively traversed
inThread(left);
}
/* There are more steps */ in the middle of the sequence traversal
else {
// If the left child is null because its predecessor was just visited, set the left child as a clue
// Complete the cue of the precursor
root.ltag = true;
root.left = pre;
}
// If the precursor has no right child, the current node is treated as the successor of the precursor node
if(pre ! =null && null == pre.right) {
pre.rtag = true;
pre.right = root;
}
// Each time you set the current node to pre, the next node treats that node as a precursor
pre = root;
BinaryTreeNode<E> right = getRight(root);
if(right ! =null) {
// If the right child node is not null, continue recursively through the right child nodeinThread(right); }}/** * middle order traversal clue binary tree */
public void inThreadList(BinaryTreeNode<E> root) {
if (root == null) {
return;
}
// Find the start node of the sequence traversal
while(root ! =null && !root.ltag) {
root = root.left;
}
while(root ! =null) {
System.out.print(root.data + ",");
// If the right child node is a clue
if (root.rtag) {
root = root.right;
} else {
// There are right child nodes, iterate over right child nodes
root = root.right;
// If the right child is not null and the left child of the right child exists
while(root ! =null && !root.ltag) {
root = root.left;
}
}
}
}
}
Copy the code3.1 test
public class ThreadTreeTest {
/** * build binary tree, add root node r */
ThreadedBinaryTree<String> integerThreadedBinaryTree = new ThreadedBinaryTree<>("r");
/** * Build binary tree */
@Before
public void buildTree(a) {
/* Build a binary tree */
ThreadedBinaryTree.BinaryTreeNode<String> r = integerThreadedBinaryTree.getRoot();
// add the left child of r to a
ThreadedBinaryTree.BinaryTreeNode<String> a = integerThreadedBinaryTree.addChild(r, "a".true);
// add the right child b of the root node r
ThreadedBinaryTree.BinaryTreeNode<String> b = integerThreadedBinaryTree.addChild(r, "b".false);
// Add the left child of node A to c
ThreadedBinaryTree.BinaryTreeNode<String> c = integerThreadedBinaryTree.addChild(a, "c".true);
// add the right child of node A to d
ThreadedBinaryTree.BinaryTreeNode<String> d = integerThreadedBinaryTree.addChild(a, "d".false);
// Add e to the left child of node B
ThreadedBinaryTree.BinaryTreeNode<String> e = integerThreadedBinaryTree.addChild(b, "e".true);
// add the right child f of node b
ThreadedBinaryTree.BinaryTreeNode<String> f = integerThreadedBinaryTree.addChild(b, "f".false);
// add the left child of c to g
ThreadedBinaryTree.BinaryTreeNode<String> g = integerThreadedBinaryTree.addChild(c, "g".true);
// Add h to the right child of c
ThreadedBinaryTree.BinaryTreeNode<String> h = integerThreadedBinaryTree.addChild(c, "h".false);
// add left child I of d
ThreadedBinaryTree.BinaryTreeNode<String> i = integerThreadedBinaryTree.addChild(d, "i".true);
// add the left child j of f
ThreadedBinaryTree.BinaryTreeNode<String> j = integerThreadedBinaryTree.addChild(f, "j".true);
}
/** * middle-order clue binary tree */
@Test
public void test2(a) {
/ / the clues
System.out.println(integerThreadedBinaryTree.inThread());
// After the cue, the traversal is more efficient
integerThreadedBinaryTree.inThreadList(integerThreadedBinaryTree.getRoot());
//g c h a i d r e b j f}}Copy the codeIf you don’t understand or need to communicate, you can leave a message. In addition, I hope to like, collect, pay attention to, I will continue to update a variety of Java learning blog!