> 文档中心 > java手动构建二叉树并实现广度遍历、深度遍历(前序中序后序)

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

文章目录

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

什么是二叉树

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

属性

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

节点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;    }}

手动构建如下所示二叉树

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

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;    }}

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

深度遍历

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

先序遍历(根左右)

算法思想

简单说就是,一棵树先序遍历要:

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;    }}

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

中序遍历(左根右)

算法思想

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;    }}

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

后续遍历(左右根)

算法思想

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;    }}

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

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

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

天天排行榜