Binary tree traversal

Binary tree binary tree ： Each node has at most 2 A child node

Noun ：

Node of the root
Subtree of root
Leaf node ： No, “ children ” Of leaf
Parent node parent
Brother node ： sibling
Child node ： child
The height of the tree
Left the child left child
The right child right child

Full binary tree ： All non leaf nodes of a binary tree have left and right children , And all leaf nodes are at the same level ... Each branch is full
Perfect binary tree ： To a n A binary tree of nodes , Number... In hierarchical order , All numbers from 1 To n ,, If all the nodes of this tree are numbered with the full binary tree of the same depth from 1 To n Same node location , Is a complete binary tree
Binary search tree binary search tree： For a binary search tree with balanced node distribution , If the total number of nodes is n, So the time complexity is O(logn), As deep as the tree
Binary search tree , also called Binary sort tree binary sort tree
Binary heap ： A special kind of complete binary tree , Store... In an array , As long as the parent node is bigger than its left and right children
Binary tree self balancing ： Red and black trees ,AVL Trees , Count piles

Binary tree traversal

In a computer program , Traversal itself is a linear operation , So traverse arrays or linked lists that also have a linear structure , It's a piece of cake
Binary tree ： Typical nonlinear data structures , When traversing, we need to transform the nonlinear associated nodes into a linear sequence

• Depth-first traversal ： In depth , Go straight to the end
  • Before the order
    The root node is at the front , From left to right
  • Middle preface
  • In the following order
• Breadth first traversal
  • Sequence traversal ： Binary tree according to the hierarchical relationship from root node to leaf node , Traverse each node horizontally layer by layer

Most problems that can be solved recursively , In fact, it can be used Stack solve
because ： Both recursion and stack have the feature of backtracking

Code ：
Recursive traversal ：

public class BinaryTreeDemo {
    
    private static class TreeNode{
    
        int data;
        TreeNode leftChild;
        TreeNode rightChild;

        public TreeNode(int data) {
    
            this.data = data;
        }
    }

    //  establish binary tree
    public static TreeNode createBinaryTree(LinkedList<Integer> inputList){
    
        TreeNode  node = null;
        if (inputList == null || inputList.isEmpty()){
    
            return null;
        }
        Integer data = inputList.removeFirst();
        if (data != null){
    
            node = new TreeNode(data);
            node.leftChild = createBinaryTree(inputList);
            node.rightChild = createBinaryTree(inputList);
        }

        return node;
    }

    //  Before the order 
    public static void preOrderTraveral(TreeNode node){
    
        if (node == null){
    
            return;
        }
        System.out.println(node.data);
        preOrderTraveral(node.leftChild);
        preOrderTraveral(node.rightChild);

    }

    //  Middle preface 
    public static void inOrderTraveral(TreeNode node){
    
        if (node == null){
    
            return;
        }
        inOrderTraveral(node.leftChild);
        System.out.println(node.data);
        inOrderTraveral(node.rightChild);
    }

    //  In the following order 
    public static void postOrderTraveral(TreeNode node){
    
        if (node == null){
    
            return;
        }
        postOrderTraveral(node.leftChild);
        postOrderTraveral(node.rightChild);
        System.out.println(node.data);
    }

    public static void main(String[] args) {
    
        LinkedList<Integer> inputList = new LinkedList<>(Arrays.asList(3,2,9,null,null,10,null,null,8,null,4));
        TreeNode node = createBinaryTree(inputList);
        System.out.println(" The former sequence traversal ");
        preOrderTraveral(node);
        System.out.println(" In the sequence traversal ");
        inOrderTraveral(node);
        System.out.println(" After the sequence traversal ");
        postOrderTraveral(node);
    }
}

Stack traversal ：

public class BinaryTreeStack {
    
    private static class TreeNode{
    
        int data;
        TreeNode leftChild;
        TreeNode rightChild;

        public TreeNode(int data) {
    
            this.data = data;
        }
    }

    //  Preface 
    public static  void preOrderTraveralWithStack(TreeNode root){
    
        Stack<TreeNode> stack = new Stack<>();
        TreeNode treeNode = root;
        while (treeNode != null || !stack.isEmpty()){
    

            while (treeNode != null){
    
                System.out.println(treeNode.data);
                stack.push(treeNode);
                treeNode = treeNode.leftChild;
            }

            if (!stack.isEmpty()){
    
                treeNode = stack.pop();
                treeNode = treeNode.rightChild;
            }

        }
    }

    //  Middle preface 
    public static void inOrderTraveralWithStack(TreeNode root){
    
        Stack<TreeNode> stack = new Stack<>();
        TreeNode treeNode = root;
        while (treeNode != null || !stack.isEmpty()){
    
            if (treeNode != null){
    
                stack.push(treeNode);
                treeNode = treeNode.leftChild;
            }else{
    
                 treeNode = stack.pop();
                System.out.println("----"+treeNode.data);
                treeNode = treeNode.rightChild;
            }
        }
    }

    /** *  After the sequence traversal  ：  The order   Left -- Right -- root  *  The first sequence traversal  ：  The order   root -- Left -- Right  *  Here we can think of , Fine tune the preorder traversal to ：  root  --  Right  --  Left ..  Then these nodes   Out of the stack  ,,push To a reverse stack , Exchange order  *  This fine adjustment is very simple , It's just push When the node reaches the stack , First push The left node , Again push Right node ,, At this time, the top of the stack is the right node ,,, The right node pops up first , Again push *  To the reverse stack stackReverse in , Again push node  *  The core :  We only need to add a stack to reverse output each node traversed in sequence after fine-tuning , You can get post order traversal  */
    public static void postOrderBinaryTreeWithStack(TreeNode root){
    
        Stack<TreeNode> stack = new Stack<>();
        TreeNode treeNode = root;
        Stack<TreeNode> stackReverse = new Stack<>();
        ArrayList<Integer> list = new ArrayList<>();
        stack.push(root);
        while (!stack.isEmpty()){
    
            treeNode = stack.pop();
            stackReverse.push(treeNode);
            // stack Take out the middle right first ,,stackReverse Put it in the middle right first , Take it out later 
            if (treeNode.leftChild != null){
    
                stack.push(treeNode.leftChild);
            }
            if (treeNode.rightChild != null){
    
                stack.push(treeNode.rightChild);
            }
        }

        while (!stackReverse.isEmpty()){
    
            treeNode = stackReverse.pop();
            list.add(treeNode.data);
        }
        System.out.println(list);


    }

    //  establish binary tree
    public static TreeNode createBinaryTree(LinkedList<Integer> inputList){
    
        TreeNode  node = null;
        if (inputList == null || inputList.isEmpty()){
    
            return null;
        }
        Integer data = inputList.removeFirst();
        if (data != null){
    
            node = new TreeNode(data);
            node.leftChild = createBinaryTree(inputList);
            node.rightChild = createBinaryTree(inputList);
        }

        return node;
    }


    //  Sequence traversal 
    public static void levelOrderTraversalWithQueue(TreeNode root){
    
        LinkedList<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()){
    
            TreeNode node = queue.poll();
            System.out.println(node.data);
            if (node.leftChild != null){
    
                queue.offer(node.leftChild);
            }
            if (node.rightChild != null){
    
                queue.offer(node.rightChild);
            }
        }
    }

    //  One level  ： A collection 
   static ArrayList<List<Integer>> levels = new ArrayList<>();
    //  Sequence traversal - recursive 
    public static void levelOrderTraversal(TreeNode node,int level){
    
        if (levels.size() == level) {
    
            // start the current level
            levels.add(new ArrayList<Integer>());
        }
            //  Fill in the data 
            levels.get(level).add(node.data);

            if (node.leftChild != null){
    
                levelOrderTraversal(node.leftChild,level+1);
            }
            if (node.rightChild != null){
    
                levelOrderTraversal(node.rightChild,level+1);
            }

        System.out.println("levels = " + levels);
    }


    public static void levelOrderTraversal(TreeNode root){
    
        if (root == null){
    
            return;
        }
        levelOrderTraversal(root,0);
    }

    public static void main(String[] args) {
    
        LinkedList<Integer> inputList = new LinkedList<>(Arrays.asList(3,2,9,null,null,10,null,null,8,null,4));
        TreeNode node = createBinaryTree(inputList);
        System.out.println(" The former sequence traversal ");
        preOrderTraveralWithStack(node);
        System.out.println(" Middle preface ");
        inOrderTraveralWithStack(node);
        System.out.println(" In the following order ");
        postOrderBinaryTreeWithStack(node);
        System.out.println(" Sequence traversal ");
        levelOrderTraversalWithQueue(node);
        System.out.println(" Sequence traversal --2");
        levelOrderTraversal(node);

    }
   
}

After the sequence traversal ： Use a reverse stack
Sequence traversal ： Using the queue , Put the child nodes offer() Go in and leave the team