Слияние двух бинарных деревьев - PullRequest
Новая
       22

Слияние двух бинарных деревьев

0 голосов
/ 03 июля 2019

Я хочу объединить дерево с другим деревом, т.к.Если есть перекрывающиеся данные, я хочу добавить их вместе.Это мой код прямо сейчас.Я не понимаю, как сделать эту функцию слияния только с параметром т.Обычно слияние не имеет двух параметров? 

public class TreeFunctions {

   private TreeNode root;

   public TreeFunctions(TreeNode root) {
        this.root = root;
   }

   public TreeNode merge(TreeNode t) {
        TreeNode curr = this.root;
        if (curr == null) {
            return t;
        }

        if (t == null) {
            return curr;
        }

        curr.data += t.data;
        curr.left = merge(t.left);
        curr.right = merge(t.right);
        return curr;
   }
}

public class TreeNode{
    TreeNode left;
    TreeNode right;
    int data;

    public TreeNode(int data) {
        this.data = data;
    }
    public TreeNode(int data, TreeNode left, TreeNode right) {
        this.data = data;
        this.left = left;
        this.right = right;
    }

    public static String inOrder(TreeNode a) {
        if(a == null) return "";
        else return inOrder(a.left).trim() + " " + a.data + " " + inOrder(a.right).trim();
    }
}

РЕДАКТИРОВАТЬ Мои тесты на слияние: 

public void testMerge2() {
        TreeFunctions c = new TreeFunctions(new TreeNode(5, new TreeNode(2), null));
        TreeNode d = new TreeNode(2, new TreeNode(2), new TreeNode(1));
        TreeNode res2 = c.merge(d);
        assertEquals(TreeNode.inOrder(res2).trim(), "4 7 1");
    }

public void testMerge3() {
        TreeFunctions c = new TreeFunctions(new TreeNode(5, new TreeNode(2), null));
        TreeNode res2 = c.merge(null);
        assertEquals(TreeNode.inOrder(res2).trim(), "2 5");
    }

public void testMerge4() {
        TreeFunctions c = new TreeFunctions(new TreeNode(1, new TreeNode(2, new TreeNode(5), null), null));
        TreeNode res2 = c.merge(new TreeNode(1, null, new TreeNode(2, null, new TreeNode(5))));
        assertEquals(TreeNode.inOrder(res2).trim(), "5 2 2 2 5");
    }

1 Ответ

0 голосов
/ 03 июля 2019

Я отредактировал свой ответ в соответствии с вашими ответами. Я считаю, что это то, что вы хотите. Пожалуйста, попробуйте и дайте мне знать.

В коде функция понижается на один уровень как для t1, так и для t2, так что слияние всегда происходит на одном и том же уровне и с одной и той же стороны (слева-слева / справа-справа). 

 public TreeNode merge(TreeNode t) {
        TreeNode curr = this.root; 
        merge2(curr,t);
        return curr;
   }
   public  void merge2(TreeNode t1,TreeNode t2) {
        if(t2==null)
            return;
        t1.data += t2.data;
        if(t2.left!=null)
        {
            if(t1.left==null)
                t1.left = new TreeNode(0);
            merge2(t1.left,t2.left);
        }
        if(t2.right!=null)
        {
            if(t1.right==null)
                t1.right = new TreeNode(0);
            merge2(t1.right,t2.right);
        }

   }
...