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();
			}
		}
	}

}