二叉树Sorrt Java递归

我对Java中的二叉树排序有一些麻烦。我需要创建以下方法，但我不明白，如何正确实现位置（pos）。练习是实现具有给定签名的二叉树排序。然后我们应该初始化一个int []，它的大小必须至少是树中节点的大小。方法二叉树Sorrt Java递归

INT binSort（节点节点，INT []一，INT POS）{...}

应该把每个节点/叶的值插入到阵列的位置pos处。我不允许使用全局变量！正如你所看到的，我们需要实现中序遍历

public class BinaryTree { 

Node root; 
int elements; 

public BinaryTree() { 
    this.elements = 0; 
} 

public void addNode(int key, String name) { 
    Node newNode = new Node(key, name); 
    if (root == null) { 
     root = newNode; 
    } else { 
     Node focusNode = root; 
     Node parent; 

     while (true) { 
      parent = focusNode; 
      if (key < focusNode.getPriority()) { 
       focusNode = focusNode.getLeftChild(); 
       if (focusNode == null) { 
        parent.setLeftChild(newNode); 
        return; 
       } 
      } else { 
       focusNode = focusNode.getRightChild(); 
       if (focusNode == null) { 
        parent.setRightChild(newNode); 
        return; 
       } 
      } 
     } 
    } 
} 

public int binSort(Node focusNode, int[] a, int pos) { 
    int tmp = pos++; 
    if (focusNode != null) { 
     if (focusNode.getLeftChild() != null) { 
      binSort(focusNode.getLeftChild(), a, tmp); 
     } 

      System.out.println(focusNode.toString() + " - " + tmp++); 
     if (focusNode.getRightChild() != null) { 
      binSort(focusNode.getRightChild(), a, tmp); 
     } 
     return focusNode.getPriority(); 
    } 
    return -1; 
} 

public static void main(String[] args) { 
    BinaryTree tree = new BinaryTree(); 
    tree.addNode(50, "Boss"); 
    tree.addNode(30, "Boss"); 
    tree.addNode(10, "Boss"); 
    tree.addNode(70, "Boss"); 
    tree.addNode(9, "Boss"); 
    tree.addNode(15, "Boss"); 
    tree.addNode(78, "Boss"); 
    tree.addNode(36, "Boss"); 

    int[] a = new int[8]; 
    tree.binSort(tree.root, a, 0); 
    System.out.println(tree.root.getPriority()); 
    System.out.println(""); 

    System.out.println(Arrays.toString(a)); 

}

}

我的输出：老板有一个键9 - 0

老板有一个关键的10 - 0

老板有一把钥匙15 - 1

老板有钥匙30 - 0

个

老板具有键36 - 1个

老板具有键50 - 0

老板有一个键70 - 1个

老板具有键78 - 2

只是忽略“老板“（这仅仅是一个无用的值！）重要的部分是应该放入数组中的具体数值是完全有序的（9,10,15,30，...，78），但是位置不是！（0,0,1,0,1,0,1,2）我不知道如何解决这个问题。

Btw。类“节点”：

String val; 
int priority; 

Node leftChild; 
Node rightChild; 

public Node(int priority, String val) { 
    this.priority = priority; 
    this.val = val; 
} 

public int getPriority() { 
    return this.priority; 
} 

public String getVal() { 
    return this.val; 
} 

public Node getLeftChild() { 
    return leftChild; 
} 

public Node getRightChild() { 
    return rightChild; 
} 

public void setLeftChild(Node child) { 
    this.leftChild = child; 
} 

public void setRightChild(Node child) { 
    this.rightChild = child; 
} 

public String toString() { 
    return val + " has a key " + priority; 
}

我希望你能够帮我解决这个问题。

来源

2016-07-05 Jakob Bennemann

你调试了你的代码吗？ – Thomas

以上示例的正确顺序应该是什么？ –

按位置你是指从该节点的高度？ –

好了，我发现我自己:)解决

public int binSort(BinTreeNode nnode, int[] a, int pos) { 
    if (nnode != null) { 
     if (nnode.getLeftChild() != null) { 
      pos = binSort(nnode.getLeftChild(), a, pos); 
     } 
     a[pos] = nnode.getValue(); 
     pos++; 
     if (nnode.getRightChild() != null) { 
      pos = binSort(nnode.getRightChild(), a, pos); 
     } 
     return pos; 
    } 
    return -1; 
}

我需要回到代替focusNode.getPriority（POS）和我只有1递增POS机，之后我的附加值当前节点！

来源

2016-07-05 19:42:29

二叉树Sorrt Java递归

回答

相关问题