Algorithm | Tree traversal

柔光的暖阳◎ 2022-01-06 16:33 136阅读 0赞

There are three types of depth-first traversal: pre-order,in-order, and post-order.

For a binary tree, they are defined as operations recursively at each node, starting with the root node as follows:

## Pre-order ##

Visit the root.  
Traverse the left subtree.  
Traverse the right subtree.

iterativePreorder(node)
      parentStack = empty stack
      parentStack.push(null)
      top =  node 
      while ( top != null )
          visit( top )
          if ( top.right != null ) 
              parentStack.push(top.right)
          if ( top.left != null ) 
              parentStack.push(top.left)
          top = parentStack.pop()

## In-order ##

Traverse the left subtree.  
Visit root.  
Traverse the right subtree.

iterativeInorder(node)
      parentStack = empty stack
      while (not parentStack.isEmpty() or node ≠ null)
        if (node ≠ null)
          parentStack.push(node)
          node = node.left
        else
          node = parentStack.pop()
          visit(node)
          node = node.right

## Post-order ##

Traverse the left subtree.  
Traverse the right subtree.  
Visit the root.

iterativePostorder(node)
      parentStack = empty stack  
      lastnodevisited = null 
      while (not parentStack.isEmpty() or node ≠ null)
        if (node ≠ null)
          parentStack.push(node)
          node = node.left
        else
          peeknode = parentStack.peek()
          if (peeknode.right ≠ null and lastnodevisited ≠ peeknode.right) 
            /* if right child exists AND traversing node from left child, move right */
            node = peeknode.right
          else
            parentStack.pop() 
            visit(peeknode)
            lastnodevisited = peeknode

## Morris Travel ##

1 /**
     2  * Definition for binary tree
     3  * struct TreeNode {
     4  *     int val;
     5  *     TreeNode *left;
     6  *     TreeNode *right;
     7  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
     8  * };
     9  */
    10 class Solution {
    11 public:
    12     vector<int> inorderTraversal(TreeNode *root) {
    13         vector<int> ret;
    14         if (!root) return ret;
    15         TreeNode *cur = root;
    16         
    17         while (cur) {
    18             if (!cur->left) {
    19                 ret.push_back(cur->val);
    20                 cur = cur->right;
    21             } else {
    22                 TreeNode *rightmost = cur->left;
    23                 while (rightmost->right != NULL && rightmost->right != cur) rightmost = rightmost->right;
    24                 if (rightmost->right == cur) {
    25                     rightmost->right = NULL;
    26                     ret.push_back(cur->val);
    27                     cur = cur->right;
    28                 } else {
    29                     rightmost->right = cur;
    30                     cur = cur->left;
    31                 }
    32             }
    33         }
    34         
    35         return ret;
    36     }
    37 };

后序：

![161440377403840.jpg][]

转载于:https://www.cnblogs.com/linyx/p/3627184.html

[161440377403840.jpg]: /images/20211227/c339228b0dd24f9ca01cf88f627c73d5.png