0

問題が発生しました

 For each node in a binary search tree, 
 create a new duplicate node, and insert 
 the duplicate as the left child of the original node. 
 The resulting tree should still be a binary search tree.

http://cslibrary.stanford.edu/110/BinaryTrees.html

そこに解決策がありますが、私の解決策は異なります。

void doubleTree(struct node* node) { 
  struct node* tempNode;

  if (node->left == NULL) 
  {
   node->left = new Node(node->data);   
  }
  else{
   tempNode = new Node(node->data);
tempNode->left = node->left;
node->left = tempNode; 
  }
}

このアプローチは正しいですか？ありがとう 。

4

4 に答える 4

1

アプローチは正しいですが、問題文doubleTree()の単語を気にしません。each1 つのノードのみを 2 倍にします。

于 2013-03-25T12:57:32.273 に答える
0

そうではありません。このコードでは、ノードを 1 つだけツリーに追加します。したがって、そのツリーにたまたまノードが 1 つしかない場合を除き、ツリー内のノードが 2 倍になることはありません。

ところで、これ以上行う前に、ツリーの問題を解決することを検討します。ツリーを印刷できない場合、他の問題の解決策が正しいことをどのように確認できますか?

于 2013-03-25T12:57:44.130 に答える
0 
void createDoubleTree(TreeNode t) {
        if (t == null) {
            return;
        }
        createDoubleTree(t.left);
        TreeNode temp=t.left;
        t.left=new TreeNode(t.k);
        t.left.left=temp;
        createDoubleTree(t.right);
    }
于 2013-10-06T21:06:50.663 に答える
-1

GDB シナリオ: 大手ソフトウェア会社にソフトウェア エンジニアとして雇われ、従業員の名前に基づいてアルファベット順に従業員のレコードを保存するタスクを割り当てられたとします。アプリケーションでは、レコードを名前で挿入、削除、および検索できるようにする必要があります。同社の主な関心事は、従業員の実績をチェックするために従業員の記録を効率的に検索することです。このためには、二分探索が適切なオプションです。しかし、BST には、正式な定義が次のように重複する値を処理しないという問題があります。根よりも小さい場合は、左側に移動します。」この定義は、重複する値を扱いません。ただし、特定のシナリオでは、複数の従業員が同じ名前を持っている可能性があるため、BST は重複した値も処理できる必要があります。ここで、重複する値にも対応するように BST 定義を変更する次のオプションがあることを考慮してください。要素がルートよりも大きい場合は右側に移動し、ルートよりも小さい場合は左側に移動します; それ以外の場合は、ルートの右側または左側に配置できます。重複するエントリを格納するには、各ノードで配列を使用します。

GDB 質問: あなたのタスクは、特定のシナリオの時間とメモリに関して、上記で提案された BST 定義の変更を使用することのコストと利点を分析することです。

于 2015-02-19T10:28:28.277 に答える