java手动构建二叉树并实现广度遍历、深度遍历（前序中序后序）

• • 什么是二叉树
  • • 属性
    • • 节点TreeNode
    • 手动构建如下所示二叉树
  • 遍历
  • • 广度遍历
    • • • 算法思想
        • 实现细节
    • 深度遍历
    • • 先序遍历（根左右）
      • • 算法思想
        • 实现细节
      • 中序遍历（左根右）
      • • 算法思想
        • 实现细节
      • 后续遍历（左右根）
      • • 算法思想
        • 实现细节

在计算机科学中，树是一种重要的非线性数据结构，直观的看，它是数据元素按分支关系组织起来的结构。二叉树是每个节点最多有两个子树的有序树。通常子树的根被称作“左子树”和“右子树”。二叉树常被用做二叉查找树和二叉堆或是二叉排序树。二叉树的每个节点至多只有两颗子树，二叉树有左右之分，次序不能颠倒。

通常我们使用数的根节点代表这颗树

和双向链表相似，二叉树的每个节点也有三个属性值：存储的数据 T data、左子树根节点 TreeNode left、右子树根节点TreeNode right

private static  class TreeNode{
    T data;
    TreeNode left;
    TreeNode right;

    //默认给出的构造方法只含有数据，左右子树都为空
    public TreeNode(T data) {
        this.data = data;
    }
}

public static void main(String[] args) {
        
        TreeNode root = new TreeNode<>(1);
        TreeNode node2 = new TreeNode<>(2);
        TreeNode node3 = new TreeNode<>(3);
        TreeNode node4 = new TreeNode<>(4);
        TreeNode node5 = new TreeNode<>(5);
        TreeNode node6 = new TreeNode<>(6);
        TreeNode node7 = new TreeNode<>(7);

        
        root.left = node2;
        root.right = node3;
        node2.left = node4;
        node2.right = node5;
        node3.left = node6;
        node3.right = node7;
        
    }

即按照一定的顺序依次遍历整棵树

可以理解为按照层数，依次向下，每层从左到右依次遍历

那么按照定义，上述二叉树的广度遍历结果应该为： 1 2 3 4 5 6 7

由于是按照层数遍历，则需要依次遍历每一层并存储每一层的节点，用于下次遍历
即先遍历根节点，再检查根节点是否有左右子树，依次循环
可以使用☞队列来进行边存边读
1、把每一层的数据依次存储进去
2、开始遍历上一层的数据，由于队列是先进先出的，所以顺序不会有误
3、在遍历上一层的时候，依次存储上一层节点的左右子树（没有则不存），即一边遍历上一层节点，一边存储下一层节点

public static void printByLayer(TreeNode root){
    if (root != null) {
        Queue queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()){
            //从队列中取出数据
            TreeNode node = queue.poll();
            System.out.print(node.data + "t");

            //边读边取
            if(node.left != null){
                queue.offer(node.left);
            }
            if(node.right != null){
                queue.offer(node.right);
            }
        }
    }else {
        System.out.println("当前为空树！");
        return;
    }
}

根据遍历根节点的先后顺序可以将深度遍历分为三种：先序遍历、中序遍历、后序遍历。核心在于一个节点就是一棵子树、递归

简单说就是，一棵树先序遍历要：

1、先遍历根节点
2、遍历左子树

左子树还有子树的话，就把左子树看做一颗新树（重复1、2、3）
没有子树就直接输出

3、遍历右子树

右子树还有子树的话，就把右子树看做一颗新树（重复1、2、3）
没有子树就直接输出

那么上述二叉树的先序遍历结果应该为 ： 1 2 4 5 3 6 7

public static void pri_print(TreeNode root){
    if (root != null) {
        System.out.print(root.data+"t");
        if(root.left != null){
            pri_print(root.left);
        }
        if(root.right != null){
            pri_print(root.right);
        }
    }else {
        System.out.println("当前为空树！");
        return;
    }
}

1、遍历左子树

左子树还有子树的话，就把左子树看做一颗新树（重复1、2、3）
没有子树就直接输出

2、遍历根节点

3、遍历右子树

右子树还有子树的话，就把右子树看做一颗新树（重复1、2、3）
没有子树就直接输出

那么上述二叉树的先序遍历结果应该为 ： 4 2 5 1 6 3 7

public static void mid_print(TreeNode root){
    if (root != null) {
        //左
        if(root.left != null){
            mid_print(root.left);
        }
        //根
        System.out.print(root.data+"t");
        //右
        if(root.right != null){
            mid_print(root.right);
        }
    }else {
        System.out.println("当前为空树！");
        return;
    }
}

1、先遍历左子树

左子树还有子树的话，就把左子树看做一颗新树（重复1、2、3）
没有子树就直接输出

2、遍历右子树

右子树还有子树的话，就把右子树看做一颗新树（重复1、2、3）
没有子树就直接输出

3、遍历根节点

那么上述二叉树的先序遍历结果应该为 ： 4 5 2 6 7 3 1

public static void last_print(TreeNode root){
    if (root != null) {
        //左
        if(root.left != null){
            last_print(root.left);
        }
        //右
        if(root.right != null){
            last_print(root.right);
        }
        //根
        System.out.print(root.data+"t");
    }else {
        System.out.println("当前为空树！");
        return;
    }
}

那么简单的二叉树以及其遍历方式就讲解完毕了。关于对二叉树的进一步讲解,请移步来看我的这篇文章☞==二叉排序树==

以上均为本人个人观点，借此分享，希望能和大家一起进步。如有不慎之处，劳请各位批评指正！鄙人将不胜感激并在第一时间进行修改！