二叉树遍历

参考:https://www.jianshu.com/p/456af5480cee
https://blog.csdn.net/My_Jobs/article/details/43451187
https://www.yunaitong.cn/binary-tree-traverse.html

一、概念

前序遍历:根节点 -> 左子树 -> 右子树

中序遍历:左子树 -> 根节点 -> 右子树

后序遍历:左子树 -> 右子树 -> 根节点

二、实现

递归遍历:

public static void preOrderVisit(TreeNode root){*
    if(root != null) {*
       System.out.print(root.value);*
       preOrderVisit(root.left);*
       preOrderVisit(root.right);*
    }*
}*



public static void inOrderVisit(TreeNode root){*
    if(root != null) {*
       inOrderVisit(root.left);*
       System.out.print(root.value);*
       inOrderVisit(root.right);*
    }*
}*



public static void postOrderVisit(TreeNode root){*
    if(root != null) {*
       postOrderVisit(root.left);*
       postOrderVisit(root.right);*
       System.out.print(root.value);*
    }*
}*

非递归:

public static void preOrderVisit(TreeNode root) {*
   Stack<TreeNode> treeStack = new Stack<TreeNode>();*
   TreeNode node = root;*
   while (node != null || !treeStack.isEmpty()) {*
        while(node != null){*
           System.out.print(node.value);*
           treeStack.push(node);*
           node=node.left;*
       } *
       if(!treeStack.isEmpty()){*
           node=treeStack.pop();*
           node=node.right;*
       }*
    }*
}*



public static void inOrderVisit(TreeNode root) {*
   Stack<TreeNode> treeStack = new Stack<TreeNode>();*
   TreeNode node = root;*
   while (node != null || !treeStack.isEmpty()) {*
        while(node != null){*
           treeStack.push(node);*
           node=node.left;*
       } *
       if(!treeStack.isEmpty()){*
           node=treeStack.pop();*
           System.out.print(node.value);*
           node=node.right;*
       }*
    }*
}*



public static void postOrderVisit(TreeNode root) {*
   Stack<TreeNode> treeStack = new Stack<TreeNode>();*
   TreeNode node = root;*
    TreeNode lastvisit*
   while (node != null || !treeStack.isEmpty()) {*
        while(node != null){*
           treeStack.push(node);*
           node=node.left;*
       } *
        node = treeStack.peek();*
        if(node.right==null || node.right==lastVisit){*
            System.out.print(node.value);*
            treeStack.pop();*
           lastVisit=node;*
           node=null;*
        } else {*
           node=node.right;            *
        }*
    }*
}*

层次遍历:

public static levelVisit(TreeNode root) {*
   Stack<TreeNode> treeStack = new Stack<TreeNode>();*
    treeStack.push(root);*
    while(!treeStack.isEmpty()){*
        TreeNode node = treeStack.pop();*
        System.out.print(node.value);*
       if(node.left!=null) treeStack.push(node.left);*
       if(node.right!=null) treeStack.push(node.right);*
    }*
}*

comments powered by Disqus