Блог

Пример:

Ввод Образца:

6

6 10 20 1 51 43

1 10 6 20 43 51

Пример Вывода:

20 6 51 131 94 36

Ввод Образца:

5

40 60 30 20 50

50 20 30 60 40

Пример Вывода:

100 40 200 150 130

Во входных данных первое значение 6-это размер дерева. Значения во второй строке соответствуют обходу по порядку данного двоичного дерева, а последняя строка соответствует обходу по предварительному заказу данного двоичного дерева.

Вывод-это обход после заказа нового дерева двоичного поиска, которое должно быть построено со значениями узлов, разделенными пробелами.

Ниже приведен мой код, но вывод идет неправильно .

 import java.util.Scanner;
import java.util.Arrays;
import java.util.TreeSet;
import java.util.Iterator;
import java.util.Set;
class Node
{
    int value;
    Node leftchild, rightchild;

    Node(int item)
    {
        value = item;
        leftchild = rightchild = null;
    }
}

class BinaryTree
{
    Node root;
    static int preIndex = 0;
    static int index=0;

    Node constructTree(int in[], int pre[], int inStrt, int inEnd)
    {
        if (inStrt > inEnd)
            return null;

        Node tNode = new Node(pre[preIndex  ]);

        if (inStrt == inEnd)
            return tNode;

        int inIndex = search(in, inStrt, inEnd, tNode.value);

        tNode.leftchild = constructTree(in, pre, inStrt, inIndex - 1);
        tNode.rightchild = constructTree(in, pre, inIndex   1, inEnd);


        return tNode;
    }

    int search(int arr[], int strt, int end, int value)
    {
        int i;
        for (i = strt; i <= end; i  )
        {
            if (arr[i] == value)
                return i;
        }
        return i;
    }

    int sumBinaryTree(Node node)
    {
        // Write the logic to recursively create Binary Tree consisting of sum of all its children
        if (node == null)
            return 0;

        // Store the old value
       int old_val = node.value;


        // Recursively call for left and right subtrees and store the sum
        // as new value of this node
       node.value = sumBinaryTree(node.leftchild)   sumBinaryTree(node.rightchild);



        // Return the sum of values of nodes in left and right subtrees
        // and old_value of this node
       return node.value   old_val;


    }

    void printPostorder(Node node)
    {
        if (node == null)
            return;

        // first recur on left subtree
        printPostorder(node.leftchild);

        // then recur on right subtree
        printPostorder(node.rightchild);

        // now deal with the node
        System.out.print(node.value   " ");
    }

    void inOrder(Node node, int array[])
    {
        if (node == null)
            return;
        inOrder(node.leftchild, array);
        array[index  ] = node.value;
        inOrder(node.rightchild, array);

    }

    Node ArrayToBST(int arr[], int start, int end) {
        // Write logic to convert the array representing Binary Tree to Binary Search Tree
        if (start > end) {
            return null;
        }

        /* Get the middle element and make it root */
        int mid = (start   end) / 2;
        Node node = new Node(arr[mid]);

        /* Recursively construct the left subtree and make it
         left child of root */
        node.leftchild = ArrayToBST(arr, start, mid - 1);

        /* Recursively construct the right subtree and make it
         right child of root */
        node.rightchild = ArrayToBST(arr, mid   1, end);

        return node;
    }
}
class Source{

    // driver program to test above functions
    public static void main(String args[])
    {
        Scanner scanner = new Scanner(System.in);
        int len = scanner.nextInt();
        int in[] = new int[len];
        int pre[] = new int[len];
        for(int i=0;i<len;i  ){
            in[i] = scanner.nextInt();
        }
        for(int i=0;i<len;i  ){
            pre[i] = scanner.nextInt();
        }
        BinaryTree tree = new BinaryTree();
        Node root = tree.constructTree(in, pre, 0, len - 1);

        tree.sumBinaryTree(root);
        int inSumTree[] = new int[len];
        for(int i=0;i<=inSumTree.length;i  )
        {
            System.out.println(inSumTree[i]);
        }

        tree.inOrder(root, inSumTree);
        Arrays.sort(inSumTree);
        Node bstRoot = tree.ArrayToBST(inSumTree, 0, len-1);
        tree.printPostorder(bstRoot);

    }
}
 

node.value = сумбинарное дерево(node.leftchild) сумбинарное дерево(node.rightchild);

Вам не хватает знака , вот и все!! Также нет необходимости добавлять дополнительную переменную для old_val. Просто верните значение node.value..

Попробуйте этот код sumBinaryTree(Node node) , и он должен сработать.

 int sumBinaryTree(Node2 node)
    {
       
        if(node==null)
            return 0;

        node.value  = sumBinaryTree(node.leftchild)   
                      sumBinaryTree(node.rightchild);

        return node.value ;

    }