将节点插入树广度优先
Inserting nodes into a tree Breadth First
我正在尝试生成具有广度优先插入形式的树。
我试图通过生成一个列表来做到这一点,其中包含树中所有元素的广度优先顺序。然后在我的 insertNode 方法中,我使用名为 needsChildren() 的方法检查节点是否需要子节点,如果需要,我将要插入的节点添加到可能的最左侧位置的树中。
如果我打电话
插入节点(10)
插入节点(8)
插入节点(20)
插入节点(5)
插入节点(29)
插入节点(50)
生成的树应该是
10
8 20
5 29 50
等等...
此解决方案无效,我不太确定原因。我认为可能是我的 generateList 没有正常工作,但我已经检查了最后打印的列表,它似乎是正确的。
是否有更好的方法来执行此操作,或者我的代码中是否存在我找不到的问题。非常感谢任何帮助。
这是我的树节点Class:
private static class TreeNode<T> {
public T data;
public TreeNode<T> left;
public TreeNode<T> right;
public TreeNode(T d) {
data = d;
left = null;
right = null;
}
}
我的 insertNode 方法:
public void insertNode(T d) {
if(root==null){
root= new TreeNode<T>(d);
}
genList(root);
if(needsChildren(nodesThatNeedChildren.get(0))){
if(nodesThatNeedChildren.get(0).left==null){
nodesThatNeedChildren.get(0).left= new TreeNode<T>(d);
}else{
nodesThatNeedChildren.get(0).right= new TreeNode<T>(d);
}
}else{
while(!needsChildren(nodesThatNeedChildren.get(0))){
nodesThatNeedChildren.remove(0);
}
System.out.println(nodesThatNeedChildren.get(0).data);
if(nodesThatNeedChildren.get(0).left==null){
nodesThatNeedChildren.get(0).left = new TreeNode<T>(d);
}else{
nodesThatNeedChildren.get(0).right = new TreeNode<T>(d);
}
}
}
我检查节点是否需要子节点的方法:
public boolean needsChildren(TreeNode<T> node){
if(node.left==null || node.right ==null){
return true;
}
return false;
}
以及我生成树中所有节点列表的方法:
public void genList(TreeNode<T> root) {
//generate new List each time
nodesThatNeedChildren.clear();
nodesThatNeedChildren.add(root);
//generate new Queue each time genList is called
tempQueue.clear();
tempQueue.add(root);
while(!tempQueue.isEmpty()){
TreeNode<T> node = tempQueue.remove(0);
if(node.left != null){
tempQueue.add(node.left);
nodesThatNeedChildren.add(node.left);
}
if(node.right != null){
tempQueue.add(node.right);
nodesThatNeedChildren.add(node.right);
}
}
}
经过一些调试,我设法找到了我的错误。这个问题出在我的 insertNode() 方法中。
我正在生成我两次插入树中的第一个节点。
这是因为我打电话给
if(root==null){
root= new TreeNode<T>(d);
}
对于第一个节点,但是在调用其余代码之后并没有中断该方法,而是调用了两次生成第一个节点的代码。一个简单的 else if 语句解决了这个问题。解析后的代码如下所示。
public void insertNode(T d) {
if(root==null){
root= new TreeNode<T>(d);
size+=1;
}
else if(root!=null){
genList(root);
if(needsChildren(nodesThatNeedChildren.get(0))){
if(nodesThatNeedChildren.get(0).left==null){
nodesThatNeedChildren.get(0).left= new TreeNode<T>(d);
size+=1;
}else{
nodesThatNeedChildren.get(0).right= new TreeNode<T>(d);
size+=1;
}
}else{
while(!needsChildren(nodesThatNeedChildren.get(0))){
nodesThatNeedChildren.remove(0);
}
if(nodesThatNeedChildren.get(0).left==null){
nodesThatNeedChildren.get(0).left = new TreeNode<T>(d);
size+=1;
}else{
nodesThatNeedChildren.get(0).right = new TreeNode<T>(d);
size+=1;
}
}
}
}
我正在尝试生成具有广度优先插入形式的树。 我试图通过生成一个列表来做到这一点,其中包含树中所有元素的广度优先顺序。然后在我的 insertNode 方法中,我使用名为 needsChildren() 的方法检查节点是否需要子节点,如果需要,我将要插入的节点添加到可能的最左侧位置的树中。
如果我打电话 插入节点(10) 插入节点(8) 插入节点(20) 插入节点(5) 插入节点(29) 插入节点(50)
生成的树应该是
10
8 20
5 29 50
等等...
此解决方案无效,我不太确定原因。我认为可能是我的 generateList 没有正常工作,但我已经检查了最后打印的列表,它似乎是正确的。
是否有更好的方法来执行此操作,或者我的代码中是否存在我找不到的问题。非常感谢任何帮助。
这是我的树节点Class:
private static class TreeNode<T> {
public T data;
public TreeNode<T> left;
public TreeNode<T> right;
public TreeNode(T d) {
data = d;
left = null;
right = null;
}
}
我的 insertNode 方法:
public void insertNode(T d) {
if(root==null){
root= new TreeNode<T>(d);
}
genList(root);
if(needsChildren(nodesThatNeedChildren.get(0))){
if(nodesThatNeedChildren.get(0).left==null){
nodesThatNeedChildren.get(0).left= new TreeNode<T>(d);
}else{
nodesThatNeedChildren.get(0).right= new TreeNode<T>(d);
}
}else{
while(!needsChildren(nodesThatNeedChildren.get(0))){
nodesThatNeedChildren.remove(0);
}
System.out.println(nodesThatNeedChildren.get(0).data);
if(nodesThatNeedChildren.get(0).left==null){
nodesThatNeedChildren.get(0).left = new TreeNode<T>(d);
}else{
nodesThatNeedChildren.get(0).right = new TreeNode<T>(d);
}
}
}
我检查节点是否需要子节点的方法:
public boolean needsChildren(TreeNode<T> node){
if(node.left==null || node.right ==null){
return true;
}
return false;
}
以及我生成树中所有节点列表的方法:
public void genList(TreeNode<T> root) {
//generate new List each time
nodesThatNeedChildren.clear();
nodesThatNeedChildren.add(root);
//generate new Queue each time genList is called
tempQueue.clear();
tempQueue.add(root);
while(!tempQueue.isEmpty()){
TreeNode<T> node = tempQueue.remove(0);
if(node.left != null){
tempQueue.add(node.left);
nodesThatNeedChildren.add(node.left);
}
if(node.right != null){
tempQueue.add(node.right);
nodesThatNeedChildren.add(node.right);
}
}
}
经过一些调试,我设法找到了我的错误。这个问题出在我的 insertNode() 方法中。
我正在生成我两次插入树中的第一个节点。
这是因为我打电话给
if(root==null){
root= new TreeNode<T>(d);
}
对于第一个节点,但是在调用其余代码之后并没有中断该方法,而是调用了两次生成第一个节点的代码。一个简单的 else if 语句解决了这个问题。解析后的代码如下所示。
public void insertNode(T d) {
if(root==null){
root= new TreeNode<T>(d);
size+=1;
}
else if(root!=null){
genList(root);
if(needsChildren(nodesThatNeedChildren.get(0))){
if(nodesThatNeedChildren.get(0).left==null){
nodesThatNeedChildren.get(0).left= new TreeNode<T>(d);
size+=1;
}else{
nodesThatNeedChildren.get(0).right= new TreeNode<T>(d);
size+=1;
}
}else{
while(!needsChildren(nodesThatNeedChildren.get(0))){
nodesThatNeedChildren.remove(0);
}
if(nodesThatNeedChildren.get(0).left==null){
nodesThatNeedChildren.get(0).left = new TreeNode<T>(d);
size+=1;
}else{
nodesThatNeedChildren.get(0).right = new TreeNode<T>(d);
size+=1;
}
}
}
}