tree (bst,maxHeap) in java
本文关键字:in java maxHeap bst tree | 更新日期: 2023-09-27 18:26:36
此信息与树的类型有关。换句话说,你应该认识到这个信息金字塔的峰值(最大堆),或二进制搜索树或两者的组合,或两者都没有。输入格式如下:(94,RR)(17,L)(36,RL)(51,R)(20,)(76,RRR)()
输入树中给定对的每个节点的格式。第一个值表示Node的数量,第二个值表示必须导航才能到达该节点的根路径。节点无法表示树的根。有了这些信息,您应该能够键入"识别树"。例如,树如下:
(94,RR) (17,L) (36,RL) (51,R) (20,) (76,RRR) ()
该字符串的树
这个树不是最大金字塔(maxHeap),不是二进制搜索树,也不是它们的组合。
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
现在我无法实现这个问题的树。请提供帮助。非常感谢。
让我们在一个数组中表示您的数据。我们可以通过对节点i
的左子节点使用公式2*i
,对节点i
的右子节点使用表达式2*i+1
,从该数组构造二叉树。我还假设你已经准备好了自己的基本BST。
1.如何确定给定的树是否是BST:根据代表树位置的String
的大小对输入进行排序。您的数据可以存储在一个名为Pair
的类中,该类存储一个表示值的整数和一个表示相对于根的位置的字符串。然后我们可以对它进行排序。下面是如何实现类和存储它的数组:
class Pair
{
int val;
String pos;
Pair(int val, String pos)
{
this.val=val;
this.pos=pos;
}
}
现在在主方法或任何地方,您都可以开始构建树阵列
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 a
Node`类的递归方法,该方法存储数据以及左右子引用
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个条件。我希望这能有所帮助!