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()不关心each问题陈述中的单词。它仅将一个节点加倍。

于 2013-03-25T12:57:32.273 回答
0

不是不正确。您的代码仅将一个节点添加到树中。因此，它不会将树中的节点加倍，除非该树恰好只有一个节点。

顺便说一句，我会先解决打印树的问题，然后再做任何事情。如果无法打印树，如何检查其他问题的解决方案是否正确？

于 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 定义以适应重复值：如果一个元素大于 root，它将在其右侧，如果它小于 root，它将在其左侧; 否则，它可能在根的右侧或左侧。对每个节点使用一个数组来存储重复的条目。

GDB 问题：您的任务是针对给定场景的时间和内存，分析在 BST 定义中使用上述建议更改的成本和收益。

于 2015-02-19T10:28:28.277 回答