如何从给定接口构建二叉树

Question

我需要构建一个简单的二叉树，其中包含Person元素。 人员必须按身高（从低到高）排序。如果有两个身高相同但性别不同的人，则应该是第一个。通常我们使用元素的左右节点。我怎样才能建立其他树？

这里是如何的人创建：

Person john = new Person() { 
    @Override 
    public boolean isMale() { 
     return true; 
    } 
    @Override 
    public int getID() { 
     return 1; 
    } 
    @Override 
    public int getHeight() { 
     return 175; 
    } 
}; 

这是一个接口：

public interface Person { 
    public int getID(); 
    public boolean isMale(); 
    public int getHeight(); 
} 

Answer 1

Full code with test class

Node.java

public class Node { 
    double key = 0; 
    Node parent = null, left = null, right = null; 
    IDancer dancer = null; 
    public Node(IDancer d) { 
     this.dancer = d; 
     String key = d.getHeight() + (d.isMale() ? "0." : "1.") + d.getID(); 
     this.key = Double.parseDouble(key); 
     System.out.println("new node: " + this.key); 
    } 
    public void copy(double key, IDancer d) { 
     this.dancer = d; 
     this.key = key; 
    } 
    public boolean hasRight() { 
     if (this.right != null) return true; 
     else return false; 
    } 
    public boolean hasLeft() { 
     if (this.left != null) return true; 
     else return false; 
    } 
    public boolean hasParent() { 
     if (this.parent != null) return true; 
     else return false; 
    } 
    public boolean isMale() { 
     if (this.dancer.isMale()) 
      return true; 
     else return false; 
    } 
} 

Dancers.java

import java.util.AbstractMap.SimpleEntry; 
import java.util.ArrayList; 
import java.util.List; 
public class Dancers implements IDancers { 
    public Tree tree = new Tree(); 
    @Override 
    public SimpleEntry<IDancer, IDancer> findPartnerFor(IDancer d) throws IllegalArgumentException { 
     if (!(d instanceof IDancer) || 
      (d.getHeight() <= 0) || 
      (d.getID() <= 0)) throw new IllegalArgumentException(); 
     IDancer partner = null; 
     tree.insert(d); 
     try {partner = (d.isMale()) ? tree.female(d) : tree.male(d); 
     } catch (NullPointerException n) {return null;} 
     if (partner != null) { 
      tree.remove(d); 
      tree.remove(partner); 
      System.err.println("Partner: " 
        + d.getID() 
        + (d.isMale() ? "M " : "F ") 
        + " For: " 
        + partner.getID() 
        + (partner.isMale() ? "M " : "F ")); 
      return new SimpleEntry<IDancer, IDancer>(d, partner); 
     } return null; 
    } 
    @Override 
    public List<IDancer> returnWaitingList() { 
     try {return tree.inorder(tree.root, new ArrayList<IDancer>()); 
     } catch(NullPointerException n) {return new ArrayList<IDancer>();} 
    } 
} 

Tree.java

import java.util.ArrayList; 
public class Tree { 
    public Node root = null; 
    public IDancer male(IDancer female) { 
     Node current = search(genKey(female)); 
     Node tmp = succsessor(current); 
     while (!tmp.isMale()) { 
      tmp = succsessor(tmp); 
     } return tmp.isMale() ? tmp.dancer : null; 
    } 
    public IDancer female(IDancer male) { 
     Node current = search(genKey(male)); 
     Node tmp = predecessor(current); 
     while (tmp.isMale()) { 
      tmp = predecessor(tmp); 
     } return tmp.isMale() ? null : tmp.dancer; 
    } 
    public Node minimum() {return minimum(this.root);} 
    private Node minimum(Node node) { 
     if (node.hasLeft()) 
      return minimum(node.left); 
     else return node; 
    } 
    public Node maximum() {return maximum(this.root);} 
    public Node maximum(Node node) { 
     if (node.hasRight()) 
      return maximum(node.right); 
     else return node; 
    } 
    public double genKey(IDancer d) { 
     return Double.parseDouble(d.getHeight() + (d.isMale() ? "0." : "1.") + d.getID()); 
    } 
    private Node search(double key, Node current) { 
     if (current.key == key) return current; 
     if (current.key > key 
       && current.hasLeft()) 
      return search(key, current.left); 
     if (current.key < key 
       && current.hasRight()) 
      return search(key, current.right); 
     return null; 
    } 
    public Node search(double key) {return search(key, this.root);} 
    public void insert(IDancer d) { 
     Node dancer = new Node(d); 
     Node y = null; 
     if (root == null) { 
      this.root = dancer; 
      return; 
     } 
     Node x = this.root; 
     while (x != null) { 
      y = x; 
      if (dancer.key < x.key) x = x.left; 
      else x = x.right; 
     } dancer.parent = y; 
     if (y == null) this.root = dancer; 
     else { 
      if (dancer.key < y.key) y.left = dancer; 
      else y.right = dancer; 
     } 
    } 
    public ArrayList<IDancer> inorder(Node node, ArrayList<IDancer> output) { 
     if (node.hasLeft()) 
      inorder(node.left, output); 
     output.add(node.dancer); 
     if (node.hasRight()) 
      inorder(node.right, output); 
     return output; 
    } 
    public void remove(IDancer d) { 
     Node z = search(genKey(d)); //toRemove 
     Node y = null; //replacer 
     Node x = null; 
     if (!z.hasLeft() || !z.hasRight()) 
      y = z; 
     else y = succsessor(z); 
     if (y.hasLeft()) 
      x = y.left; 
     else x = y.right; 
     if (x != null) 
      x.parent = y.parent; 
     if (!y.hasParent()) 
      this.root = x; 
     else if (y == y.parent.left) 
      y.parent.left = x; 
     else y.parent.right = x; 
     if (y != z) 
      z.dancer = y.dancer; 
     y = null; 
    } 
    private Node succsessor(Node n) { 
     if (n.hasRight()) 
      return minimum(n.right); 
     Node tmp = n.hasParent() ? n.parent : null; 
     while (tmp != null && n == tmp.right) { 
      n = tmp; 
      tmp = tmp.parent; 
     } return tmp; 
    } 
    private Node predecessor(Node n) { 
     if (n.hasLeft()) 
      return maximum(n.left); 
     Node tmp = n.hasParent() ? n.parent : null; 
     while (tmp != null && n == tmp.left) { 
      n = tmp; 
      tmp = tmp.parent; 
     } return tmp; 
    } 
}