插入功能

Question

你好以下模板代码是从'Computational Geometry and Computer graphics in C++ by Michael J Laszlo '

代码上面的代码

#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; 

} 

输出的

#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; 

} 

用法

问题

在哪里作者回事？还是我执行错了？

我个人认为，在插入功能失常，因为搜索的一些成员先前插入返回否..

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;