二叉搜索樹 - 所有遍歷方法工作不正確

Question

我正在處理二叉搜索樹，但是我在遍歷方法中遇到了一些問題。它不打印正確的數據。它甚至看起來像是從記憶中失去它。一切正常，直到添加第四個元素。你能看看這裏嗎？

頭文件

#ifndef TREENODE_H 
    #define TREENODE_H 
    #include<cstdlib> 
    #include<iostream> 

    template <class T> 
    class Bintree 
    { 
     struct Node 
     { 
      T val; 
      Node *left; 
      Node *right; 
     }; 
     public: 
     Bintree(); 
     Bintree(const Bintree&); 
     ~Bintree(); 
     Node* root; 
     void preorder(Node*); 
     void inorder(Node*); 
     void postorder(Node*); 
     Node* minimum(Node*); 
     Node* findelement(Node*); 
     Node* maximum(Node*); 
     void add(T); 
     void del(T); 
     void delnode(Node*); 
    }; 

    #endif 

treenode.cpp文件

#include "treenode.h" 

template<class T> 
Bintree<T>::Bintree() 
{ 
    root = nullptr; 
} 

template<class T> 
Bintree<T>::Bintree(const Bintree<T>& source) 
{ 
    root = copy(source.root, NULL); 
} 

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

template<class T> 
void Bintree<T>::preorder(Node* root) 
{ 
    if(root==nullptr) return; 
    std::cout<<root->val<<"\t"; 
    preorder(root->left); 
    preorder(root->right); 
} 

template<class T> 
void Bintree<T>::inorder(Node* root) 
{ 
    if(root==nullptr) return; 
    inorder(root->left); 
    std::cout<<root->val<<"\t"; 
    inorder(root->right); 
} 

template<class T> 
void Bintree<T>::postorder(Node* root) 
{ 
    if(root==nullptr) return; 
    postorder(root->left); 
    postorder(root->right); 
    std::cout<<root->val<<"\t"; 
} 

template<class T> 
typename Bintree<T>::Node* Bintree<T>::minimum(Node* root) 
{ 
    if(!root->left) return root; 
    else 
    { 
     while(root->left!=nullptr) 
      root = root->left; 
     return root; 
    } 
} 

    template<class T> 
    typename Bintree<T>::Node* Bintree<T>::maximum(Node* root) 
    { 
     if(!root->right) return root; 
     else 
     { 
      while(root->right!=nullptr) 
       root = root->right; 
      return root; 
     } 
    } 

    template<class T> 
    void Bintree<T>::add(T x) 
    { 
     Node *p = new Node; 
     p->left = nullptr; 
     p->right = nullptr; 
     p->val = x; 
     if(root == nullptr) 
      root = p; 
     else 
     { 
      for(;;) 
      { 
       if(x<root->val) 
       { 
        if(!root->left) 
        { 
         root->left = p; 
         break; 
        } 
        else root = root->left; 
       } 
       else 
       { 
        if(!root->right) 
        { 
         root->right = p; 
         break; 
        } 
        else root = root->right; 
       } 
      } 
     } 
    } 

的main.cpp文件

#include "treenode.cpp" // When I write treenode.h it gives me 
//an error like `Undefined reference to...` member functions. Why? 

int main() 
{ 
    try 
    { 
     Bintree<char> BST; 
     BST.add('a'); 
     BST.add('c'); 
     BST.add('x'); 
     BST.add('y'); 
     std::cout<<"min: "<<BST.minimum(BST.root)->val; 
     std::cout<<"max: "<<BST.maximum(BST.root)->val<<"\n"; 
     BST.preorder(BST.root); 
    } 
    catch (std::exception const &e) 
    { 
     std::cerr<<"Exception caught: "<<e.what()<<'\n'; 
    } 
    return 0; 
} 

Answer 1

沒有什麼不對您遍歷這樣。你的add函數總是修改根目錄。
它應該只在插入空樹時才這樣做。

使用本地變量遍歷：

template<class T> 
void Bintree<T>::add(T x) 
{ 
    Node *p = new Node; 
    p->left = nullptr; 
    p->right = nullptr; 
    p->val = x; 
    if(root == nullptr) 
     root = p; 
    else 
    { 
     Node* current = root; 
     for(;;) 
     { 
      if(x<current->val) 
      { 
       if(!current->left) 
       { 
        current->left = p; 
        break; 
       } 
       else current = current->left; 
      } 
      else 
      { 
       if(!current->right) 
       { 
        current->right = p; 
        break; 
       } 
       else current = current->right; 
      } 
     } 
    } 
}