java实现二叉查找树

定义

二叉查找树具备以下特征：

• 左子树上所有结点的值均小于等于它的根结点的值。
• 右子树上所有结点的值均大于等于它的根结点的值。
• 左、右子树也是二叉查找树

java实现

下面，我们来利用java实现一棵二叉查找树：

实现：

首先要建立一个节点类Node：

代码块1

package Tree;

/**
 * 节点类
 * @author javadaodechengxuyuan
 *
 */
public class Node {
    private long value;
    private Node leftNode;//节点下面的左节点
    private Node RightNode;//节点下面的右节点
    
    //构造器
    public Node(long value){
        this.value=value;
    }

    public long getValue() {
        return value;
    }
    public void setValue(long value) {
        this.value = value;
    }
    public Node getLeftNode() {
        return leftNode;
    }
    public void setLeftNode(Node leftNode) {
        this.leftNode = leftNode;
    }
    public Node getRightNode() {
        return RightNode;
    }
    public void setRightNode(Node rightNode) {
        RightNode = rightNode;
    }
}

这是二叉树类，就是这个类用来操作节点类的：

代码块2

package Tree;
/**
 * @author javadaodechengxuyuan
 * 二叉树：每个节点有最多两个分叉，
 * 分别作为父节点的左值和右值，遵循左小右大的规则进行分叉
 */
public class Tree {
    private Node root;
    private Node current;
    private Node parent;
    /**
     * @author javadaodechengxuyuan
     * 为一颗二叉树添加节点
     */
    public void insert(long value){//为二叉树插入新的节点
        //创建新的节点
        Node newNode=new Node(value);
        
        //创建完后就该考虑把这个节点放在哪里了，下面这些代码就是用来判断将这个节点放在哪里的
        if(root==null){
            this.root=newNode;//如果root为空，那么第一次调用添加时应给root初始化
        }else{
            this.current=root;//初始化current
            while(true){//进入死循环，一直等到给newNode找到合适的位置时进行终止死循环
                if(this.current.getValue()>value){//比root小，放在左侧
                    this.parent=this.current;//让parent一直保留本次的current
                    this.current=this.current.getLeftNode();
                    if(this.current==null){//如果当前的左值为空，那么就终止循环并赋值给这个左值
                        this.parent.setLeftNode(newNode);//将这个新节点放在这个位置
                        return;//最终找到合适位置，死循环终止
                    }
                }else{//比root大，放在右侧
                    this.parent=this.current;//让parent一直保留本次的current
                    this.current=this.current.getRightNode();//将当前的节点重新赋值给下一次需要比较的节点
                    if(this.current==null){//如果当前的右值为空，那么就终止循环并赋值给这个左值
                        this.parent.setRightNode(newNode);//将这个新节点放在这个位置
                        return;//最终找到合适位置，死循环终止
                    }
                }
            }
        }    
    }

    public Node getRoot() {
        return root;
    }

    public void setRoot(Node root) {
        this.root = root;
    }
}

这是测试类：

代码块3

package Tree;
/**
 * 测试类
 * @author javadaodechengxuyuan
 *
 */
public class Test {
    public static void main(String args[]){
        Tree t=new Tree();
        t.insert(10);//根节点
        t.insert(20);
        t.insert(15);
        t.insert(9);
        t.insert(35);
        System.out.print(t.getRoot().getValue()+"、");//第0层：根节点
        System.out.print(t.getRoot().getLeftNode().getValue()+"、");//第一层左值
        System.out.print(t.getRoot().getRightNode().getValue()+"、");//第一层右值
        System.out.print(t.getRoot().getRightNode().getLeftNode().getValue()+"、");//第二层左值
        System.out.print(t.getRoot().getRightNode().getRightNode().getValue());//第二层右值
        //输出结果应为：10、9、20、15、35
    }
}

输出结果为：

10、9、20、15、35