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

文章目录

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

什么是二叉树

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

属性

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

节点TreeNode

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

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

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

手动构建如下所示二叉树

public static void main(String[] args) {
        /*
         * 创建树节点
         * */
        TreeNode<Integer> root = new TreeNode<>(1);
        TreeNode<Integer> node2 = new TreeNode<>(2);
        TreeNode<Integer> node3 = new TreeNode<>(3);
        TreeNode<Integer> node4 = new TreeNode<>(4);
        TreeNode<Integer> node5 = new TreeNode<>(5);
        TreeNode<Integer> node6 = new TreeNode<>(6);
        TreeNode<Integer> 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、在遍历上一层的时候，依次存储上一层节点的左右子树（没有则不存），即一边遍历上一层节点，一边存储下一层节点

实现细节

/**
 * @param root:  根节点
 * @return void
 * decription: 广度遍历二叉树
 */
public static void printByLayer(TreeNode root){
    if (root != null) {
        Queue<TreeNode> 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

实现细节

/**
 * @param root:  根节点
 * @return void
 * decription: 先序遍历二叉树  根左右
 */
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

实现细节

/**
 * @param root:  根节点
 * @return void
 * decription: 中序遍历 左根右
 */
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

实现细节

/**
 * @param root:  根节点
 * @return void
 * decription: 后续遍历
 */
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;
    }
}