A travel algorithm for binary trees

  • Visit (node), preorder(left Subtree), preorder(right Subtree).
  • In-order traversal: in-order(left Subtree), visit (node), in-order(right Subtree).
  • Post-order traversal: post-order(left Subtree), post-order(right Subtree), visit (node).
  • Hierarchical traversal: Visits each node one layer at a time.

Traverse each node of the binary tree in the preceding four ways.

Practice the techniques of the tour algorithm 1

The left subtree of figure A is A block, like A large node surrounded by parentheses. The right subtree does the same thing. And then do the front, middle and back traversal for each block.

  • Preorder traversal. A, (B, D, E), (C, F, G) I get A, B, D, E, C, F, G.

  • Middle order traversal. (D, B, E), A, (F, C, G). The result is D, B, E, A, F, C, G.

  • Post-order traversal. (D, E, B), (F, G, C), A. The result is D, E, B, F, G, C, A.

  • Hierarchy traversal. A, B, C, D, E, F, G

Practice the techniques of the tour algorithm ii

The idea is to draw a line from the left to the bottom for each node, and then read the nodes from left to right. The results are: A, B, D, E, C, F, G.

For each node, draw a line from the middle to the bottom, and then read the nodes from left to right. It’s D, B, E, A, F, C, G.

Back-order traversal idea: draw a line from the right to the bottom of each node, and then read the nodes from left to right. It’s D, E, B, F, G, C, A.

Practice the techniques of the tour algorithm 3

The idea of a pre-traversal is to draw a line to the left of each node, then wrap the tree around each node and branch starting at the root. The order through these short lines is the result. A, B, D, E, C, F, G.

The idea of a middle-order traversal is to draw a line from the bottom edge of each node, then wrap the tree around each node and branch starting at the root. The order through these short lines is the result. D, B, E, A, F, C, G.

Backorder traversal idea: Draw a line to the right of each node, then circle the tree starting at the root, passing through each node and branches of the tree. The order through these short lines is the result. D, E, B, F, G, C, A.

extension

  • The idea of pre-order traversal, mid-order traversal, and subsequent traversal is in depth-first order. The idea of hierarchical traversal is to traverse in breadth-first order.
  • It’s order n because we’re going through every node in the tree.
  • The extra space required for the hierarchy traversal of the breadth-first traversal idea is O (w), where W is the maximum width of the Binary Tree. For example, in the case of Perfect Binary Tree, the largest node is at the last level, and the i-level has at most 2i-1So it needs extra space O (Ceil(n/2)); Three other ways of thinking about depth-first traversal that require extra space are O (h), where h is the maximum height of a binary tree, such as an equilibrium tree h is Log2Phi of n, but h is n for an extremely unbalanced left-leaning or right-leaning tree. So in the worst case, the extra space needed for both is O (n). But the worst happens to different types of trees, so the amount of extra space required varies from tree to tree. It is clear from the above that the additional space required for the hierarchy traversal of breadth-first traversal thoughts is likely to be greater when the tree is more balanced, and the additional space required for the other three traversal modes of depth-first traversal thoughts is likely to be greater when the tree is less balanced.

Github

Github.com/renmoqiqi/1…