首页 > 代码库 > 二叉树基础——前序遍历、中序遍历、后序遍历、按层遍历

二叉树基础——前序遍历、中序遍历、后序遍历、按层遍历

转载请注明原文地址:

 

一:树的结点

    一般默认树的结点由:结点值、左儿子、右儿子,构造函数组成。

class TreeNode{
    int value;
    TreeNode  left;
    TreeNode  right;
    public TreeNode(int i){
    this.value=http://www.mamicode.com/i;
    }
}

二:二叉树的遍历实现——递归和非递归

    1:递归实现==按照遍历方式(前、中、后)对左、根、右的访问顺序去 打印结点值、递归左儿子、递归右儿子

    public void preorder(TreeNode root){
        if(root==null){
            return;
        }
        System.out.println(root.val);    //
        preorder(root.left,pre);//
        preorder(root.right,pre);//
    }

    public void inorder(TreeNode root){
        if(root==null){
            return;
        }
        inorder(root.left,in); /左
        System.out.println(root.val);//
        inorder(root.right,in);//
    }

    public void postorder(TreeNode root){
        if(root==null){
            return;
        }
        postorder(root.left,post);//
        postorder(root.right,post);//
        System.out.println(root.val);//
    }

 

    2:非递归实现==使用 栈 来控制结点的处理顺序

 

二叉树基础——前序遍历、中序遍历、后序遍历、按层遍历