java数据结构

链表

线性表，但不会按线性的顺序存储数据，而是每一个节点里存着下一个节点的指针
链表和数组都是线性数据结构

• 数组不便于做删除、插入，但遍历查找简单，有固定长度
• 链表适合插入、删除，不宜过长，否则导致遍历性能下降

public class LinkedList{
    public static void main(String[] args) {
        NodeManager nm = new NodeManager();
        for(int i=0;i<=5;i++){
            nm.addData(i+1);
        }
        nm.deleteData(3);
        boolean a = nm.updateData(4, 7);
        nm.showData();
        boolean b = nm.findData(7);
        System.out.println(a);
        System.out.println(b);
        nm.insertData(3,20);
        nm.showData();
    }
}

class NodeManager{
    public Node root;//根节点
    private int currentIndex=0;//节点位置
    //提供给外部访问的接口
    public void addData(int data){
        if(root == null){
            root = new Node(data);
        }else{
            root.addData(data);
        }
    }
    public void deleteData(int data){
        if(root==null){
            System.out.println("无节点可删除");
        }else if(root.getData() == data){
            root = root.next;
            System.out.println("删除成功");
        }else{
            root.deleteData(data);
        }
    }
    public boolean findData(int data){
        if(root==null)return false;
            if(root.getData()==data){
                return true;
            }else{
                return root.findData(data);
            }
    }
    public boolean updateData(int oldData,int newData){
        if(root==null)return false;
        if(root.getData()==oldData){
            root.setData(newData);
            return true;
        }else{
            return root.updateData(oldData,newData);
        }
    }
    public void insertData(int index,int newData){
        //index为插入位置，在其前插入
        if(index<0)return;
        currentIndex = 0;
        if(index==currentIndex){
            Node newNode = new Node(newData);
            newNode.next = root;
            root = newNode;
        }else{
            root.insertData(index,newData);
        }
    }
    public void showData(){
        if(root==null){
            System.out.println("当前数据为空");
        }else{
            System.out.print(root.getData()+"->");
            root.showData();
        }
    }
    private class Node{
        private int data;//存储的数据
        private Node next;//存储下一个节点
        public Node(){}
        public Node(int data){
            this.data = data;
        }
        public void setData(int data){
            this.data = data;
        }
        public int getData(){
            return this.data;
        }
        //添加节点
        public void addData(int data){
            if(next==null){
                next = new Node(data);
            }else{
                next.addData(data);
            }
        }
        //删除节点
        public void deleteData(int data){
            if(this.next!=null){
                if(this.next.data==data){
                    this.next = this.next.next;
                }else{
                    this.next.deleteData(data);
                }
            }  
        }
        //查找节点
        public boolean findData(int data){
            if(this.next!=null){
                if(this.next.data==data){
                    return true;
                }else{
                    return this.next.findData(data);
                }
            }
            return false;
        }
        //更改节点
        public boolean updateData(int oldData,int newData){
            if(this.next!=null){
                if(this.next.data==oldData){
                    this.next.data = newData;
                    return true;
                }else{
                    return this.next.updateData(oldData, newData);
                }
            }
            return false;
        }
        //插入节点
        public void insertData(int index,int newData){
            currentIndex++;
            if(index==currentIndex){
                Node newNode = new Node(newData);
                newNode.next = this.next;
                this.next = newNode;
            }else{
                this.next.insertData(index, newData);
            }
        }
        //显示所有节点
        public void showData(){
            if(next!=null){
                System.out.print(next.data+"->");
                next.showData();
            }
        }
    }
}

二叉树

public class BinaryTreeDemo {
    public static void main(String[] args) {
        BinaryTree bt = new BinaryTree();
        bt.add(2);
        bt.add(3);
        bt.add(1);
        bt.add(5);
        bt.add(3);
        bt.show();
    }
}

//二叉树
class BinaryTree {

    private Node root;

    // 外部提供使用接口
    public void add(int data) {
        if (this.root == null) {
            root = new Node(data);
        } else {
            root.addNode(data);
        }
    }

    public void show() {
        if(root == null) {
            System.out.println("数据不存在");
        }else {
            root.showNode();
        }
    }

    private class Node {
        private int data;
        private Node left;
        private Node right;

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

        // 添加操作
        private void addNode(int data) {
            if (this.data >= data) {
                if (this.left == null) {
                    this.left = new Node(data);
                } else {
                    this.left.addNode(data);
                }
            } else {
                if (this.right == null) {
                    this.right = new Node(data);
                } else {
                    this.right.addNode(data);
                }
            }
        }

        // 显示操作
        //中序遍历
        private void showNode() {
            if(this.left != null) {
                this.left.showNode();
            }
            System.out.print(this.data+"->");
            if(this.right != null) {
                this.right.showNode();
            }
        }
    }

}