c++ - 遍历二叉搜索树

Question

我已经实现了一个基本的二叉搜索树。这是我的节点

 #ifndef NODE_H
    #define NODE_H

    template<typename T> class node{

        template<typename E> friend class bst;

        public:
            node():data(0), left(NULL), right(NULL){}
            node(T data):data(data),left(NULL), right(NULL){}   

        private:
            T data;
            node<T>* left;
            node<T>* right;
    };

#endif

这是我的 bst。

#ifndef BST_H
#define BST_H

template<typename T> class bst{
    public:
        bst():root(NULL), nodes(0){}
        bst(node<T>* root):root(root), nodes(0){}

        void insert(node<T>* root, const T& data){

            if(root == NULL){
                node<T>* root = new node<T>();
                root->data = data;
                nodes++;
                return;
            }else if(data <= root->data) {
                insert(root->left, data);

            }else if(data >= root->data){
                insert(root->right, data);

            }
        }

        void preorder(node<T>* root){
            if(root == NULL) return;
            std::cout<< root->data<<'\n';

            preorder(root->left);
            preorder(root->right);
        }
    private:
        node<T>* root;
        int nodes;
};
#endif

调用函数

int main(){

    node<int>* root = new node<int>(17);
    bst<int>* t = new bst<int>(root);


    t->insert(root,21);
    t->insert(root,12);
    t->insert(root, 9);

    t->preorder(root);

    delete t;
}

输出只是 17，这是根。我觉得不知何故我的插入方法没有正常工作，因为预购是一个非常标准的实现。有人可以帮我看看这里出了什么问题吗。

Answer 1

在 insert 里面不创建局部变量，只使用 one passe。所以不是

node<T>* root = new node<T>();

只做

root = new node<T>();

并通过引用传递 root。我会用 typedef 来做

typedef node<T>* nodePtr;
void insert(nodePtr &root, const T& data){

但你也可以不用