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

What are the four kinds of traversal of python binary tree? aiming at this problem, this article introduces the corresponding analysis and solution in detail, hoping to help more partners who want to solve this problem to find a more simple and feasible method.

How does the data structure traverse? the traversal of the binary tree starts from the root node and traverses the whole tree according to a certain order, which is divided into four ways according to the order, namely, pre-order, middle-order, post-order and sequence. There is a long-standing formula for these sorts of rankings:

Preorder traversal: root node-> left subtree-> right subtree

Traversal in the middle order: left subtree-> root node-> right subtree

Traversal after order: left subtree-> right subtree-> root node

Hierarchical traversal: you can simply traverse by hierarchy.

Next, let's explain these recipes:

Let's draw a simple binary tree first.

Explain with the above binary tree:

Preorder

The formula of preorder traversal is: root node-> left subtree-> right subtree. It means to traverse the root node A first, then the left subtree B, but B also has a left subtree, and then take B as the root, and the next step should be the left subtree C-right subtree D of root B. Because C node and D node themselves are leaf nodes, they have no child nodes. At this time, all the descendant nodes of the left subtree B of the root node A have been traversed. Next, we will traverse the right subtree E of the root node A, and then regard E as the root node. The root E has no left node, only the right node F, at this time, the traversal of the whole tree is completed, and the final traversal order is A-B-C-D-E-F.

Intermediate order

The formula for traversing in the middle order is: left subtree-> root node-> right subtree. The logic of the middle order is a little strange. He starts from the leftmost leaf node of the whole tree, that is, the C node in the image above, finds the root node of C node, that is, node B, and then finds the right node D node of node B. at this time, the whole left subtree of root node A has been traversed. According to the above formula, he traverses the root node A, and the root node A has a right subtree node E. If E has a left subtree, we should first traverse the left subtree of E, starting from the leftmost leaf node of E, but E does not have a left subtree at this time, then we should traverse the root node Epene E there is a right leaf node F, and finally traverse F, so that the whole data structure traversal is completed, the traversal order is C-B-D-A-E-F.

Post-order

The formula for traversing the post-order is:

Left subtree-> right subtree-> root node.

It means to traverse the root node An at last. In fact, according to the traversal mode in the above order, we should be able to draw a conclusion, starting with the leftmost leaf node C, the right node D of the left leaf node C, the root node of the left leaf node C, and the right node B of the left leaf node. Next, we will traverse the right subtree of the whole tree. Starting from the left leaf node, there is no left leaf node, so the root node of the right leaf node is E. Finally, the root node An of the whole tree is traversed in C-B-D-F-E-An order.

Sequence

Sequence traversal, as the name implies, is traversed layer by layer, in order from left to right and from top to bottom. The traversal order is A-B-E-C-D-F.

This is the answer to the question about what the four kinds of traversal of python binary tree are. I hope the above content can be of some help to you. If you still have a lot of doubts to be solved, you can follow the industry information channel to learn more about it.

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.