java 中的树 (bst,maxHeap)

Question

此信息与树的类型有关。换句话说，你应该认识到这个信息金字塔的峰值（Max Heap），或二叉搜索树或两者的组合或它们的 none 没有。输入格式如下： (94,RR) (17,L) (36,RL) (51,R) (20,) (76,RRR) ()
输入格式给定对的树中的每个节点。第一个值表示节点的数量，第二个值表示必须导航才能到达此节点的根路径。 Node 没有办法代表树的根。有了这些信息，您应该能够键入 Identify the tree。比如树如下：

(94,RR) (17,L) (36,RL) (51,R) (20,) (76,RRR) ()

tree for this string

这棵树不是最大金字塔（最大堆），不是二叉搜索树，也不是它们的组合。

Entrance :
At the entrance you get a string that information is relevant to a tree. Each tree
With the statement (s) end. Entry Exit program ends.
Output:
You are one of the following phrases in your printed output.

1.BST: If the input tree is a binary search tree.
2.MaxHeap: If the tree is the maximum pyramid entrance.  
3.BST MaxHeap: If the combined input of binary search tree and the pyramid is the maximum.
4.Nothing: If there is none of the above.

**Sample Input:**
(94,RR) (17,L) (36,RL) (51,R) (20,) (76,RRR) ()
(94,) (59,LL) (61,RR) (53,LR) (79,L) (77,R) (15,RL) ()
(72,) (44,LR) (15,L) (2,LL) ()
Exit
**Sample Output:**
Nothing
MaxHeap
BST

现在我无法实现此 question.please 帮助的树。谢谢。

Answer 1

让我们用数组表示您的数据。我们可以通过对节点 i 的左子节点使用公式 2*i 对节点 i 的右子节点使用公式 2*i+1 从该数组构建二叉树。我还假设您已准备好自己的基本 BST。

1。如何确定给定的树是否为 BST： 按表示树位置的 String 的大小对输入进行排序。您的数据可以存储在一个名为 Pair 的 class 中，它存储一个表示值的整数和一个表示相对于根的位置的字符串。然后我们可以对其进行排序。以下是实现 class 和存储它的数组的方法：

class Pair
{
    int val;
    String pos;
    Pair(int val, String pos)
    {
        this.val=val;
        this.pos=pos;
    }
}

现在在 main 方法或任何地方，您可以开始构建树数组

int n;
//Take n which is number of nodes here
Pair[] input=new Pair[n];
for(int i=0;i<n;i++)
{
    input[i]=new Pair(*input value*, *input Position*);
}

Arrays.sort(input, new Comparator<Book>() //Sorts by the distance from start node
{
    @Override
    public int compare(Pair p1, Pair p2)
    {
        return p1.pos.length()-p2.pos.length();
    }
});

现在，只需在 BST 中创建一个名为 Insert(Node curr, int value, String where, int tillWhere)'. I am assuming again, that your BST has aNode` class 的递归方法，它存储数据以及左右子引用。

class Node //The node for the BSt should look something like this 
{
    Node left, right;
    int data;
    Node(Node left, Node right, int data)
    {
        this.left=left;
        this.right=right;
        this.data=data;
    }
}

<br>

//Method for inserting into the BST
void Insert(Node curr, int value, String where, int tillWhere)
{
    if(curr==null)
        curr=new Node(value);
    else
    {
        if(where.charAt(tillWhere)=='L')
            Insert(curr.left, value, where, tillWhere+1);
        else
            Insert(curr.right, value, where, tillWhere+1);
    }
}

现在，只需执行 BST 的 In-order traversal 并将结果存储在数组 Inorder 中。之后，如果数据按排序顺序排列，它将是 BST。

ArrayList<Integer> inOrder=new ArrayList<Integer>();

//Method
void Inorder(Node curr)
{
    if(curr!=null)
    {
        if(curr.left!=null)
            Inorder(curr.left);
        inOrder.add(curr.data); //Appending to list
        if(curr.right!=null)
            Inorder(curr.right);
    }
}

//Now after method call:
boolean isBST(ArrayList<Integer> inOrder)
{
    for(int i=1;i<=inOrder.size();i++)
        if(inOrder.get(i)<inOrder.get(i-1)) //Not possible in BST
            return false; 
    return true
}

如何确定给定的树是否是堆： 简单地满足属性父树 >= 它的子树。我们可以为此编写一个简单的递归解决方案：

boolean isHeap(int[] arr, int i, int n)// array storing the tree, initial postion , size
{
   if (i > (n - 2)/2) //Root
       return true;

   // If an internal node and is greater than its children, and
   // same is recursively true for the children
   if (arr[i] >= arr[2*i + 1]  &&  arr[i] >= arr[2*i + 2] &&
       isHeap(arr, 2*i + 1, n) && isHeap(arr, 2*i + 2, n))
       return true;

   return false;
}

您可以根据我上面给您的数据计算出您问题中的所有 4 个条件。希望对您有所帮助！

java 中的树 (bst,maxHeap)

tree (bst,maxHeap) in java

c#

java

tree

binary-tree

data-structures