二叉树及相关数据结构的java语言实现

---

二叉树是一种很直观的非线性数据结构。本篇主要记录与二叉树相关的数据结构的java语言实现方法。

一、二叉树

1. 节点

既然有java，就简简单单用类来实现节点。

class TreeNode{
    int value;
    TreeNode leftNode;
    TreeNode rightNode;
    //构造函数
    TreeNode(int v){
        this.value = v;
    }
}

main函数手动建树：

    public static void main(String[] args){
        TreeNode node1 = new TreeNode(10);
        TreeNode node2 = new TreeNode(3);
        TreeNode node3 = new TreeNode(30);
        TreeNode node4 = new TreeNode(15);
        TreeNode node5 = new TreeNode(6);
        node1.leftNode = node2;
        node1.rightNode = node3;
        node3.leftNode = node4;
        node2.rightNode = node5;
        //结构：10 - 30 - 15
        //        - 3  - 6

这样就建好了一个无序的二叉树。

2. 遍历

一般遍历有深度优先和广度优先两种，深度包括先序、后序、中序遍历。这三者区别主要是先序遍历优先访问中间节点，中序是在中间访问中间节点（先访问左节点，后中节点，后右节点），后序遍历是先左右节点最后中间节点。

static void traversal(TreeNode node){
        //先序遍历
        if(node == null) return;
        System.out.println(node.value);
        traversal(node.leftNode);
        traversal(node.rightNode);
    }

广度优先遍历即层次遍历，和bfs类似，将首节点入队，每次循环从队伍中取出一个点，输出中间节点，把左右子节点入队，从上到下按层访问。

static void layerTraversal(TreeNode node){
        //层次遍历（bfs）
        if(node == null) return;
        LinkedList<TreeNode> list = new LinkedList<TreeNode>();
        list.add(node);
        while(!list.isEmpty()){
            TreeNode node_now = list.removeFirst();
            System.out.println(node_now.value);
            // 左右儿子通通入队
            if(node_now.leftNode != null)
            list.add(node_now.leftNode);
            if(node_now.rightNode != null)
            list.add(node_now.rightNode);
        }
    }