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

The main content of this article is to explain "what is the traversal method of binary tree in Java", interested friends may wish to have a look. The method introduced in this paper is simple, fast and practical. Next let the editor to take you to learn "Java to achieve binary tree traversal method is what" it!

Traversing binary tree

Traversing or traveling, traversal. Systematically access the nodes in the data structure, and each node is accessed exactly once.

Depth-first traversal of binary tree

Three recursive definitions of depth-first traversal:

Preorder method (tLR order, preorder traversal): access the root node, traverse the left subtree in the preorder, and traverse the right subtree in the preorder.

Middle order (LtR order, inorder traversal): traversing the left subtree in the middle order; accessing the root node; traversing the right subtree in the middle order.

Post-order method (LRt order, postorder traversal): traversing the left subtree in post-order; traversing the right sub-tree in post-order; accessing the root node.

Recursive pre-order, middle-order and post-order public static List preOrderTraverseByRecursion (BinaryTreeNode root, List list) {if (root! = null) {list.add (root.getKey ()); / / preorder access node preOrderTraverseByRecursion (root.getLeft (), list); / / list.add (root.getKey ()); / / medium-order access node preOrderTraverseByRecursion (root.getRight (), list) / / list.add (root.getKey ()); / / access nodes by sequential method} return list;} non-recursive traversal

Recursive algorithm is very simple, recommended to use, the current compilation system optimization efficiency is very good. In special cases, stack is used to simulate recursion, and the backtracking characteristic of depth-first traversal is consistent with the working principle of stack, and some application environment resource constraints are not suitable for recursion.

Non-recursive preorder traversal

Realize

/ * * Preorder traversal (non-recursive) * avoid recursion (with nodes entering the stack) * * @ param root * / public static List preOrderTraverseByNonRecursion (BinaryTreeNode root) {List list = new ArrayList (); / / used to store the traversed result Stack stack = new Stack (); / / used to store the right subtree node BinaryTreeNode p = root / / when both the left and right subtrees are not traversed, traverse while (p! = null | | stack.size () > 0) {if (p! = null) {/ / traverse the left subtree list.add (p.getKey ()) when the left subtree is not empty; / / output stack.push (p.getRight ()) from the current node / / the right subtree goes into the stack and traverses the right subtree p = p.getLeft () after traversing the left subtree; / / traversing the left subtree} else {/ / after traversing the left subtree, traverse the right subtree p = stack.pop ();}} return list;} non-recursive mid-order traversal

Realize

/ * * Central order traversal (non-recursive) * * @ param root * / public static List inOrderTraverseByNonRecursion (BinaryTreeNode root) {List list = new ArrayList (); Stack stack = new Stack (); BinaryTreeNode current = root / / traverse the left subtree of the node and put the root node on the stack until the left subtree is null, then go out the stack to get the node and traverse the left subtree of the right subtree of the node until it is null while (current! = null | |! stack.empty ()) {if (current! = null) {stack.push (current); current = current.getLeft ();} else {BinaryTreeNode top = stack.pop () List.add (top.getKey ()); current = top.getRight ();}} return list;} non-recursive post-order traversal

Realize

/ * * subsequent traversal (non-recursive) * * @ param root * / public static List postOrderTraverseByNonRecursion (BinaryTreeNode root) {Stack stack = new Stack (); List list = new ArrayList (); stack.push (root); BinaryTreeNode current; while (stack.isEmpty () = = false) {current = stack.pop (); if (current! = null) {list.add (current.getKey ()) Stack.push (current.getLeft ()); stack.push (current.getRight ());}} Collections.reverse (list); return list;} width first traversal binary tree

Starting from the 0 layer (root node) of the binary tree, traverse the layer from top to bottom; in the same layer, visit the nodes one by one in the order from left to right. The characteristic is that it traverses and visits first, which accords with the characteristics of the queue and is realized through the queue. The implementation is as follows:

/ * * sequence traversal (width first traversal) * is characterized by first in, first out, and conforms to the characteristics of the queue * * @ param root * @ return * / public static List layerOrderTraverse (BinaryTreeNode root) {List list = new ArrayList (); LinkedList queue = new LinkedList (); BinaryTreeNode current; queue.offer (root); while (! queue.isEmpty ()) {current = queue.poll () List.add (current.getKey ()); if (current.getLeft ()! = null) {queue.addLast (current.getLeft ());} if (current.getRight ()! = null) {queue.addLast (current.getRight ());}} return list;} construct a binary tree based on the traversal sequence

Let's start with a conclusion and explanation:

Only a first (middle, second) sequence can not construct a unique binary tree (reason: it is impossible to determine the left and right subtrees or root nodes)

Only the first (second) order sequence and the middle order sequence can construct a unique binary tree (reason: the first order sequence and the post order sequence can not construct the only binary tree)

A unique binary tree can be constructed by extending the first (last) order sequence.

It is impossible to construct a unique binary tree with extended middle order sequences.

Constructing binary tree by creating preorder sequence and intermediate order sequence

Achieve:

/ * * construct binary tree based on preorder sequence and intermediate order sequence (recursive implementation) *

* the first element of the preorder sequence is the root node of the tree. Find out the location k: * 1 of the root node from the middle order sequence. Determine the middle order sequence of the left and right subtree of the root node: the element before this position is the middle order sequence of the left subtree of the root node, and the element after this position is the middle order sequence of the right subtree of the root node. Determine the preorder sequence of the left subtree and the right subtree of the root node: the first element of the preorder sequence followed by the k element is the preorder sequence of the left subtree of the root node, and the preorder sequence of the right subtree of the root node is after the position of kryp1.

*

* perOrder [I] ~ param [j] is the preorder sequence of the subtree * inOrder [s] ~ inOrder [t] is the intermediate order sequence of the subtree * * @ param perOrder * @ param inOrder * @ param j * @ param s * @ param t * @ return * / public static BinaryTreeNode buildTreeByPerOrderAndInOrder (Integer [] perOrder, Integer [] inOrder, int I, int j, int s Int t) {if (I > j) {return null } BinaryTreeNode root = new BinaryTreeNode (perOrder [I]); int k; k = s; while (kt) {return null;} root.setLeft (buildTreeByPerOrderAndInOrder (perOrder, inOrder, I + 1, j + k-s, s, k-1)); root.setRight (buildTreeByPerOrderAndInOrder (perOrder, inOrder, I + k-s + 1, j, k + 1, t)); return root } construct binary tree by creating post-order sequence and middle-order sequence

There are three ways to combine the left subtree and the right subtree of a node, the left subtree is null, the right subtree is null, and the left and right subtrees are not null. When using the recursive idea, the post-order sequence and middle order sequence of the left and right subtrees are analyzed according to these three cases. The implementation is as follows:

/ * * construct a binary tree based on the post-order sequence and intermediate order sequence (recursive implementation) * * postOrder [I] ~ postOrder [j] is the post-order sequence of the subtree * inOrder [s] ~ inOrder [t] is the intermediate order sequence of the subtree * * @ param postOrder * @ param inOrder * @ param I * @ param j * @ param s * @ param T * @ return * / public static BinaryTreeNode buildTreeByPostOrderAndInOrder (Integer [] postOrder Integer [] inOrder, int I, int j, int s, int t) {if (I > j) {return null } BinaryTreeNode root = new BinaryTreeNode (postOrder [j]); int k; k = s; while (kt) {return null;} / / number of left subtrees int countLeft = k-s; / / number of right subtrees int countRight = t-k If (countLeft = = 0) {/ / the left subtree is null root.setRight (buildTreeByPostOrderAndInOrder (postOrder, inOrder, j-countRight, j-1, t-countRight + 1, t);} else if (countRight = = 0) {/ / the right subtree is null root.setLeft (postOrder, inOrder, j-countLeft, j-1, t-countLeft, t-countRight-1)) } else {/ / left and right subtrees are not null root.setLeft (buildTreeByPostOrderAndInOrder (postOrder, inOrder, I, I + countLeft-1, s, s + countLeft-1); root.setRight (buildTreeByPostOrderAndInOrder (postOrder, inOrder, j-1-countRight + 1, j-1, t-countRight + 1, t));} return root } at this point, I believe you have a deeper understanding of "what is the traversal method of Java binary tree". 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.