0

我真的在这家伙身上扯掉我的头发。这就是问题所在。我已经硬编码了一个 2-3 树，并验证了它可以使用输出它当前所在节点的值的中序遍历函数工作。所以我知道树是正确构建的。

 Node *r;
  Node zero,one,two,three,four,five,six,seven,eight,nine,ten;
  r = &zero;

          //Root
 zero.small = 50;
 zero.large = 90;
 zero.left = &one;       //Child node to the left
 zero.middle = &four;    //Child node in the middle
 zero.right = &seven;    //Child node to the right

  //Left Tree
 one.small = 20;
 one.large = NULL;
 one.left = &two;
 one.middle = NULL;
 one.right = &three;

 two.small = 10;
 two.large = NULL;
 two.left = NULL;
 two.middle = NULL;
 two.right = NULL;

 three.small = 30;
 three.large = 40;
 three.left = NULL;
 three.middle = NULL;
 three.right = NULL;

  //Middle Tree
 four.small = 70;
 four.large = NULL;
 four.left = &five;
 four.middle = NULL;
 four.right = &six;

 five.small = 60;
 five.large = NULL;
 five.left = NULL;
 five.middle = NULL;
 five.right = NULL;

 six.small = 80;
 six.large = NULL;
 six.left = NULL;
 six.middle = NULL;
 six.right = NULL;

  //Right Tree
 seven.small = 120;
 seven.large = 150;
 seven.left = &eight;
 seven.middle = &nine;
 seven.right = &ten;

 eight.small = 100;
 eight.large = 110;
 eight.left = NULL;
 eight.middle = NULL;
 eight.right = NULL;

 nine.small = 130;
 nine.large = 140;
 nine.left = NULL;
 nine.middle = NULL;
 nine.right = NULL;

 ten.small = 160;
 ten.large = NULL;
 ten.left = NULL;
 ten.middle = NULL;
 ten.right = NULL;

 cout<<"inorder traversal for debug"<<endl;
 inOrder(*r);

输出为：10 20 30 40 50 60 70 80 90 100 110 120 130 140 150 160

这样就证明了树是正确构建的。我被要求修改代码以在树中搜索值。所以我在下面写了这个函数，它本质上是中序遍历函数减去输出和一个简单的 if 语句，如果在树中找到搜索键，则返回 TRUE。

bool retrieve(Node r, int key)
{
 if (r.left)
    retrieve(*r.left, key);
 if (r.small)
 {
     if (r.small == key)
    {
        cout<<"The node: "<<r.small<<" is equal to search key: "<<key<<endl; //for debug purposes
        return true;
    }
 }
 if (r.middle)
    retrieve(*r.middle, key);
 if (r.large)
 if (r.right)
    retrieve(*r.right, key);  
}

提示用户输入要搜索的数字（int 键），并在输入时输入 if 语句

if (retrieve(*r, key))
 {
     cout<<key<<" is found!"<<endl;
 }
 else
     cout<<key<<" is not found!"<<endl;

现在的问题是这对我来说在逻辑上似乎是合理的，但是当我输入值“85”（根本不在树上）时，程序输出“85 is found!”。注意它没有输出我在函数中的 COUT 语句。cout<<"The node: "<<r.small<<" is equal to search key: "<<key<<endl;我已经调试并逐步完成了程序，无论 bool 函数（检索）总是返回 true ......什么？所以我在输入“60”（位于树上）时切换了 bool 函数中的 if 语句以返回 false（仅用于调试目的），布尔函数仍然返回 true。我尝试了几种略有不同的代码组合，但无济于事..到底发生了什么？

提前致谢，

泰勒

4

3 回答 3

0

您永远不会返回值，除非在if (r.small == key)分支中。

从2-3 树 - 维基百科，我会说你的代码应该首先将key与small和large键进行比较，然后根据比较返回结果retrieve(*r.left/middle/right, key)。

这些方面的东西（未经测试）

if (key < r.small)
    return retrieve(*r.small, key);

if (key == r.small)
    return TRUE;

if (r.right == NULL)
    return retrieve(*r.middle, key);

if (key < r.large)
    return retrieve(*r.middle, key);

if (key == r.large)
    return TRUE;

return retrieve(*r.right, key);
于 2013-04-07T21:17:42.840 回答
0

需要先检查在当前节点中是否找到了key，无论是small还是large，如果是，则返回true。如果不是，则需要在每个包含的节点上递归调用retrieve，如果其中任何一个返回true，则返回true。如果您的函数尚未返回，则需要返回 false。

于 2013-04-07T21:24:53.507 回答
0

您需要进行初始测试以查看递归是否应该停止，因为您至少是节点。

// precondition: current is not 0
// returns: true or false. If true, location is set to the node 
// where it was found.
bool DoSearch(Node *current, int key, Node *location)
{
 /*
  * Is key in current?
  */
if (current->smallValue == key || (current->isThreeNode() 
       && current->largeValue == key)) {

    location = current;
    return true;

} else if ((current->isLeafNode())) {

    location = current;
    return false;
 /*
  *  Does current have two keys?
  */
} else if (current->isThreeNode()){

    if (key < current->smallValue) {

        DoSearch(key, current->leftChild, location);

    }  else if (key < current->largeValue) {

        DoSearch(key, current->middleChild, location);

    } else {

        DoSearch(key, current->rightChild, location);
    }

} else { // ...or only one?

     if (key < current->smallValue) {

        DoSearch(key, current->leftChild, location);

    }  else {

        DoSearch(key, current->rightChild, location);
    }
}
}
于 2013-05-14T01:39:36.323 回答