11

最近、取り組んでいたプロジェクトの二分探索木の実装を完了しました。うまくいき、多くのことを学びました。ただし、今は通常のバイナリ ツリーを実装する必要があります...何らかの理由で困惑しています。

InsertNode 関数を実行する方法を探しています..

通常、BSTでは、データ<ルートかどうかを確認してから左に挿入し、その逆も同様です。ただし、通常のバイナリ ツリーでは、一度に 1 レベルずつ、左から右に埋められるだけです。

特定の順序で左から右にバイナリ ツリーに新しいノードを追加する関数を実装するのを手伝ってくれる人はいますか?

BSTの挿入は次のとおりです。

void Insert(Node *& root, int data)
{
  if(root == nullptr)
  {
    Node * NN = new Node;
    root = NN;
  }
  else
  {
    if(data < root->data)
    { 
      Insert(root->left, data);
    }
    else
    {
      Insert(root->right, data);
    }
  }
}
4

5 に答える 5

13

これがしばらく前に投稿された質問であることは承知していますが、それでも私の考えを共有したいと思いました。

私がすることは（これは実際にはあまり文書化されていないため）、Breadth-First-Search（キューを使用）を使用し、最初に遭遇した null に子を挿入することです。これにより、ツリーが別のレベルに移動する前に、最初にレベルがいっぱいになります。適切な数のノードがあれば、常に完全になります。

私は C++ であまり作業したことがないので、正しいことを確認するために Java で行いましたが、次のように理解できます。

public void insert(Node node) {
    if(root == null) {
        root = node;
        return;
    }

    /* insert using Breadth-first-search (queue to the rescue!) */
    Queue<Node> queue = new LinkedList<Node>();
    queue.offer(root);

    while(true) {
        Node n = queue.remove();
        if(!n.visited) System.out.println(n.data);
        n.visited = true;

        if(n.left == null) {
            n.left = node;
            break;
        } else {
            queue.offer(n.left);
        }           

        if(n.right == null) {
            n.right = node;
            break;
        } else {
            queue.offer(n.right);
        }
    }
}
于 2013-12-11T08:43:08.420 に答える
5

Javascript の実装 (Web コンソールにコピー アンド ペースト可能):

ES6 実装 (class キーワードを使用した新しい JavaScript 構文)

  class BinaryTree {
      constructor(value){
          this.root = value;
          this.left = null;
          this.right = null;
      }

      insert(value){
          var queue = [];
          queue.push(this); //push the root
          while(true){
              var node = queue.pop();
              if(node.left === null){
                  node.left = new BinaryTree(value);
                  return;
              } else {
                  queue.unshift(node.left)
              }

              if(node.right === null){
                node.right = new BinaryTree(value);
                return;
              } else {
                queue.unshift(node.right)
              }
          }
      }
  }

  var myBinaryTree = new BinaryTree(5);
  myBinaryTree.insert(4);
  myBinaryTree.insert(3);
  myBinaryTree.insert(2);
  myBinaryTree.insert(1);

     5
   /   \
  4     3
 / \   (next insertions here)
 2  1

疑似古典パターンの実装

  var BinaryTree = function(value){
    this.root = value;
    this.left = null;
    this.right = null;
  }

  BinaryTree.prototype.insert = function(value){
    //same logic as before
  }
于 2016-10-23T02:45:12.377 に答える
0

意味がわかっている場合は、x = new (x) などの再帰的なアプローチを使用してみてください。この方法では、ルート ノードについて心配する必要はありません。私はあなたのためにいくつかの擬似コードを書くつもりです:

//public function
add(data){
    root = add(data, root)
}

//private helper function 
Node add(data, currentNode){
    if(currentNode = 0)
        return new Node(data)

    if(data less than currentNode's data)
        currentNode.left = add(data, currentNode.left)
    if(data more than currentNode's data)
        currentNode.right = add(data, currentNode.right)

    return currentNode      
}

C++ での BST の実装に関するチュートリアルを作成しました。

于 2013-05-19T05:13:31.873 に答える