写一个算法 统计二叉树结点个数递归做

这是我们老师给我们写的二叉树最基本的.......追加、删除节点的程序，很简单，但是也不简单，如果你基础比较好，这个可以忽略，如果不好，看看也无妨，打酱油路过.......呵呵

#include <iostream>
using namespace std;
// 二叉搜索树
class BsTree {
public:
// 构造函数中初始化为空树
BsTree (void) : m_root (NULL), m_size (0) {}
// 析构函数中释放剩余节点
~BsTree (void) {
Clear ();
}
// 插入数据
void Insert (int data) {
Insert (new Node (data), m_root);
m_size++;
}
// 删除数据，不存在返回false
bool Remove (int data) {
Node*& find = Find (data, m_root);
if (find) {
Insert (find -> m_left, find -> m_right);
Node* node = find;
find = find -> m_right;
delete node;
m_size--;
return true;
}
return false;
}
// 删除所有值为data的数据
void RemoveAll (int data) {
while (Remove (data));
}
// 清空树
void Clear (void) {
Clear (m_root);
m_size = 0;
}
// 将全部old更新为_new
void Update (int old, int _new) {
while (Remove (old))
Insert (_new);
}
// 能否找到data
bool Find (int data) {
return Find (data, m_root) != NULL;
}
// 中序遍历
void Travel (void) {
cout << '{';
Travel (m_root);
cout << '}' << endl;
}
// 获取树的大小
size_t GetSize (void) {
return m_size;
}
// 获取树的高度
size_t GetHeight (void) {
return GetHeight (m_root);
}
private:
// 节点
class Node {
public:
Node (int data) : m_data (data), m_left (NULL), m_right (NULL) {}
int m_data; // 数据
Node* m_left; // 左树
Node* m_right; // 右树
};
void Insert (Node* node, Node*& tree) {
if (! tree)
tree = node;
else if (node) {
if (node -> m_data < tree -> m_data)
Insert (node, tree -> m_left);
else
Insert (node, tree -> m_right);
}
}
Node*& Find (int data, Node*& tree) {
if (! tree)
return tree;
else
if (data == tree -> m_data)
return tree;
else
if (data < tree -> m_data)
return Find (data, tree -> m_left);
else
return Find (data, tree -> m_right);
}
void Clear (Node*& tree) {
if (tree) {
Clear (tree -> m_left);
Clear (tree -> m_right);
delete tree;
tree = NULL;
}
}
void Travel (Node*& tree) {
if (tree) {
Travel (tree -> m_left);
cout << ' ' << tree -> m_data << ' ';
Travel (tree -> m_right);
}
}
size_t GetHeight (Node*& tree) {
if (tree) {
size_t lh = GetHeight (tree -> m_left);
size_t rh = GetHeight (tree -> m_right);
return (lh > rh ? lh : rh) + 1;
}
return 0;
}
Node* m_root; // 树根
size_t m_size; // 树的大小
};
int main (void) {
BsTree bs;
bs.Insert (50);
bs.Insert (70);
bs.Insert (20);
bs.Insert (60);
bs.Insert (40);
bs.Insert (30);
bs.Insert (10);
bs.Insert (90);
bs.Insert (80);
bs.Travel ();
cout << bs.GetSize () << ", " << bs.GetHeight () << endl;
cout << boolalpha << bs.Find (3) << endl;
cout << boolalpha << bs.Find (10) << endl;
bs.Remove (60);
bs.Remove (30);
bs.Travel ();
bs.Insert (40);
bs.Insert (40);
bs.Travel ();
bs.RemoveAll (40);
bs.Travel ();
bs.Insert (70);
bs.Insert (70);
bs.Travel ();
bs.Update (70, 75);
bs.Travel ();
bs.Clear ();
bs.Travel ();
return 0;
}

int count(BiTree *t)
{
if(t==NULL)
return 0;

int left=0,right=0;

if(t->lchild!=NULL)
left=count(t->lchild);
if(t->rchild!=NULL)
right=count(t->rchild);

return left+right+1;
}