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

This article mainly introduces "how to realize the three kinds of traversal of python N-tree". In the daily operation, I believe that many people have doubts about how to realize the three kinds of traversal of python N-tree. The editor consulted all kinds of materials and sorted out simple and easy-to-use operation methods. I hope it will be helpful for you to answer the doubt of "how to realize the three kinds of traversal of python N-tree". Next, please follow the editor to study!

1. Hierarchical traversal

"" # Definition for a Node.class Node: def _ _ init__ (self, val=None, children=None): self.val = val self.children = children "class Solution: def levelOrder (self Root: 'Node')-> list [list]: if not root: return [] queue = collections.deque () queue.append (root) res = [] while queue: size = len (queue) temp = [] for _ in range (size): node = queue.popleft () temp.append (node.val) if node.children: queue.extend (node.children) res.append (temp) return res2, Preorder traversal

The preorder traversal is from left to right, with the root before the child; recursion is relatively simple, and the iterative method requires the help of an auxiliary stack to push the children of each node into the stack.

"" # Definition for a Node.class Node: def _ init__ (self, val=None, children=None): self.val = val self.children = children "class Solution: def preorder (self, root: 'Node')-> List [int]: if not root: return [] # iterative method stack, output = [root,] [] while stack: root = stack.pop () output.append (root.val) stack.extend (root.children [::-1]) return output # Recursive res = [] def helper (root): if not root: Return res.append (root.val) for children in root.children: helper (children) helper (root) return res3, Post-order traversal

In the post-order traversal, we first traverse all the children of a node, and then traverse the node itself. For example, when the current node is u and its child nodes are v1, v2, v3, then the result of post-order traversal is [children of v1], v1, [children of v2], v2, [children of v3], v3, u, where [children of vk] represents the post-order traversal result of the subtree with vk as the root node (excluding vk itself). We reverse this result and we get u, v3, [children of v3]', v2, [children of v2]', v1, [children of v1]', where [a] 'represents the inversion of [a]. At this point, we find that the result is very similar to the preorder traversal, except that the traversal order of the child nodes in the preorder traversal is v1, v2, v3, and here is v3, v2, v1.

"" # Definition for a Node.class Node: def _ init__ (self, val=None, children=None): self.val = val self.children = children "class Solution: def postorder (self, root: 'Node')-> List [int]: if not root: return [] # the subsequent traversal is to traverse the child node of a node first After traversing the node itself # recursive result = [] def postHelper (root): if not root: return None children = root.children for child in children: postHelper (child) result.append (root.val) postHelper (root) return result # iterative method: auxiliary stack res = [] stack = [root ] while stack: node = stack.pop () if node is not None: res.append (node.val) for children in node.children: stack.append (children) return res [::-1]

Conclusion: there is not much difference between N-tree and binary tree, the only difference is that many children do not need to judge about children.

At this point, the study of "how to achieve three kinds of traversal of python N-tree" is over. I hope to be able to solve your doubts. The collocation of theory and practice can better help you learn, go and try it! If you want to continue to learn more related knowledge, please continue to follow the website, the editor will continue to work hard to bring you more practical articles!

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.