Java实现C/S架构的聊天系统

package Base; import java.nio.channels.SelectionKey; import java.nio.channels.SocketChannel; public class Tree { public Node root; //二叉树的：中序遍历 public void inOrder(Node temp){ if(temp!=null){ inOrder(temp.leftChild); System.out.println("--中序--"+temp.ID); inOrder(temp.rightChild); } } //二叉树的：先序遍历 public void PreOrder(Node temp){ if(temp!=null){ System.out.println("--先序--"+temp.ID); PreOrder(temp.leftChild); PreOrder(temp.rightChild); } } public synchronized boolean find_ThisID(int this_id){ Node temp = root; if(temp!=null){ while(temp!=null){ if(temp.ID==this_id){ return false; } if(this_id<temp.ID){ temp = temp.leftChild; continue; } if(this_id>temp.ID){ temp = temp.rightChild; continue; } } } return true; } public synchronized boolean del_thisID(int this_id){ remove(this_id); return true; } public synchronized Node find_This_userID(int this_id){ Node temp = root; if(temp!=null){ while(temp!=null){ if(temp.ID==this_id){ return temp; } if(this_id<temp.ID){ temp = temp.leftChild; continue; } if(this_id>temp.ID){ temp = temp.rightChild; continue; } } } return null; } public synchronized Area_Buffer find_This_ID(int this_id){ Node temp = root; if(temp!=null){ while(temp!=null){ if(temp.ID==this_id){ return temp.buffer; } if(this_id<temp.ID){ temp = temp.leftChild; continue; } if(this_id>temp.ID){ temp = temp.rightChild; continue; } } } return null; } public synchronized SelectionKey find_To_ID_key(int id){ Node temp = root; if(temp!=null){ while(temp!=null){ if(temp.ID==id){ return temp.key; } if(id<temp.ID){ temp = temp.leftChild; continue; } if(id>temp.ID){ temp = temp.rightChild; continue; } } } return null; } public synchronized SocketChannel find_To_ID(int id){ Node temp = root; if(temp!=null){ while(temp!=null){ if(temp.ID==id){ return temp.socket; } if(id<temp.ID){ temp = temp.leftChild; continue; } if(id>temp.ID){ temp = temp.rightChild; continue; } } } return null; } public synchronized Area_Buffer findSocket(SocketChannel s){ return findSocket(root,s).buffer; } public synchronized int find_This_ID(SocketChannel s){ return findSocket(root,s).ID; } public Node findSocket(Node temp,SocketChannel s){ if(temp!=null){ if(temp.socket.equals(s)){ return temp; } Node ten = findSocket(temp.leftChild,s); if(ten.socket.equals(s)){ return ten; } Node tenn = findSocket(temp.rightChild,s); if(tenn.socket.equals(s)){ return tenn; } } return null; } //计算高度 public int hi(Node t){//三目运算符 如果传出节点为空 则返回-1，否则返回此节点的高度 return t == null ? -1 : t.height; } public synchronized void insert(int element,SocketChannel s,SelectionKey k){ //保存整棵树 root = insert(element,s, root,k); } public Node insert(int data,SocketChannel s, Node rot,SelectionKey k){ if(rot==null){//若传入节点为空，则返回当前节点 return new Node(data , s,k); } if(data==rot.ID){ System.out.println("tree----已存在！");//用于测试 return null; } //用当前值与根节点的值进行比较，创建过程与二叉排序树的过程相同，平衡树的创建只是多了旋转操作 if(data<rot.ID){ rot.leftChild=insert(data,s,rot.leftChild,k); if(hi(rot.leftChild)-hi(rot.rightChild)==2){ /* * 若插入结点在根节点的左侧，则用距离插入点最近的根节点，因为插入在左侧 所以左侧的树的高度也许会升高 * 所以用最近根节点的左子树的高度减去其右子树的高度，若右子树的高度为0则右子树的高度返回-1；否则返回右子树的高度 * 因为插入之前的整棵树是平衡的 若插入左子树之后，以距离插入节点最近的根节点的高度会+1，再加上平衡树的性质（根节点左右子树的高度差的绝对值不会超过1） * 因此 插入节点之后 若右子树与右子树的差为2的话 ，则说明树的平衡被打破，变得不平衡 */ if(data<rot.leftChild.ID){ /*若树不平衡，则判断距离插入节点最近的根节点的左侧不平衡，还是其右侧不平衡， *若左侧不平衡则只需要以此根节点右旋转一次即可达到平衡 */ rot=R_R(rot); }else{//右侧不平衡，则需要以此根节点先左旋转一次。然后再右旋转一次即可 rot=L_R(rot); } } }else if(data>rot.ID){//原理与右侧相对 rot.rightChild=insert(data,s, rot.rightChild,k); if(hi(rot.rightChild)-hi(rot.leftChild)==2){ if(data<rot.rightChild.ID){ rot = R_L(rot); }else{ rot=L_L(rot); } } } rot.height=Math.max(hi(rot.leftChild), hi(rot.rightChild))+1; return rot; } //左高单次右旋转 public Node R_R(Node node){ Node left=node.leftChild; node.leftChild=left.rightChild; left.rightChild=node; //重新计算node的高度，并给高赋值 node.height=Math.max(hi(node.leftChild),hi(node.rightChild))+1; //重新计算left节点的高度，并给高赋值 left.height=Math.max(hi(left.rightChild), node.height)+1; //经过旋转之后，原先node为根节点传入 此时根节点为right节点 return left;//返回新的父节点 } //右高单次左旋转 public Node L_L(Node node){ Node right=node.rightChild; node.rightChild=right.leftChild; right.leftChild=node; //重新计算node的高度，并给高赋值 node.height=Math.max(hi(node.leftChild),hi(node.rightChild))+1; //重新计算right节点的高度，并给高赋值 right.height=Math.max(hi(right.rightChild), node.height)+1; //经过旋转之后，原先node为根节点传入 此时根节点为right节点 return right; } //左高两次旋转 先左后右旋转 public Node L_R(Node node){//以两次旋转之后，返回新的根节点 Node temp=L_L(node.leftChild); node.leftChild=temp; return R_R(node); } //右高两次旋转先右后左旋转 public Node R_L(Node node){ Node temp = R_R(node.rightChild); node.rightChild=temp; return L_L(node); } public void remove(int element){ root = remove(element, root); } public Node remove(int x, Node t){ if(t == null) return null; if(x < t.ID){ t.leftChild = remove(x, t.leftChild); //完了之后验证该子树是否平衡 if(t.rightChild != null){ //若右子树为空，则一定是平衡的，此时左子树相当对父节点深度最多为1, 所以只考虑右子树非空情况 if(t.leftChild == null){ //若左子树删除后为空，则需要判断右子树 if(hi(t.rightChild)-t.height == 2){ Node k = t.rightChild; if(k.rightChild != null){ //右子树存在，按正常情况单旋转 System.out.println("-----------------11111"); t = L_L(t); }else{ //否则是右左情况，双旋转 System.out.println("---------------22222"); t = R_L(t); } } }else{ //否则判断左右子树的高度差 //左子树自身也可能不平衡，故先平衡左子树，再考虑整体 Node k = t.leftChild; //删除操作默认用右子树上最小节点补删除的节点 //k的左子树高度不低于k的右子树 if(k.rightChild != null){ if(hi(k.leftChild)-hi(k.rightChild) == 2){ Node m = k.leftChild; if(m.leftChild != null){ //左子树存在，按正常情况单旋转 System.out.println("---