基于java的二叉树数据结构实现

首先我们要认识下，什么是二叉树，先看下百科

理解了二叉树的结构，接下来我们就来分解一下二叉树的组成。

首先一个最简易的二叉树就是一个节点，结构包含左节点、右节点，同时应该还包含自身存储的信息。

import lombok.Data;
import lombok.ToString;

/**  
* @ClassName: Node  
* @Description: 树节点 每个节点有3个基本属性,即左右节点和节点存储的数据
* @author M.k.  
* @date 2018年10月12日  
*/
@Data
@ToString
public class Node<T> {
    
    /**
     * 节点数据
     */
    private T data;
    
    /**
     * 左节点
     */
    private Node<T> left;
    
    /**
     * 右节点
     */
    private Node<T> right;

    /**
     * @param data
     */
    public Node(T data) {
        super();
        this.data = data;
    }
    
}

 

接下来，定义一个树，树里面只包含了一个根节点，还有一些扩展性方法，比如插入、查询之类的。

二叉树的遍历形式一般分为三种：

 ①、中序遍历:左子树——》根节点——》右子树
 ②、前序遍历:根节点——》左子树——》右子树
 ③、后序遍历:左子树——》右子树——》根节点

例如：

先序遍历的结果为:0  1   3  7  4  2  5  6

中序遍历的结果为:7   3   1  4  0  5  2  6

后序遍历的结果为:7   3   4  1  5  6  2  0

一般常用的是中序遍历。

import lombok.Data;
import lombok.ToString;

/**
 * @ClassName: BinaryTree
 * @Description: 二叉树结构
 *               <p>
 *               二叉树中的节点都拥有两个分叉
 *               <p>
 *               二叉树查找主要分三种方式：
 *               <P>
 *               ①、中序遍历:左子树——》根节点——》右子树
 *               <P>
 *               ②、前序遍历:根节点——》左子树——》右子树
 *               <P>
 *               ③、后序遍历:左子树——》右子树——》根节点
 * @author M.k. 
 * @date 2018年10月12日
 * 
 */
@Data
@ToString
public class BinaryTree<T> {

    /**
     * 二叉树种存储根节点
     */
    private Node<T> root;
    
    /**
     * @Title: find   
     * @Description: 默认以中序遍历   
     * @param: @return      
     * @return: Node<T>      
     * @throws
     */
    public Node<T> find() {
        Node<T> node = getRoot();
        return node;
    }
    
    
    /**
     * @Title: insert   
     * @Description: 二叉树插入   
     * @param: @param node      
     * @return: void      
     * @throws
     */
    public void insert(T data) {
        Node<T> insert = new Node<>(data);
        if(null == getRoot()) {
            setRoot(insert);
            return;
        }
        // 定位根节点
        Node<T> current = getRoot();
        Node<T> parent = null;
        while(null != current) {
            parent = current;
            // 如果中节点大于插入节点数据，开始左查找，否则进行右查找
            if(current.getData().hashCode() > insert.getData().hashCode()) {
                current = current.getLeft();
                if(current == null) {
                    parent.setLeft(insert);
                }
            } else {
                current = current.getRight();
                if(current == null) {
                    parent.setRight(insert);
                }
            }
        }
    }
    
}

 

以上只实现了一下插入功能，to be continue...

test:

public class TestBT {
    public static void main(String[] args) {
        BinaryTree<Integer> bt = new BinaryTree<>();
        Random random = new Random();
        StringBuilder sequence = new StringBuilder();
        for(int i = 0; i < 10; i++) {
            int randonInt = random.nextInt(20);
            bt.insert(randonInt);
            sequence.append(randonInt).append(",");
        }
        System.out.println(sequence.toString());
        System.out.println(bt);
    }
}

运行结果：