Java implements pre -, middle - and post order threaded binary tree and traversal

1, Principle of cued binary tree

Introduced earlier Binary tree The article mentioned that the binary tree can use two storage structures: sequential storage and chain storage. When using chain storage, there will be a large number of empty finger needle fields. In order to make full use of these empty finger needle fields, a cued binary tree is extended to use these empty finger needle fields and improve the retrieval efficiency. In the figure above, the purple area is the empty finger fields that are not pointed to. From the perspective of storage space, these empty finger fields waste memory resources.

From another perspective, if you need to know the predecessor and successor nodes of node C, you need to traverse each time. Can you store the predecessor and successor nodes of node C in advance, so as to save the traversal operation and improve efficiency?

Based on the above analysis, we can make full use of the null pointer field in the binary list to store the pointers of the precursor and successor nodes of the node in a certain traversal mode.

This pointer to the precursor and successor becomes the clue, and the binary chain of the clue becomes the clue list, and the corresponding binary tree is called Threaded Binary Tree

• First, the binary tree shall be traversed in medium order (for those who do not understand the traversal of binary tree, please refer to the data structure: binary tree), and the pointer field with empty right pointer of all nodes shall be pointed to its subsequent nodes, as shown in the following figure: By traversing node D in the middle order, it is found that the right pointer of node D is Null, and the successor node of node D is B, so the right node of D points to node B (as shown in operation ① in the above figure), and the right pointer of node B is Null, so the right pointer points to node A (as shown in operation ② in the above figure), and so on. If the successor node to node f is Null, the right pointer of F points to Null.

• Next, point all pointers with null left pointer to its precursor node, as shown in the following figure: As shown in the figure above, the left pointer field of node D points to Null (operation ⑤), the precursor node of node E is A, the left pointer of node E points to node A, and so on, and the left node of node F points to node C.

• Through the above two steps, the clue of the whole binary tree is completed.

After cueing, it can be seen (the blue arrow indicates the precursor and the pink arrow indicates the successor) that the cued binary tree is equivalent. Therefore, the binary tree is converted into a special two-way linked list, which brings convenience to add, delete and find nodes and improves efficiency. The diagram after converting to a linked list is as follows: Cue needs to modify the structure of the node. The modified data structure is as follows:

class Node
{
private int num;
private Object data;	//Data domain
private Node left;		//Left pointer field
private Node right;		//Right pointer field

/**
* leftType == 0 Indicates that it points to the left subtree. If it is 1, it points to the precursor node
*/
private int leftType;

/**
* rightType == 0 Indicates that it points to the right subtree. If it is 1, it points to the successor node
*/
private int rightType;
}

3, Code implementation clue binary tree

• Node structure

class Node
{
private int num;
private Object data;
private Node left;
private Node right;

/**
* leftType == 0 Indicates that it points to the left subtree. If it is 1, it points to the precursor node
*/
private int leftType;

/**
* rightType == 0 Indicates that it points to the right subtree. If it is 1, it points to the successor node
*/
private int rightType;

public Node(int num, Object data)
{
this.num = num;
this.data = data;
}

/**
* Preorder traversal
*/
public void preOrder()
{
//Output parent node information first
System.out.println(this);
//Judge whether the left node of this node is empty
//If the left node is not null and the pointer type is not a precursor type
if (this.left != null && this.leftType != 1)
{
//Left preorder traversal
this.left.preOrder();
}
//Judge whether the right node of this node is empty
//If the right node is not null and the pointer type is not a successor type
if (this.right != null && this.rightType != 1)
{
//Forward right traversal
this.right.preOrder();
}
}

/**
* Middle order traversal cued binary tree
*/
public void infixOrder()
{
//Judge whether the left node of this node is empty
if (this.left != null && this.leftType != 1)
{
//Left middle order traversal
this.left.infixOrder();
}
//Output parent node information
System.out.println(this);
//Judge whether the right node of this node is empty
if (this.right != null && this.rightType != 1)
{
//Right middle order traversal
this.right.infixOrder();
}
}

/**
* Postorder traversal
*/
public void postOrder()
{
//Judge whether the left node of this node is empty
if (this.left != null && this.leftType != 1)
{
//Left postorder traversal
this.left.postOrder();
}
//Judge whether the right node of this node is empty
if (this.right != null && this.rightType != 1)
{
//Right backward traversal
this.right.postOrder();
}
//Output parent node information
System.out.println(this);
}

//get set method omitted

@Override
public String toString()
{
return "Node{" +
"num=" + num +
", data=" + data +
'}';
}
}

/**
* Define ThreadedBinaryTree to realize the binary tree of cueing function
*/
{
/**
* Root node
*/
private Node root;

/**
* To achieve cueing, you need to create a pointer to the predecessor node of the current node
* When cueing recursively, pre always keeps the previous node
*/
private Node pre = null;

public void setRoot(Node root)
{
this.root = root;
}

public void createBinaryTree(ArrayList<Node> list)
{
this.createBinaryTree(list,0);
}

/**
* Create binary tree
* @param list Node list
* @param index Index for creating
* @return
*/
private Node createBinaryTree(ArrayList<Node> list, int index)
{
Node node = null;

if (isEmpty())
{
setRoot(list.get(0));
}

if (index < list.size())
{
node = list.get(index);
node.setLeft(createBinaryTree(list, (2*index+1)));
node.setRight(createBinaryTree(list, (2*index+2)));
}
return node;
}

public boolean isEmpty()
{
return root == null;
}

{
}

{
}

{
}

/**
* Preordered cued binary tree
* @param node Current nodes requiring cueing
*/
{
//Recursive backtracking condition
if (node == null)
{
return;
}

//Traverse to leaf node (the precursor pointer is not used)
if (node.getLeft() == null)
{
node.setLeft(pre);
node.setLeftType(1);
}

//pre.getLeft() != node must be indispensable
//Otherwise, after the first backtracking to the parent node, if this judgment is not added, the post drive pointer of the pre node will point to the parent node
//At this time, the predecessor and successor nodes of pre point to the parent node, which will inevitably lead to a life and death cycle and cannot end the recursion
if (pre != null && pre.getRight() == null && pre.getLeft() != node)
{
pre.setRight(node);
pre.setRightType(1);
}

pre = node;

if (node.getLeftType() == 0)
{
}

}

/**
* Medium order cued binary tree
* @param node Current nodes requiring cueing
*/
{
if (node == null)
{
return;
}
//1. Recursive cued left subtree

//2. Cue the current node
//Process the precursor node of the current node
if (node.getLeft() == null)
{
//Make the left pointer of the current node point to the predecessor node
node.setLeft(pre);
//Modify the type of the left pointer of the current node
node.setLeftType(1);
}
//Processing successor nodes
if (pre != null && pre.getRight() == null)
{
//Let the right pointer of the predecessor node point to the current node
pre.setRight(node);
//Modify the right pointer type of the precursor node
pre.setRightType(1);
}

//After each node is processed, make the current node the precursor of the next node
pre = node;

//3. Recursive cued right subtree
}

/**
* Post ordered cued binary tree
* @param node Current nodes requiring cueing
*/
{
if (node == null)
{
return;
}

if (node.getLeft() == null)
{
node.setLeft(pre);
node.setLeftType(1);
}

if ( pre!= null && pre.getRight() == null )
{
pre.setRight(node);
pre.setRightType(1);
}
pre = node;
}

/**
* A method of traversing cued binary tree in order in non recursive way
*/
{
Node node = root;
while (node != null)
{
//Loop to find node with leftType == 1
while (node.getLeftType() == 0)
{
node = node.getLeft();
}

System.out.println(node);

while (node.getRightType() == 1)
{
node = node.getRight();
System.out.println(node);
}

node = node.getRight();
}
}

{
if (root != null)
{
root.preOrder();
}else
{
System.out.println("Binary tree is empty,Unable to traverse");
}
}

{
if (root != null)
{
root.infixOrder();
}else
{
System.out.println("Binary tree is empty,Unable to traverse");
}
}

{
if (root != null)
{
root.postOrder();
}else
{
System.out.println("Binary tree is empty,Unable to traverse");
}
}
}

above.

If there are deficiencies or errors, please comment and correct.

It's not easy to tidy up. Leave it for three times before you go!

Keywords: data structure Binary tree

Added by bcarlson on Thu, 23 Dec 2021 19:51:09 +0200