2二叉搜索树路口 [英] Intersection of 2 binary search trees

问题描述

嘿，所以我想创建一个新的树基本上是2个给定的二叉搜索树路口（路口的数学定义）。我有打印出所有节点在树的特定级别的方法和我有可以找出tree.I的深度正在粘贴我的工作至今，虽然它是不完整的，我坚持同一种方法logic.Help将AP preciated。

 公共静态的Bst.DNA＆LT;客户＆GT;相交（BST＆LT;客户＆gt;一种，的Bst.DNA＆LT;客户＆GT; B）{
    BST＆LT;客户＆GT;结果=新的Bst.DNA＆LT;客户＆GT;（）;
    BTNode＆LT;客户＆GT; CUR1;
    BTNode＆LT;客户＆GT; cur2;
    BTNode＆LT;客户＆GT; cur3;
    CUR1 = a.root;
    cur2 = b.root;
    cur3 = result.root;
    INT Resultdepth;
    如果（a.maxDepth（）＆其中; b.maxDepth（））
        Resultdepth = a.maxDepth（）;
    其他
        Resultdepth = b.maxDepth（）;

    如果（CUR1 == NULL || cur2 == NULL）{// intially HANDELING根案
        结果= NULL;
    }
    其他
      cur3.item.set_account_id（cur1.item.get_accountid（）+ cur2.item.get_accountid（））;

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

    而（小于一些检测＆GT;）{

    }


    返回结果;

}


    公众诠释MAXDEPTH（）{
        返回MD（根）;
    }

    INT MD（BTNode＆LT; E＆gt;节点）{
       如果（节点== NULL）{
            回报（0）;
        }
       其他 {
            INT lDepth = MD（node.left）;
            INT rDepth = MD（node.right）;
            //使用更大+ 1
            返程（Math.max（lDepth，rDepth）+ 1）;
        }
    }

     //用于打印节点在特定的电平，并给予启动电平
      公共无效PrintAt（BTNode＆LT; E＆GT; CUR，INT水平，诠释desiredLevel）{
         如果（CUR == NULL）{
            返回;
        }
         如果（水平== desiredLevel）{
             System.out.print（cur.item.toString（）+）;
          }
         其他 {
             PrintAt（cur.left，等级+ 1，desiredLevel）;
             PrintAt（cur.right，等级+ 1，desiredLevel）;
          }
}
 

解决方案

您必须为了在同一时间同步遍历两个树和。

我会建议，以实现Iterable接口，为您的类。然后，你从两个树得到的第一个值。如果他们是平等的，把它放在新的树，以及来自迭代器获取下一个值。如果不是，循环迭代器具有较小值，直到你得到的价值是最不一样大与其他迭代器的最后一个值。冲洗和重复。

Hey, So I want to create a new tree which is basically the intersection (mathematical definition of intersection) of 2 given binary search trees. I have a method that prints out all the nodes at a particular level of the tree and I have a method that can find out the depth of the tree.I am pasting my work so far though it is incomplete and I'm stuck with the logic.Help will be appreciated.

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

解决方案

You have to traversal both trees in order at the same time and "in sync".

I'd suggest to implement the Iterable interface for your class. Then you get the first values from both trees. If they are equal, put it in the new tree, and get the next values from both iterators. If not, iterate the iterator with the smaller values until the value you get is as least as big as the last value from the other iterator. Rinse and repeat.

这篇关于2二叉搜索树路口的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！