Shulou(Shulou.com)05/31 Report--

This article introduces how to achieve python binary tree traversal analysis, the content is very detailed, interested friends can refer to, hope to be helpful to you.

/ * preorder traversal: according to the order of "root left and right", first traverse the root node, then traverse the left subtree, then traverse the right subtree * traversal in the order of "left root and right", first traverse the left subtree, then traverse the root node, finally traverse the right subtree * subsequent traversal: according to the order of "left and right roots", first traverse the left subtree, then traverse the right subtree, and finally traverse the root node *

* Note: * 1) the term "first / middle / last" here refers to the order in which the root nodes are traversed each time. * 2) each node can be regarded as a follower node. * 3) when traversing, we treat the current node as a root node. * / public class BinaryTree {Integer value;BinaryTree leftChild;BinaryTree rightChild;public BinaryTree (Integer value, BinaryTree leftChild, BinaryTree rightChild) {this.value = value; this.leftChild = leftChild; this.rightChild = rightChild;} / / stores the traversed node static ArrayList list = new ArrayList (); / * * pre-order traversal * / public static void preOrder (BinaryTree root) {if (root = = null) return; list.add (root); / / 1. Save the current node (root node) into list if (root.leftChild! = null) {/ / 2. If the left subtree of the current node is not empty, continue to look left for preOrder (root.leftChild);} / / 3. If the left subtree of the current node is empty, it means that the root node and the left child have been traversed, then traverse the right child if (root.rightChild! = null) {preOrder (root.rightChild);}} / * traversal in the middle order * / public static void inOrder (BinaryTree root) {if (root = = null) return; if (root.leftChild! = null) {inOrder (root.leftChild) } list.add (root); if (root.rightChild! = null) {inOrder (root.rightChild);}} / * * Post-order traversal * / public static void postOrder (BinaryTree root) {if (root = = null) return; if (root.leftChild! = null) {postOrder (root.leftChild);} if (root.rightChild! = null) {postOrder (root.rightChild) } list.add (root);} / * * preorder traversal non-recursive * * [@ param] (https://my.oschina.net/u/2303379) root * / public static void preOrderNonRecursion (BinaryTree root) {if (root = = null) return; Stack stack = new Stack (); BinaryTree currentNode = root While (! stack.empty () | | currentNode! = null) {while (currentNode! = null) {list.add (currentNode); stack.push (currentNode); / / 1. Store the current node (root node) in the stack currentNode = currentNode.leftChild; / / 2. When the left subtree of the current node is not empty, the loop continues with the left subtree of the current node as the root node. Note: this is similar to recursive preorder traversal. } / / 3. If the left subtree of the current node is empty, it means that the root node and the left child have been traversed, then traverse the right child if (! stack.empty ()) {currentNode = stack.pop (); currentNode = currentNode.rightChild Non-recursive * * [@ param] (https://my.oschina.net/u/2303379) root * / public static void inOrderNonRecursion (BinaryTree root) {if (root = = null) return; Stack stack = new Stack (); BinaryTree currentNode = root; while (! stack.empty () | | currentNode! = null) {while (currentNode! = null) {stack.push (currentNode)) CurrentNode = currentNode.leftChild;} / / when root is empty, the bottom of the left subtree has been reached, so you need to stack if (! stack.empty ()) {currentNode = stack.pop (); list.add (currentNode); currentNode = currentNode.rightChild Non-recursive * key points: * 1) Post-order traversal needs to determine whether the last visited node is located in the left subtree or the right subtree. * 2) if it is located in the left subtree, you need to skip the root node, enter the right subtree, and then go back to the root node; * 3) if it is located in the right subtree, access the root node directly. * * [@ param] (https://my.oschina.net/u/2303379) root * / public static void postOrderNonRecursion (BinaryTree root) {if (root = = null) return; Stack stack = new Stack (); BinaryTree currentNode = root; / / currently visited node BinaryTree lastVisitNode = null / / Last visited node / / move currentNode to the leftmost while (currentNode! = null) {stack.push (currentNode) of the left subtree of the current node; currentNode = currentNode.leftChild;} while (! stack.empty ()) {currentNode = stack.pop () / / in subsequent traversal, the premise that a root node is accessed is that the current node (which can be regarded as the root node) has no right subtree or the right subtree of the current node has just been visited. If (currentNode.rightChild! = null & & currentNode.rightChild! = lastVisitNode) {stack.push (currentNode); / / the right subtree of the current node is not empty and has not been accessed, so the root node (the current node) stacks again. / / enter the right subtree and move currentNode to the leftmost subtree of the current node's right subtree currentNode = currentNode.rightChild; while (currentNode! = null) {stack.push (currentNode); currentNode = currentNode.leftChild;}} else {/ / access list.add (currentNode); lastVisitNode = currentNode Returns the depth of the current number * 1. If a tree has only one node, its depth is 1 * 2. If the root node has only the left subtree but no right subtree, then the depth of the tree is the depth of the left subtree plus 1 * 3. If the root node has only the right subtree but no left subtree, then the depth of the tree should be the depth of the right subtree plus 1 * 4. If there are both right and left subtrees, the depth of the tree is the greater value of the depth of the left and right subtrees plus 1 * * [@ param] (https://my.oschina.net/u/2303379) root * [@ return] (https://my.oschina.net/u/556800) * / public static int getTreeDepth (BinaryTree root) {int left = 0, right = 0; if (root.leftChild = = null & & root.rightChild = = null) {return 1) } if (root.leftChild! = null) {left = getTreeDepth (root.leftChild);} if (root.rightChild! = null) {right = getTreeDepth (root.rightChild);} return left > right? Initialization of left + 1: right + 1;} / * tree: start from leaf node, from leaf to root * / public static BinaryTree getBinaryTree () {BinaryTree leaf1 = new BinaryTree (11, null, null); BinaryTree leaf2 = new BinaryTree (12, null, null); BinaryTree firstMidNode1 = new BinaryTree (21, leaf1, leaf2); BinaryTree leaf3 = new BinaryTree (13, null, null); BinaryTree leaf4 = new BinaryTree (14, null, null) BinaryTree firstMidNode2 = new BinaryTree (22, leaf3, leaf4); BinaryTree secondMidNode1 = new BinaryTree (31, firstMidNode1, firstMidNode2); BinaryTree leaf5 = new BinaryTree (32, null, null); BinaryTree root = new BinaryTree (41, secondMidNode1, leaf5); return root;} public static void main (String [] args) {BinaryTree root = getBinaryTree (); / preOrder (root); / / inOrder (root); / / postOrder (root); preOrderNonRecursion (root) / / inOrderNonRecursion (root); / / postOrderNonRecursion (root); ArrayList resultList = new ArrayList (); for (BinaryTree node: list) {resultList.add (node.value);} System.out.println ("result of traversal:" + resultList); System.out.println ("height of tree:" + getTreeDepth (root)) }} on how to achieve python binary tree traversal analysis is shared here, I hope the above content can be of some help to you, can learn more knowledge. If you think the article is good, you can share it for more people to see.

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.