java - 2 个二叉搜索树的交集

Question

嘿，所以我想创建一棵新树，它基本上是 2 个给定二叉搜索树的交集(交集的数学定义)。我有一种方法可以打印出树的特定级别的所有节点，我有一种方法可以找出树的深度。到目前为止，我正在粘贴我的工作，尽管它不完整而且我坚持使用logic.Help 将不胜感激。

    public static Bst<Customer> intersect (Bst<Customer> a, Bst<Customer> b){
    Bst<Customer> result = new Bst<Customer>();
    BTNode<Customer> cur1;
    BTNode<Customer> cur2;
    BTNode<Customer> cur3;
    cur1=a.root;
    cur2=b.root;
    cur3=result.root;
    int Resultdepth;
    if(a.maxDepth()<b.maxDepth())
        Resultdepth=a.maxDepth();
    else
        Resultdepth=b.maxDepth();

    if(cur1==null || cur2==null){ // Handeling the root case intially
        result = null;
    }
    else 
      cur3.item.set_account_id(cur1.item.get_accountid()+ cur2.item.get_accountid());

    cur1=cur1.left;
    cur2=cur2.left;
    cur3=cur3.left;       

    while(<some check>){

    }


    return result;

}


    public int maxDepth(){
        return mD(root);
    }

    int mD(BTNode<E> node){
       if (node==null) {
            return(0);
        }
       else {
            int lDepth = mD(node.left);
            int rDepth = mD(node.right);
            // use the larger + 1
            return(Math.max(lDepth, rDepth) + 1);
        }
    }

     // for printing the nodes at a particular level and giving the starting level
      public void PrintAt(BTNode<E> cur, int level, int desiredLevel) {
         if (cur == null) {
            return;
        }
         if (level == desiredLevel) {
             System.out.print(cur.item.toString() + "");
          }
         else {
             PrintAt(cur.left, level+1, desiredLevel);
             PrintAt(cur.right, level+1, desiredLevel);
          }
}

Answer 1

您必须同时“同步”地按顺序遍历两棵树。

我建议为您的类实现 Iterable 接口(interface)。然后你从两棵树中得到第一个值。如果它们相等，则将其放入新树中，并从两个迭代器中获取下一个值。如果不是，则使用较小的值迭代迭代器，直到您获得的值至少与另一个迭代器的最后一个值一样大。冲洗并重复。