Binary tree

Preordered or preordered binary tree traversal

The nodes are represented by letters and the numbers indicate the order of the traversal outputs

function beforeTraversal(root){
    let result = []
    let stack = []
    while(root || stack.length>0) {while(root){
            result.push(root.val)
            stack.push(root)
            root = root.left
        }
        root = stack.pop()
        root = root.right
    }
    return result
}
Copy the code

The analysis code runs in and out of the stack in this order:

  • A,B,D,E into the result stack,
  • E (stack) stack
  • D (stack) stack
  • F to the result stack, F to the stack,
  • F (stack) stack
  • A stack (stack)
  • A. result B. stack C. result D. stack
  • H goes into the result stack and into the stack
  • G goes on the result stack and onto the stack
  • G (stack) stack
  • H (stack) stack
  • C (stack) stack
  • S is added to the result stack and added to the stack
  • S (stack) stack

Result stack is the order of the last output: A, B, D, E, F, C, H, G, S

Middle order traversal of binary trees

The nodes are represented by letters and the numbers indicate the order of the traversal outputs

function inorderTraversal(root){
    if(! root)return [];
    let result = []
    let stack = []
    while(root || stack.length ){
        while(root){
            stack.push(root)
            root = root.left
        }
        root = stack.pop()
        result.push(root.val)
        root = root.right
    }
    return res
}
Copy the code

The analysis code runs in and out of the stack in this order:

  • A (stack) stack
  • B (stack) stack
  • D (stack) stack
  • E (stack) stack
  • E goes out of the stack and E goes into the result stack
  • D goes out of the stack and D goes into the result stack
  • F goes to the stack,F goes out of the stack, and F goes to the result stack
  • B goes out of the stack and B goes into the result stack
  • A goes out of the stack and A goes into the result stack
  • C (stack) stack
  • H goes into the stack,H goes out of the stack, and H goes into the result stack
  • G goes into the stack,G goes out of the stack, and G goes into the result stack
  • C goes out of the stack and C goes into the result stack
  • S goes into the stack,S goes out of the stack, and S goes into the result stack

The final output is: E D F B A H G C S

Backward traversal of a binary tree

The nodes are represented by letters and the numbers indicate the order of the traversal outputs

function postorderTraversal(root) {
      let result =[];
      let stack = [];
      while (root || stack.length){
        while(root){
          stack.push(root);
          result.unshift(root.val); // Where unshift is pushed to the front
          root = root.right;
        }
        root = stack.pop();
        root = root.left;
      }
      return res;
  };
  
Copy the code

The analysis code runs in and out of the stack in this order:

  • A goes to the stack, and A goes to the result stack
  • Result: [C,A] result: [C,A]
  • Result: [S,C,A]
  • S (stack) stack
  • C (stack) stack
  • Result :[H,S,C,A]
  • Result :[G,H,S,C,A]
  • G (stack) stack
  • H (stack) stack
  • A stack (stack)
  • Result :[B,G,H,S,C,A]
  • B (stack) stack
  • Result :[D,B,G,H,S,C,A]
  • F into (stack), F into (result) stack result:[F,D,B,G,H,S,C,A]
  • F (stack) stack
  • D (stack) stack
  • E (stack) stack, E into the stack (result) result: [E, F, D, B, G, H, A, C, A]
  • E (stack) stack

The final output result is: [E,F,D,B,G,H,A,C,A] post-order traversal from the order of the stack can be seen from the right side of the tree traversal and use the METHOD of JS array unshift to cross the back of the stack of elements in the first place, so as to achieve post-order traversal