认识达内从这里开始

认真做教育专心促就业

数据结构-二叉树-三种遍历-Java实现

发布：济南IT培训
来源：互联网
时间：2018-04-17 17:03

    最近济南IT培训在写一个方法.数据表中每一条记录都有一个parent_id字段,就是父亲的ID,然后现在要根据单条记录来获取所有的子孙记录.这让我想到了使用树形结构来实现.
    在实现之前先来回顾一下简单的二叉树结构,具体的实现方法等后面另写一篇文章,到时候会写的很详细,让每个人都能看懂,容易学会.
    一、所谓的二叉树分为五种:
    1,null,就是没有节点;
    2,只有一个根节点;
    3,只有左孩子;
    4,只有右孩子;
    5,左右孩子都有;
    二、稍微分析一下二叉树的特点:
    性质1:在二叉树的第i层上至多有2^(i-1)个节点(i >= 1)
    性质2:深度为k的二叉树至多有2^(k-1)个节点(k >=1)
    性质3:对于任意一棵二叉树T而言,其叶子节点数目为N0,度为2的节点数目为N2,则有N0 = N2 + 1.
    性质4:具有n个节点的完全二叉树的深度 .
    三、二叉树的三种遍历方式:
    前序遍历,中序遍历,后续遍历.
    其实这三种遍历无非就是节点本身、左孩子、右孩子三个节点遍历的前后顺序不同罢了;
    四、看代码:
    这里的代码实现简单,有兴趣的朋友可以直接复制粘贴拿去运行,稍微看看就能懂了,这里就是简单的写了一个demo,朋友们可以拿去自由发挥.
    先创建一个二叉树节点对象Node.java,我是在同包中创建的;
    package demo;
    /**
    * 二叉树节点对象
    * @description
    * @author
    * @className Node.java
    * @param
    * @return
    * @createTime 2017年12月8日下午8:42:44
    * @version 1.0
    */
    public class Node {
    private Node leftChild; // 左孩子
    private Node rightChild; // 右孩子
    private int data;// 节点数据
    public Node getLeftChild() {
    return leftChild;
    }
    public void setLeftChild(Node leftChild) {
    this.leftChild = leftChild;
    }
    public Node getRightChild() {
    return rightChild;
    }
    public void setRightChild(Node rightChild) {
    this.rightChild = rightChild;
    }
    public int getData() {
    return data;
    }
    public void setData(int data) {
    this.data = data;
    }
    /**
    * 构造器
    * @param data
    */
    public Node(int data) {
    super();
    this.data = data;
    }
    }
    接下来就是二叉树遍历了;
    package demo;
    import java.util.ArrayList;
    import java.util.List;
    /**
    *
    * @description 二叉树Demo
    * @author
    * @className BinaryTree.java
    * @param
    * @return
    * @createTime 2017年12月8日下午8:41:39
    * @version 1.0
    */
    public class BinaryTree {
    public static void main(String[] args) {

// 数组,将这个数组转化为二叉树并处理这二叉树

济南IT培训

    int[] array = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
    List<Node> list = createBinTree(array);
    // 得到根
    //Node node = list.get(0);
    Node node = list.get(3);
    // 先序遍历
    System.out.println("先序遍历:");
    preOrderTraverse(node);
    System.out.println();
    // 中序遍历
    System.out.println("中序遍历:");
    inOrderTraverse(node);
    System.out.println();
    // 后序遍历
    System.out.println("后序遍历:");
    postOrderTraverse(node);
    System.out.println();
    }
    /**
    * 创建二叉树
    * @param array
    */
    public static List<Node> createBinTree(int[] array){
    /**
    * 遍历数据,并将数组中每个元素转换成二叉树中的一个节点
    * 并使用List集合存储
    */
    Node node = null;
    List<Node> list = new ArrayList<Node>();
    for(int i=0; i<array.length; i++){
    // 每个元素值都是节点携带的数据
    node = new Node(array[i]);
    list.add(node);
    }
    /**
    * 转换成二叉树
    * 算法:先处理除最后一个父节点以外的父节点
    * 最后一个父节点最后处理
    * 因为最后一个父节点特殊,当数组的长度是偶数时没有右孩子
    */
    for(int i=0; i<list.size()/2-1; i++){
    // 设置每个父节点的左孩子
    list.get(i).setLeftChild(list.get(i*2+1));
    // 设置每个父节点的右孩子
    list.get(i).setRightChild(list.get(i*2+2));
    }
    // 最后一个父节点的处理
    int lastParentIndex = list.size()/2-1;
    list.get(lastParentIndex).setLeftChild(list.get(lastParentIndex*2+1));
    // 长度为奇数的时候有右孩子
    if(list.size()%2==1){
    list.get(lastParentIndex).setRightChild(list.get(lastParentIndex*2+2));
    }
    return list;
    }
    /**
    * 先序遍历
    * @param node
    */
    public static void preOrderTraverse(Node node){
    if (node == null)
    return;
    System.out.print(node.getData() + " ");
    preOrderTraverse(node.getLeftChild());
    preOrderTraverse(node.getRightChild());
    }
    /**
    * 中序遍历
    * @param node
    */
    public static void inOrderTraverse(Node node) {
    if (node == null)
    return;
    inOrderTraverse(node.getLeftChild());
    System.out.print(node.getData() + " ");
    inOrderTraverse(node.getRightChild());
    }
    /**
    * 后序遍历
    * @param node
    */
    public static void postOrderTraverse(Node node) {
    if (node == null)
    return;
    postOrderTraverse(node.getLeftChild());
    postOrderTraverse(node.getRightChild());
    System.out.print(node.getData() + " ");
    }

}

更多济南IT培训相关咨询,请扫描下方二维码

济南IT培训