在二叉树中计算节点

Question

http://pastebin.com/gGY6Dw5y

有一个指向上面的代码的链接。关键是要制作一个方法来计算二叉树中的节点，然后创建两个也计算节点的方法，树的每一边都有一个方法。我的问题是如何调用该方法来计算节点。

我的问题是如何调用我的countNodes方法。我不知道它在寻找什么样的论点。

#include "stdafx.h" 
#include <iostream> 
#include <fstream> 
#include <istream> 
#include <string> 
#include <cstdlib> 
using namespace std; 
template <class datatype> 
class treenode{ 
public: 
    datatype data; 
    string qa; 
    treenode<datatype> *lchild, *rchild; 

}; 
template<class datatype> 
class btree{ 
private: 
    treenode<datatype> *root, *current; 
public: 
    btree(); 
    bool tree_empty(void); 
    void insertdata(datatype x); //call from main program to insert data 
    void inserttree(treenode<datatype> *&p, datatype d); 
    void inorder(treenode<datatype> *p); 
    void printinorder(void);//call from main program 
    void preorder(treenode<datatype> *p); 
    void printpreorder(void);//call from main program 
    void postorder(treenode<datatype> *p); 
    void printpostorder(void);//call from main program 
    void deletevalue(datatype v); 
    void deltree(datatype val, treenode<datatype> *&p); 
    treenode<datatype>* findmin(treenode<datatype> *p); 
    void inserttree2(treenode<datatype> *&p, datatype d, string qas); 
    void insertdata2(datatype x, string a); 
    void yesno(void); 
    int countNodes(treenode<datatype> *p); 


}; 

template<class datatype> 
btree<datatype>::btree(){ 
    root =NULL; 
}; 

template<class datatype> 
bool btree<datatype>::tree_empty(){ 
    bool x = true; 
    if(root == NULL){ 
      x = true; 
    }else{ 
      x = false; 
    } 
    return x; 
}; 

template<class datatype> 
void btree<datatype>::insertdata(datatype x){ 
    inserttree(root,x); 
}; 

template<class datatype> 
void btree<datatype>::inserttree(treenode<datatype> *&p, datatype d){ 
    if(p == NULL){ 
      p = new treenode<datatype>; 
      p->data = d; 
      p->lchild = NULL; 
      p->rchild = NULL; 
    }else{ 
      if(p->data > d) 
        inserttree(p->lchild,d); 
      else 
        inserttree(p->rchild,d); 
    } 
}; 

template<class datatype> 
void btree<datatype>::inorder(treenode<datatype> *p){ 
    if(p!= NULL){ 
      inorder(p->lchild); 
      cout<< p->data << " "; 
      inorder(p->rchild); 
    } 
}; 

template<class datatype> 
void btree<datatype>::printinorder(void){ 
    inorder(root); 
}; 

template<class datatype> 
void btree<datatype>::preorder(treenode<datatype> *p){ 
    if(p!= NULL){ 
      cout<< p->data << " "; 
      preorder(p->lchild); 
      preorder(p->rchild); 
    } 
}; 

template<class datatype> 
void btree<datatype>::printpreorder(void){ 
    preorder(root); 
}; 

template<class datatype> 
void btree<datatype>::postorder(treenode<datatype> *p){ 
    if(p!= NULL){ 
      postorder(p->lchild); 
      postorder(p->rchild); 
      cout<< p->data << " "; 
    } 
}; 

template<class datatype> 
void btree<datatype>::printpostorder(void){ 
    postorder(root); 
}; 

template<class datatype> 
void btree<datatype>::deletevalue(datatype v){ 
    deltree(v,root); 
}; 

template<class datatype> 
void btree<datatype>::deltree(datatype val, treenode<datatype> *&p){ 
    treenode<datatype> *buff; 
    if(p != NULL) 
      if(val < p->data) 
        deltree(val,p->lchild); 
      else 
        if(val > p->data) 
          deltree(val, p->rchild); 
        else 
          if(p->lchild == NULL && p->rchild == NULL) 
            p= NULL; 
          else 
            if(p->lchild == NULL) 
              p= p->rchild; 
            else 
              if(p->rchild == NULL) 
                p = p->lchild; 
              else 
              { 
                buff = findmin(p->rchild); 
                buff->lchild = p->lchild; 
                p = p->rchild; 

              } 


}; 
template<class datatype> 
void btree<datatype>::inserttree2(treenode<datatype> *&p, datatype d, string qas){ 
    if(p ==NULL){ 
      p = new treenode<datatype>; 
      p->data = d; 
      p->qa = qas; 
      p->lchild = NULL; 
      p->rchild = NULL; 
    }else{ 
      if(p->data > d) 
        inserttree2(p->lchild,d,qas); 
      else 
        inserttree2(p->rchild,d,qas); 
    } 
}; 

template<class datatype> 
void btree<datatype>::insertdata2(datatype x, string a){ 
    inserttree2(root,x,a); 
}; 
template<class datatype> 
void btree<datatype>::yesno(void){ 
    current = root; 
    bool solved = false; 
    char c; 
    cout<<current->qa<<endl; 
    while(!solved){ 
      cout<<"Enter a Y or N"; 
      cin>> c; 
      if(c == 'Y' ||c == 'N'){ 
      if(c == 'Y'){ 
        current = current->lchild; 
      } 
      if(c == 'N'){ 
        current = current->rchild; 
      } 
      cout<<current->qa<<endl; 
      if(current->lchild == NULL){ 
        solved = true; 
        cout<<"You have your answer "<<endl; 
      } 
      } 
      } 
}; 

template<class datatype> 
treenode<datatype>* btree<datatype>::findmin(treenode<datatype> *p){ 
    if(p->lchild == NULL) 
      return (p); 
    else 
      return(findmin(p->lchild)); 
}; 

template<class datatype> 
int btree<datatype>::countNodes(treenode<datatype> *p){ 
int count = 1;  
    if (p == NULL){ 
     return 0; 
      }else{ 
     int count = 1; /
     count += countNodes(p->lchild); 

     count += countNodes(p->rchild); 
      }        /
     return count; 
    }; 

int _tmain(int argc, _TCHAR* argv[]) 
{ 


    btree<int> genesistree; 
    int datavalues, 
      deletevalues, 
      addvalues, 
      newdata, 
      olddata, 
      newnewdata, 
      ifstatement, 
      c, 
    *p; 
    bool flag; 
    genesistree.insertdata(14); 
      genesistree.insertdata(2); 
      genesistree.insertdata(34); 
      genesistree.insertdata(41); 
      genesistree.insertdata(12); 


    /* 
    if(genesistree.tree_empty()){ 
      cout<<"The list is empty"<<endl; 
    }else{ 
      cout<<"The list is not empty"<<endl; 
    } 
    cout<<""<<endl; 

    cout<<"Enter the ammount of data values for the tree"<<endl; 
    cin>>datavalues; 
    cout<<""<<endl; 
    for(c = datavalues, c >= 0; c--;){ 
      cout<<"Enter a datavalue for the tree"<<endl; 
      cin>>newdata; 
      genesistree.insertdata(newdata); 
      cout<<""<<endl; 
    } 

    cout<<""<<endl; 

    if(genesistree.tree_empty()){ 
      cout<<"The list is empty"<<endl; 
    }else{ 
      cout<<"The list is not empty"<<endl; 
    } 

    cout<<""<<endl; 
    cout<<"Print Preorder"<<endl; 
    genesistree.printpreorder(); 
    cout<<""<<endl; 
    cout<<""<<endl; 
    cout<<"Print in order"<<endl; 
    genesistree.printinorder(); 
    cout<<""<<endl; 
    cout<<""<<endl; 
    cout<<"Print Postorder"<<endl; 
    genesistree.printpostorder(); 
    cout<<""<<endl; 
    cout<<""<<endl; 
    cout<<"Enter the ammount of datavalues you would like to delete"<<endl; 
    cin>>deletevalues; 
    cout<<""<<endl; 
    if(deletevalues < datavalues){ 
    for(c = deletevalues, c >= 0; c--;){ 
      cout<<"Enter a datavalue to delete in the tree"<<endl; 
      cin>>olddata; 
      genesistree.deletevalue(olddata); 

    } 
    }else{ 
      if(deletevalues == 0){ 
        cout<<""<<endl; 
      }else{ 

      } 
    } 
    cout<<""<<endl; 
    cout<<"Would you like to re print the results?"<<endl; 
    cout<<""<<endl; 
    cout<<"Hit 1 for yes, and 0 for no"<<endl; 
    cin>>ifstatement; 
    if(ifstatement == 1){ 
      flag = true; 
    }else{ 
      flag = false; 
    } 
    if(flag == true){ 
    cout<<""<<endl; 
    cout<<"Print Preorder"<<endl; 
    genesistree.printpreorder(); 
    cout<<""<<endl; 
    cout<<""<<endl; 
    cout<<"Print in order"<<endl; 
    genesistree.printinorder(); 
    cout<<""<<endl; 
    cout<<""<<endl; 
    cout<<"Print Postorder"<<endl; 
    genesistree.printpostorder(); 
    cout<<""<<endl; 
    cout<<""<<endl; 
    }else{ 
      if(flag == false){ 
      cout<<""<<endl; 
      } 
    } 
    cout<<""<<endl; 

cout<<"Enter the ammount of datavalues you would like to add"<<endl; 
    cin>>addvalues; 
    cout<<""<<endl; 
    if(addvalues > 0){ 
    for(c = deletevalues, c >= 0; c--;){ 
      cout<<"Enter a datavalue to add in the tree"<<endl; 
      cin>>newnewdata; 
      genesistree.insertdata(newnewdata); 
      cout<<""<<endl; 

    } 
    }else{ 
      if(deletevalues == 0){ 
        cout<<""<<endl; 
      }else{ 

      } 
    } 
    cout<<""<<endl; 
    cout<<"Would you like to re print the results?"<<endl; 
    cout<<""<<endl; 
    cout<<"Hit 1 for yes, and 0 for no"<<endl; 
    cin>>ifstatement; 
    if(ifstatement == 1){ 
      flag = true; 
    }else{ 
      flag = false; 
    } 
    if(flag == true){ 
    cout<<""<<endl; 
    cout<<"Print Preorder"<<endl; 
    genesistree.printpreorder(); 
    cout<<""<<endl; 
    cout<<""<<endl; 
    cout<<"Print in order"<<endl; 
    genesistree.printinorder(); 
    cout<<""<<endl; 
    cout<<""<<endl; 
    cout<<"Print Postorder"<<endl; 
    genesistree.printpostorder(); 
    cout<<""<<endl; 
    cout<<""<<endl; 
    }else{ 
      if(flag == false){ 
      cout<<""<<endl; 
      } 
    } 
    */ 
    cout<<""<<endl; 
    countNodes(genesistree); 
      /* 
    btree<int> mytree; 
    string QandA[7]; 
    int Tpos[7]; 
    QandA[0] = "Question 1"; 
    QandA[1] = "Question 2";//Y to 0 
    QandA[2] = "Question 3";//N to 0 
    QandA[3] = "answer 1";//Y to 1 
    QandA[4] = "answer 2";//N to 1 
    QandA[5] = "answer 3";//N to 2 
    QandA[6] = "answer ";//Y to 2 

    Tpos[0] = 50; 
    Tpos[1] = 40; 
    Tpos[2] = 60; 
    Tpos[3] = 20; 
    Tpos[4] = 45; 
    Tpos[5] = 70; 
    Tpos[6] = 55; 

    for(int i = 0; i<=6; i++){ 

      mytree.insertdata2(Tpos[i],QandA[i]); 

    } 
    mytree.yesno(); 



    cout<<endl;  
    */ 
    return 0; 
} 

Answer 1

你countNodes方法采用treeNode指针。看起来没有什么办法可以访问根节点，所以这个方法在btree类以外是没用的。

我会做像这样

template<class datatype> 
int btree<datatype>::getNodeCount() const 
{ 
    if (root == NULL) return 0; 
    // Otherwise continue counting from root. 
    ... 

Answer 2

这里是解决这个的一种方式的另一种方法：

在课堂上，一个新的功能：）

template<class datatype> 
class btree{ 
public: 
    ... 
    int countNodes(); 
    int countNodes(treenode<datatype> *p); 
}; 

INT countNodes（以从你的程序中调用。

template<class datatype> 
int btree<datatype>::countNodes(){ 
    return countNodes(root); 
} 

INT countNodes（树节点* P），被内部调用（大概应该是私人的，因为客户端不必访问根结点反正）：

template<class datatype> 
int btree<datatype>::countNodes(treenode<datatype> *p){ 
    int count = 1;  
    if (p == NULL){ 
    return 0; 
    }else{ 
    count += countNodes(p->lchild); 
    count += countNodes(p->rchild); 
    } 
    return count; 
} 

注意的是，实施对于countNodes（treenode * p）也改变了。

然后，在主：

btree<int> genesistree; 
genesistree.insertdata(14); 
genesistree.insertdata(2); 
genesistree.insertdata(34); 
genesistree.insertdata(41); 
genesistree.insertdata(12); 
cout << genesistree.countNodes(); 

打印如图5所示，树的大小。