Shulou(Shulou.com)06/03 Report--

This article mainly explains "how to understand the difficulty of binary tree of Java data structure". The content of the explanation in this article is simple and clear, and it is easy to learn and understand. next, please follow the editor's train of thought to study and learn "how to understand the difficulty of binary tree of Java data structure".

What is a cue binary tree?

First of all, let's find out what a clue binary tree is.

Definition: a binary tree is "worn up" by changing all originally empty right (child) pointers to the node's successor in the middle sequence, and all originally empty left (child) pointers to the precursor of the node's mid-order sequence.

Take another look at why there is a clue to the binary tree?

As the name implies, the clue binary tree must be searched according to the clue, and the search speed must be faster.

The threaded binary tree can traverse the binary tree linearly, so it is faster than recursive traversal in the middle order. Using a threaded binary tree can also easily find the parent node of a node, which is more efficient than explicitly using the parent node pointer or stack. This is useful when the stack space is limited or when the stack that stores the parent node cannot be used (for finding the parent node through a depth-first search).

Is that all the clues? Of course not, we are all lazy, can wait to solve the problem, why will think of new ways. What we need to solve is:

In order to solve the problem that it is impossible to directly find the precursor and successor nodes of the node in a certain ergodic sequence.

But at the same time, it is difficult for the binary list to find the left and right children, that is, after building the clue binary tree, there will be a problem with the original traversal mode of the linked list.

Finally, take a look at the diagram of the binary tree.

In our book on the clue binary tree, basically there is the following picture:

You can see that the picture above is still a little confused. Let's take a look at the picture drawn by hand below me.

How to thread the binary tree

Ohh! Before that, I would like to mention to you that there are several ways to traverse binary trees.

Recursive definition of preorder traversal binary tree (root left and right)

Recursive definition of Middle order traversal binary Tree (left Root and right)

Recursive meaning of subsequent traversal of binary trees (left and right roots)

This blog mainly discusses the traversal of intermediate order.

The result of its mid-order traversal is ABCDE F GHI

Its mid-order clue binary tree traverses as follows

Draw the clue binary tree first.

The dotted arrow is a clue pointer, for all nodes with an empty left pointer: point the left pointer of the node to the previous node of the node in the mid-order traversal; for all nodes with the right pointer pointing to the null node, point the right pointer of the node to the next node of the node in the mid-order traversal. Except for the last end node.

Middle order graphical threaded binary tree

How to find the successor node of a number through the threaded binary tree

That is to say, a special two-way linked list is formed. taking F-> E as an example, F-> E does not arrive directly, but indirectly through F-> B-> D-> E.

We try to use Java to build a clue binary tree horn.

To be clear, I have never used Java to build a tree, not even a binary tree. If there is any error, please point out

Data node class

Package com.testtree;/** * @ author pier * / public class TreeNode {/ * data field * * / private int data; / * * left pointer * * / private TreeNode left; / * * whether the left child is a clue. The Boolean type is mainly used to determine whether the null is not sufficient for * / private boolean leftIsThread; / * * right pointer * / private TreeNode right. / * * whether the right child is a clue * * / private boolean rightIsThread; / * * determine the corresponding position of the pointer according to the data field * * / public TreeNode (int data) {this.data = data; this.left = false; this.right = null; this.rightIsThread = false;} public int getData () {return data } public void setData (int data) {this.data = data;} public TreeNode getLeft () {return left;} public void setLeft (TreeNode left) {this.left = left;} public boolean isLeftIsThread () {return leftIsThread;} public void setLeftIsThread (boolean leftIsThread) {this.leftIsThread = leftIsThread } public TreeNode getRight () {return right;} public void setRight (TreeNode right) {this.right = right;} public boolean isRightIsThread () {return rightIsThread;} public void setRightIsThread (boolean rightIsThread) {this.rightIsThread = rightIsThread } @ Override public boolean equals (Object obj) {if (obj instanceof TreeNode) {TreeNode temp = (TreeNode) obj; if (temp.getData () = = this.data) {return true;}} return false } @ Override public int hashCode () {return super.hashCode () + this.data;}}

Binary tree class

Package com.testtree;/*author:pier2021/10/12*/public class BiTree {/ * * Root node * * / private TreeNode root; / * * size * * / private int size; / * * Save precursor when threaded * * / private TreeNode pre = null; public BiTree () {this.root = null; this.size = 0; this.pre = null } public BiTree (int [] data) {this.pre = null; this.size = data.length; / / create a binary tree this.root = createTree (data, 1) } / * create binary tree * * / public TreeNode createTree (int [] data, int index) {if (index > data.length) {return null;} TreeNode node = new TreeNode (data [index-1]); TreeNode left = createTree (data, 2 * index); TreeNode right = createTree (data, 2 * index + 1) Node.setLeft (left); node.setRight (right); return node;} / * * order traversal * * / public void inList (TreeNode root) {if (root! = null) {inList (root.getLeft ()); System.out.print (root.getData () + ","); inList (root.getRight ()) }} public TreeNode getRoot () {return root;} public void setRoot (TreeNode root) {this.root = root;} public int getSize () {return size;} public void setSize (int size) {this.size = size } / * * threaded binary tree * * / public void inThread (TreeNode root) {if (root! = null) {/ / threaded left child inThread (root.getLeft ()) / / left child is empty if (null = = root.getLeft ()) {/ / set left child to clue root.setLeftIsThread (true); root.setLeft (pre) } / / right child is empty if (pre! = null & & null = = pre.getRight ()) {pre.setRightIsThread (true); pre.setRight (root);} pre = root; / / right child inThread (root.getRight ()) }} / * traversal clue binary tree in order * * / public void inThreadList (TreeNode root) {if (root! = null) {/ / if the left child is not a clue while (root! = null & &! root.isLeftIsThread ()) {root = root.getLeft () } do {/ / if the right child is a clue System.out.print (root.getData () + ","); if (root.isRightIsThread ()) {root = root.getRight () } / / have right child else {root = root.getRight (); while (root! = null & &! root.isLeftIsThread ()) {root = root.getLeft () } while (root! = null);}

Test class

Package com.testtree;/** * @ author pier * / public class Test {public static void main (String [] args) {/ / Don't ask me why the setting is so large. At the end, see my screenshot int [] arr = new int [10000]; for (int I = 0; I)

< arr.length; i++) { arr[i]=i+1; } //创建一颗二叉树 BiTree biTree = new BiTree(arr); //中序遍历二叉树 System.out.println("中序遍历结果如下:"); long start1 = System.currentTimeMillis(); biTree.inList(biTree.getRoot()); long end1 = System.currentTimeMillis(); System.out.println(); System.out.println("普通遍历时间为:"+(end1-start1)+"毫秒"); System.out.println("\n"); //中序遍历将二叉树线索化 biTree.inThread(biTree.getRoot()); System.out.println("线索二叉树中序遍历如下:"); long start2 = System.currentTimeMillis(); biTree.inThreadList(biTree.getRoot()); long end2 = System.currentTimeMillis(); System.out.println(); System.out.println("线索二叉树的遍历时间为:"+(end2-start2)+"毫秒"); }} 运行结果 当我使用1-10的时候效果截图

Thank you for reading, the above is the content of "how to understand the difficulty of Java data structure binary tree". After the study of this article, I believe you have a deeper understanding of how to understand the difficulty of Java data structure binary tree, and the specific use needs to be verified in practice. Here is, the editor will push for you more related knowledge points of the article, welcome to follow!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.