在java中的树数据结构中插入字符串 [英] Inserting strings in tree data structure in java
问题描述
Hello I have got this tree data structure implementation in java ,
however the problem I am facing is that somehow the add method does
seem to me that it is not working properly .
When I for example use " public void CreateFromDefinition(String definition) "
and put in for example " (A(B(E(K),F),C(G(L,M)),D(H,I(N),J))) " , then when I use
System.out.println(y.GetListDefinition());
then what I get for the output is =
name : (A
Exception in thread "main" java.lang.NullPointerException
at ads2.ADS2Tree.CreateFromDefinition(ADS2Tree.java:72)
at ads2.Main.main(Main.java:90)
Java Result: 1
有人可以帮我解决这个问题吗?
谢谢
------------------------------
这是树和节点的代码 -
树的代码:
Can anybody please help me solve this problem ?
Thank you
------------------------------
Here is the code for the tree and node -
Code for the tree :
package ads2;
/*
* This class defines the top-level tree data structure.
*/
public class ADS2Tree
{
// Default Constructor
public ADS2Tree()
{
}
// -------------
public ADS2TreeNode leftNode()
{return root.left;}
public ADS2TreeNode rightNode() {return root.right;}
public static int getNodeValue()
{
return ADS2TreeNode.nodeValue;
}
private ADS2TreeNode root;
// Takes a string input of a list structure that defines a tree
// e.g. definition="(A(B(E(K),F),C(G(L,M)),D(H,I(N),J)))");
// and sets up the internal tree structure to represent this structure
// Any previous tree structure is overridden when this method is called
public void CreateFromDefinition(String definition)
{
int startofname = 0;
ADS2TreeNode current = new ADS2TreeNode (definition) ; // "dummy"
root = current ;
//TreeNode current = null;
for (int i = 0; i<definition.length(); i++)
{
char val = definition .charAt(i);
if ( val == '(' || val == ')' || val == ',')
{
if (startofname != i)
{
String name = definition.substring(startofname,i);
System.out.println("name : " + name);
ADS2TreeNode node = new ADS2TreeNode (name);
current.AddChild(node);
if (val == '(')
{
current = node ;
}
else if (val == ')')
{
current = current.GetParent();
}
startofname = i + 1;
}
root = root.GetChild(0);
// current = current ;
}
}
}
// Returns a String containing the list format of the tree in the following format:
// NodeName(Child1,Child2,...Childn)
// For example: (A(B(E(K),F),C(G(L,M)),D(H,I(N),J)))
public String GetListDefinition()
{
return "(" + root.toString() + " ) " ;
// return "Implement list output of this tree, for example: (A(B(E(K),F),C(G(L,M)),D(H,I(N),J)))";
}
// Returns a String contain the pre-order enumation of the tree data structure
// The return type should just contain the name of the treenodes, separated by commas
// For example: A,B,C,D,E,F,G
public String GetPreOrder(ADS2TreeNode root)
{
GetPreOrder(root.left);
GetPreOrder(root.right);
if (root == null)
return "";
String result = root.data;
if (root.left != null)
result += GetPreOrder(root.left);
if (root.right != null)
result += GetPreOrder(root.right);
return result;
}
public String GetInOrder()
{
return null;
}
public String GetPostOrder()
{ if (root == null)
return "";
String result = "";
if (root.left != null)
result += GetPreOrder(root.left);
if (root.right != null)
result += GetPreOrder(root.right);
result += root.data;
return result;
}
private void GetBreadthFirstOrder(ADS2TreeNode root)
{
GetBreadthFirstOrder(root);
}
public String GetBreadthFirstOrder()
{
if (root == null)
return root.GetData();
System.out.print(root.data + " ");
GetBreadthFirstOrder(root.left);
GetBreadthFirstOrder(root.right);
return null;
}
public int GetTreeDegree()
{
return GetTreeHeight(root);
}
public int GetTreeHeight()
{
if (root==null)
return 0;
int x = GetTreeHeight(root.left);
int y = GetTreeHeight(root.right);
return (x>y?x:y)+1;
}
public int GetTreeNodeCount()
{
return GetTreeNodeCount(root);
}
private int GetTreeNodeCount(ADS2TreeNode p)
{
if(p == null) return 0;
else
if(p.left == null && p.right == null) return 1;
else
return GetTreeNodeCount(p.left) + GetTreeNodeCount(p.right);
}
public String toString()
{
return super.toString();
}
private int GetTreeHeight(ADS2TreeNode left) {
throw new UnsupportedOperationException("Not supported yet.");
}
}
// ----------------------------- ---------------------------
以下是节点的代码:
// --------------------------------------------------------
Here is the code for node :
package ads2;
public class ADS2TreeNode
{
public String data; // data about this node
private ADS2TreeNode parent; // parent node
public ADS2TreeNode child[];
public int noOfChildren;
private final int maxChildren = 10;
// add in variables to hold one or more child nodes
public ADS2TreeNode right; // right node
public ADS2TreeNode left;
public static int nodeValue;
public ADS2TreeNode p;
// Add required constructors
public ADS2TreeNode()
{
child = new ADS2TreeNode[maxChildren];
noOfChildren = 0;
}
public ADS2TreeNode(String definition) {
child = new ADS2TreeNode[maxChildren];
noOfChildren = 0;
data = definition;
}
public String GetData()
{
return data;
}
public void SetData(String data)
{
this.data=data;
}
// returns the number of children this node has
public int GetNoOfChildren()
{
return noOfChildren;
}
public String toString()
{
String res = data;
if ( noOfChildren != 0)
{
res += " ( " + child[0];
for ( int i = 1; i < noOfChildren; i++)
res+= "," + child[i];
res+= ")";
}
return res;
}
void AddChild(ADS2TreeNode node)
{
// Checking whether there is enough space
if(noOfChildren < maxChildren) {
// Can add child
node.parent = this;
child[noOfChildren] = node;
noOfChildren++;
}
// else { cannot add child }
}
ADS2TreeNode GetParent() {
return parent;
}
ADS2TreeNode GetChild(int i) {
return child[i];
}
}
推荐答案
第一个问题是你设置root
到null
并尝试使用它;
First problem is that you set theroot
tonull
and try to use that;
root = root.GetChild(0);
您需要确保在 root
<之后不进行处理code>空。一种方法可能是修复 for -loop;
You need to make sure you don't keep processing after root
is null
. One way might be by fixing the for-loop;
for (int i = 0; i<definition.length() && root != null; i++)
但即便如此,因为你让 root
更改 CreateFromDefinition
当方法完成时,它仍然是 null
,因为 GetListDefinition
调用 root.toString()
它会失败。
你想要的确保 root
成员始终指向root,实现此目的的一种懒惰方法是将 root
设置为创建初始节点;
But even then, as you let root
change inside CreateFromDefinition
it will still be null
when the method completes, and since GetListDefinition
calls root.toString()
it will fail.
You'll want to make sure the root
member always points to the root, a lazy way of achieving this would be to set root
to the initial node created;
int startofname = 0;
ADS2TreeNode current = new ADS2TreeNode (definition) ; // "dummy"
root = current ;
ADS2TreeNode r = current;
然后,在该方法结束时,设置 root = r;
。
希望这会有所帮助,
Fredrik
then, at the end of that method, set root=r;
.
Hope this helps,
Fredrik
这篇关于在java中的树数据结构中插入字符串的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!