1

二分探索木の助けが必要です。ノードと BST クラスは次のとおりです。

public class Node {
    private int key;
    private Node parent;
    private Node leftChild;
    private Node rightChild;

    public Node(int key, Node leftChild, Node rightChild) {
        this.setKey(key);
        this.setLeftChild(leftChild);
        this.setRightChild(rightChild);
    }

    public void setKey(int key) {
        this.key = key;
    }

    public int getKey() {
        return key;
    }

    public void setParent(Node parent) {
        this.parent = parent;
    }

    public Node getParent() {
        return parent;
    }

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

    public Node getLeftChild() {
        return leftChild;
    }

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

    public Node getRightChild() {
        return rightChild;
    }
}

public class BinarySearchTree {

    private Node root;

    public void insert(int key) {
        insert(new Node(key, null, null));
    }

    public void insert(Node z) {

        Node y = null;
        Node x = root;

        while (x != null) {
            y = x;

            if (z.getKey() < x.getKey()) {
                x = x.getLeftChild();
            } else {
                x = x.getRightChild();
            }
        }

        z.setParent(y);

        if (y == null) {
            root = z;
        } else if (z.getKey() < y.getKey()) {
            y.setLeftChild(z);
        } else {
            y.setRightChild(z);
        }
    }

    public void preorderTraversal() {
        preorderTraversal(root);
    }

    public void preorderTraversal(Node node) {
        if (node != null) {
            System.out.print(node.getKey() + " ");
            preorderTraversal(node.getLeftChild());
            preorderTraversal(node.getRightChild());            
        }
    }

    public void inorderTraversal() {
        inorderTraversal(root);
    }

    private void inorderTraversal(Node node) {
        if (node != null) {
            inorderTraversal(node.getLeftChild());
            System.out.print(node.getKey() + " ");
            inorderTraversal(node.getRightChild());
        }
    }

    public void postorderTraversal() {
        postorderTraversal(root);
    }

    private void postorderTraversal(Node node) {
        if (node != null) {
            postorderTraversal(node.getLeftChild());
            postorderTraversal(node.getRightChild());
            System.out.print(node.getKey() + " ");
        }
    }
}

( http://www.brilliantsheep.com/java-implementation-of-binary-search-tree-insert-and-traversal-methods/から取得) これは比較的単純な実装です。ただし、各ノードに追加情報を保存する必要があります。ノードには、選挙の候補者と候補者の投票数が含まれている必要があります。この割り当て (および BST を使用しなければならない理由) については多くの不満がありましたが、それには立ち入らないでください。

候補に 1 ～ 20 の番号を付け、これをバイナリ検索ツリーのキーとして使用しています。私の質問は、このコード (またはわずかに変更されたバージョン) を使用して、キーを指定して特定のノード情報を更新するにはどうすればよいですか?

例えば。その人が候補者 4) に投票した場合、候補者 4 の投票情報を更新するにはどうすればよいですか?

いくつかの検索メソッドを見てきましたが、どのノードで呼び出す必要があるのか​​ わかりません。

どんな助けでも大歓迎です。

4

1 に答える 1

0

クラスに2 つのプロパティを追加するだけで、Node必要な追加情報を格納できます。したがって、Node クラスは次のようになります。

public class Node {

  private int key;
  private Node parent;
  private Node leftChild;
  private Node rightChild;

  public string candidateName;
  public int votes;

  // .. other properties and methods
}

候補 4 に投票したら、ツリーをたどってキー 4 のノードを見つけ、次のようにします。node.votes++

擬似コードでは、次のようになります。

Node node = root;

while (node.key != 4) {
  // implement your tree traversal algorithm here
}

// when you reach here, node is the candidate you were searching
// for, or null if not found

if (node != null) {
  node.votes++;
}

votesNode コンストラクターで必ず 0 に初期化してください。

于 2013-03-22T08:48:52.860 に答える