c++ - 插入搜索树类行为不当的函数

Question

您好，以下模板代码来自'Computational Geometry and Computer graphics in C++ by Michael J Laszlo '

代码

#include <cstdlib>


template <class T> class SearchTree;



template<class T> class TreeNode{

private:
    TreeNode * _lchild;
    TreeNode * _rchild;
    T val;
public:
    TreeNode(T);
    virtual ~TreeNode(void);
    friend class SearchTree<T>;
    };

template <class T> TreeNode<T> :: TreeNode(T v) : val(v) , _lchild(NULL) , _rchild(NULL)
{}

template <class T> TreeNode <T> :: ~TreeNode(void)
{
if ( _lchild) delete _lchild;
if ( _rchild) delete _rchild;
}


//////////////////////////////////////////////////////////////////////////////////////
///////-------------------------------------------------------------------------------
//////////////////////////////////////////////////////////////////////////////////////
//////+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
/////////////////////////////////////////////////////////////////////////////////////


template <class T> class SearchTree {

private:
    TreeNode <T> * root;
    int (*cmp) (T,T);
    void _inorder(TreeNode <T>*,void(*)(T));
public:
    SearchTree ( int (*) (T,T));
    ~SearchTree(void);
    int isEmpty(void);
    T find(T);
    T findMin(void);
    void inorder( void (*) (T));
    void insert(T);void remove(T);T removeMin(void);

};

template <class T>
SearchTree<T>::SearchTree(int(*c) (T,T)): cmp(c) ,root(NULL)
{} 

template <class T>
SearchTree<T>::~SearchTree()
{ if (root) delete root ;} 


template <class T> void SearchTree <T>::_inorder(TreeNode <T> *n ,void (*visit) (T))
{

if (n) {
_inorder(n->_lchild ,visit);
(*visit)(n->val);
_inorder(n->_rchild,visit);
};
}

template <class T> void SearchTree<T> :: inorder(void (*visit)(T)) {_inorder(root,visit);}

template <class T>
void SearchTree<T>::insert(T val)
{
if (root ==NULL) {

root =new TreeNode <T> (val);
return;
}

else{
int result;
TreeNode <T> * n, *p =root;
while (n) {
    p=n;
    result=(*cmp)(val,p->val);
    if (result <0) 
        {n = p->_lchild;}
    else if (result >0)
        { n= p->_rchild;}
    else 
        {return ;};
    }

    if (result <0) p->_lchild =new TreeNode <T> (val);
    else    p -> _rchild =new  TreeNode <T> (val);
}













}


template <class T>
T SearchTree <T> :: find ( T val) {
int result;
TreeNode <T> * n =root;
while (n) {
 result=(*cmp)(val,n->val);
 if (result >0) n =n->_rchild;
 else if (result <0 ) n=n->_lchild;
 else return n->val;


};
return 0;

}

以上代码的使用

#include "treenode.h"
#include<iostream>

int compare(int x , int y)
{

if (x > y) {return 1;}
else if (x ==y) { return 0 ;}
else {return -1;};

};


void printer(int x) {std::cout <<x<<"\n";};
int main(){

SearchTree <int> jo(compare);jo.insert(9);
jo.insert(2);jo.insert(10);jo.insert(3);
jo.inorder(printer);
std::cout<<jo.find(10)<<std::endl;
return 0;

}

输出

3 9 0

问题

作者哪里错了？还是我实现错了？

我个人认为插入函数行为不当，因为搜索之前插入的一些成员返回负数..

Answer 1

这是 insert() 的重要部分:

int result;
TreeNode <T> * n, *p = root;

while (n)
{
    p = n;
    result = (*cmp)(val, p->val);

    if (result < 0) 
        n = p->_lchild;
    else if (result > 0)
        n = p->_rchild;
    else 
        return;
}

if (result < 0)
    p->_lchild = new TreeNode <T> (val);
else
    p->_rchild = new TreeNode <T> (val);

我唯一看到的错误是 n 开始未初始化。这会造成困惑。您需要将其设置为 root。你只是混淆了 n 和 p:

TreeNode <T> *n = root, *p;