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

This article mainly explains "what are the ways of traversing Java binary trees". Interested friends may wish to have a look. The method introduced in this paper is simple, fast and practical. Next, let the editor take you to learn "what are the traversing ways of Java binary trees?"

There are four ways to traverse a binary tree:

Traversing binary tree of binary tree means that starting from the root node, all the nodes in the binary tree are accessed in a certain order, so that each node is visited sequentially and only once.

The four traversal methods are: pre-order traversal, mid-order traversal, post-order traversal, sequence traversal.

Before traversing, let's first introduce how to create a binary tree. Here, we use the method of building a left tree before building a right tree.

First, declare the node TreeNode class, with the following code:

Public class TreeNode {public int data; public TreeNode leftChild; public TreeNode rightChild; public TreeNode (int data) {this.data = data;}}

Let's create a binary tree:

/ * build binary tree * @ param list input sequence * @ return * / public static TreeNode createBinaryTree (LinkedList list) {TreeNode node = null; if (list = = null | | list.isEmpty ()) {return null;} Integer data = list.removeFirst (); if (datatrees null) {node = new TreeNode (data) Node.leftChild = createBinaryTree (list); node.rightChild = createBinaryTree (list);} return node;}

Then we will explain them one by one in the order listed above.

First of all, let's look at the preorder traversal. The so-called preorder traversal is to visit the root node first, then the left node, and finally the right node.

As shown in the figure above, the result of the preorder traversal is:

ABDFECGHI

The implementation code is as follows:

/ * * binary tree preorder traversal root-> left-> right * @ param node binary tree node * / public static void preOrderTraveral (TreeNode node) {if (node = = null) {return;} System.out.print (node.data+ "); preOrderTraveral (node.leftChild); preOrderTraveral (node.rightChild);}

The so-called mid-order traversal is to visit the left node, then the root node, and finally the right node.

As shown in the figure above, the result of traversal in the middle order is:

DBEFAGHCI

The implementation code is as follows:

/ * binary tree order traversal left-> root-> right * @ param node binary tree node * / public static void inOrderTraveral (TreeNode node) {if (node = = null) {return;} inOrderTraveral (node.leftChild); System.out.print (node.data+ "); inOrderTraveral (node.rightChild);}

Finally, there is post-order traversal, the so-called post-order traversal is to visit the left node first, then the right node, and finally the root node.

As shown in the above figure, the post-order traversal result is as follows:

DEFBHGICA

The implementation code is as follows:

/ * binary tree post-order traversal left-> right-> root * @ param node binary tree node * / public static void postOrderTraveral (TreeNode node) {if (node = = null) {return;} postOrderTraveral (node.leftChild); postOrderTraveral (node.rightChild); System.out.print (node.data+ "");}

After talking about the above three recursive methods, let's talk about how non-recursion traverses the front, middle and back order.

Again, first look at the non-recursive preorder traversal

1. First apply for a new stack and write it down as stack

two。 Declare a node treeNode to point to the node node

3. If treeNode is not empty, print the value of treeNode, put treeNode on the stack, and then point treeNode to the right node of treeNode

4. Repeat step 3 until treenode is empty

5. Then push out the stack and let treeNode point to the right child of treeNode.

6. Repeat step 3 until stack is empty.

The implementation code is as follows:

Public static void preOrderTraveralWithStack (TreeNode node) {Stack stack = new Stack (); TreeNode treeNode = node; while (treeNodecodes null | |! stack.isEmpty ()) {/ / iterate to visit the left child of the node and stack while (treeNodewritten nodes null) {System.out.print (treeNode.data+ ""); stack.push (treeNode) TreeNode = treeNode.leftChild;} / / if the node has no left child, pop up the top node and visit the right child of the node if (! stack.isEmpty ()) {treeNode = stack.pop (); treeNode = treeNode.rightChild;}

Traversal in the middle order is non-recursive, so there are no more specific steps here.

Specific process:

1. Apply for a new stack, mark it as stack, and apply for a variable cur. The initial treeNode is the header node.

two。 First push the treeNode node into the stack, for the whole subtree headed by the treeNode node, press the left subtree of the whole tree into the stack in turn, that is, keep treeNode=treeNode.leftChild, and then repeat step 2

3. Repeat step 2 until you find that cur is empty, pop up a node marked treeNode from stack, print the value of node, and let treeNode= treeNode.right, and then repeat step 2

4. Ends when stack is empty and cur is empty.

Public static void inOrderTraveralWithStack (TreeNode node) {Stack stack = new Stack (); TreeNode treeNode = node; while (treeNodecodes null | |! stack.isEmpty ()) {while (treeNodecodes null) {stack.push (treeNode); treeNode = treeNode.leftChild;} if (! stack.isEmpty ()) {treeNode = stack.pop () System.out.print (treeNode.data+ ""); treeNode = treeNode.rightChild;}}

The post-order traverses the non-recursive implementation, and the post-order traversal here is a little more complex than the first two implementations. We need a tag bit to remember a node on our node at this time. Look at the code comments.

Public static void postOrderTraveralWithStack (TreeNode node) {Stack stack = new Stack (); TreeNode treeNode = node; TreeNode lastVisit = null; / / Mark the last visited node while (treeNodeprinted null | |! stack.isEmpty ()) {/ / node is not empty, the node goes into the stack and points to the next left child while (treeNodeprinted null) {stack.push (treeNode). TreeNode = treeNode.leftChild;} / / stack is not empty if (! stack.isEmpty ()) {/ / out stack treeNode = stack.pop () / * this is to determine whether treeNode has a right child. * if there is no treeNode.data output, let lastVisit point to treeNode, and let treeNode be empty * if there is a right child, continue to put the current node into the stack. TreeNode points to its right child and continues to repeat the cycle * / if (treeNode.rightChild = = null | | treeNode.rightChild = = lastVisit) {System.out.print (treeNode.data + "") LastVisit = treeNode; treeNode = null;} else {stack.push (treeNode); treeNode = treeNode.rightChild;}}

Finally, I would like to introduce you to sequence traversal.

The specific steps are as follows:

1. First apply for a new queue, marked as queue

two。 Press the header node head into the queue

3. Every time you leave the team from queue, mark it as node, and then print the node. if the left child of node is not empty, the left child will join the team; if the right child of node is not empty, the right child will join the team.

4. Repeat step 3 until queue is empty.

The implementation code is as follows:

Public static void levelOrder (TreeNode root) {LinkedList queue = new LinkedList (); queue.add (root); while (! queue.isEmpty ()) {root = queue.pop (); System.out.print (root.data+ ""); if (root.leftChildchild null) queue.add (root.leftChild); if (root.rightChildchild null) queue.add (root.rightChild) }} at this point, I believe you have a deeper understanding of "what is the way of traversing Java binary trees". You might as well do it in practice. Here is the website, more related content can enter the relevant channels to inquire, follow us, continue to learn!

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.