二叉树的实现

1.一个完整的书类应该包括三个基本类：

节点类、二叉排序树类、测试类

节点类

package com.company;

public class Node {  //创建一个节点类，为后续创建节点对象做准备
    public int value;

    public int getValue() {
         return value;
    }

    public void setValue(int value) {
        this.value = value;
    }

    public Node getLeftNode() {
        return LeftNode;
    }

    public void setLeftNode(Node leftNode) {
        LeftNode = leftNode;
    }

    public Node LeftNode;

    public Node getRightNode() {
        return RightNode;
    }

    public void setRightNode(Node rightNode) {
        RightNode = rightNode;
    }

    public Node RightNode;


    public Node(){}

    public Node(int value) {
        this.value = value;
    }
}

讲解

对于二叉树的一个节点，他应该包括三部分：

该节点本身所拥有的值（value）、该节点拥有的向下传递的左子节点、右子节点      
（有点类似于链表的节点，仅有的区别就在于：二叉树两个子节点一个value值、链表一个子节点一个value值）

对于上面代码中Java基础的类的定义和实现要有：

变量的get和set方法、类的有参和无参构造方法

二叉排序树类

package com.company;

import java.util.Arrays;
public class Tree {
    //创建根节点属性
    private Node root;

    public Tree(){}
    public Tree(Node root) {
        this.root = root;
    }

    public Node getRoot() {
        return root;
    }

    //添加元素到这棵树上
    public void add(int value){
        Node node =new Node(value);
        if(root==null){
            root=node;
        }else{
            //如果有根节点，那么就将索引节点先放在根节点身上
            Node current=root;
            while(true){
                //判断value的值是否小于current对象的value值
                if(valuecurrent.getValue()){
                    //来到这里，说明node节点应该出现在current节点的右侧
                    //判断右子节点是否存在
                    if(current.getRightNode()==null){
                        current.setRightNode(node);
                        break;
                    }
                    current=current.getRightNode();
                }else{
                    break;
                }
            }

        }

    }
    //查询功能
    public Node get(int value){//根据节点内容，返回节点对象
        //定义一个节点对象变量，用来记录当前正在比较的节点对象
        Node currentNode=root;
        while(true){
            //比较value和current节点对象的value值是否相同
            if(value==currentNode.getValue()){
                return currentNode;
            }else if(value>currentNode.getValue()){
                currentNode=currentNode.getRightNode();
            }else{
                currentNode=currentNode.getLeftNode();
            }
            if(currentNode==null){
                 return null;
            }
        }
         }
    //遍历功能
    public void order(Node node){
        if(node==null)return;
        //先遍历Node的左节点
        order(node.getLeftNode());
        //将node对象的内容输出
        System.out.println(node.getValue());
        //遍历node对象的右节点
        order(node.getRightNode());
    }
}

讲解
思路详见代码注释：核心是遍历和将节点对象包装成一个属性

测试类

package com.company;

import java.util.Arrays;
import java.util.Scanner;

public class Demo {
    public static void main(String[] args) {
        int[] arr = {1, 5, 3, 8, 4};
        Tree tree = new Tree();


//遍历数组
        int a=0;
        for (int i = 0; i < arr.length; i++) {
            a++;
            //根据索引获得元素
            int value = arr[i];
            //将元素添加到树上
            tree.add(value);
        }

//查询二叉树
        Scanner sc =new Scanner(System.in);
        System.out.println("输入数据：");
        int value=sc.nextInt();
        if(tree.get(value)!=null){
            System.out.println("存在");
        }else{
            System.out.println("不存在");
        }
        tree.order(tree.getRoot());
    }
}

将代码复制到一个包下，分三类，即可实现二叉树哦~