二叉树求叶子结点个数算法（c++）

以前收集的代码，贴给你，希望对你能有所帮助.二叉树的代码实现如下：
// FileName : btree.h#ifndef __BINARY_TREE_H__
#define __BINARY_TREE_H__#include
#include #ifdef _DEBUG
#define DEBUG_NEW new (_NORMAL_BLOCK, THIS_FILE, __LINE__)
#endif#ifdef _DEBUG
#define new DEBUG_NEW
#undef THIS_FILE
static char THIS_FILE[] = __FILE__;
#endif#ifdef _DEBUG
#ifndef ASSERT
#define ASSERT assert
#endif
#else // not _DEBUG
#ifndef ASSERT
#define ASSERT
#endif
#endif // _DEBUGtemplate
class CBTNode
{
public:
T data;
CBTNode *parent;
CBTNode *left;
CBTNode *right;
CBTNode(
T data = T(),
CBTNode *parent = NULL,
CBTNode *left = NULL,
CBTNode *right = NULL
) : data(data), parent(parent), left(left), right(right) {}
};template
class CBTree
{
protected:
CBTNode *m_pNodeRoot;public:
CBTree(CBTNode *initroot = NULL);
~CBTree();
void AssignTo(CBTNode *p);
void Copy(CBTree &p);private:
CBTNode* Copy(CBTNode *p); void DestroyNode(CBTNode *p); void PreOrderTraverse(
const CBTNode *p,
void (*Visit)(const T &data)
) const; void InOrderTraverse(
const CBTNode *p,
void (*Visit)(const T &data)
) const; void PostOrderTraverse(
const CBTNode *p,
void (*Visit)(const T &data)
) const; void GetNodesCount(const CBTNode *p, unsigned int *unCount) const; void GetLeafCount(const CBTNode *p, unsigned int *unCount) const;public:
T& GetNodeData(CBTNode *p);
T GetNodeData(const CBTNode *p) const;
void SetNodeData(CBTNode *p, const T &data);
CBTNode*& GetRoot();
CBTNode* GetRoot() const;
CBTNode*& GetParent(CBTNode *p);
CBTNode* GetParent(const CBTNode *p) const;
CBTNode*& GetLeftChild(CBTNode *p);
CBTNode* GetLeftChild(const CBTNode *p) const;
CBTNode*& GetRightChild(CBTNode *p);
CBTNode* GetRightChild(const CBTNode *p) const;
CBTNode*& GetLeftSibling(CBTNode *p);
CBTNode* GetLeftSiblig(const CBTNode *p) const;
CBTNode*& GetRightSibling(CBTNode *p);
CBTNode* GetRightSibling(const CBTNode *p) const;public:
int IsEmpty() const;
void Destroy();
void PreOrderTraverse(void (*Visit)(const T &data)) const;
void InOrderTraverse(void (*Visit)(const T &data)) const;
void PostOrderTraverse(void (*Visit)(const T &data)) const;
unsigned int GetNodesCount() const; // Get how many nodes
unsigned int GetLeafCount() const;
unsigned int GetDepth() const;
unsigned int GetDepth(const CBTNode *p) const;
};template
inline CBTree::CBTree(CBTNode *initroot) : m_pNodeRoot(initroot)
{
}template
inline CBTree::~CBTree()
{
Destroy();
}template
inline void CBTree::AssignTo(CBTNode *p)
{
ASSERT(p);
m_pNodeRoot = p;
}template
inline void CBTree::Copy(CBTree &p)
{
if (NULL != p.m_pNodeRoot)
m_pNodeRoot = Copy(p.m_pNodeRoot);
else
m_pNodeRoot = NULL;
}template
inline CBTNode* CBTree::Copy(CBTNode *p)
{
if (p)
{
CBTNode *pNewNode = new CBTNode;
if (NULL == pNewNode)
return NULL;
pNewNode->data = p->data;
pNewNode->parent = p->parent;
pNewNode->left = Copy(p->left);
pNewNode->right = Copy(p->right);
return pNewNode;
}
else
return NULL;
}template
inline CBTNode*& CBTree::GetLeftChild(CBTNode *p)
{
ASSERT(p);
return *(&(p->left));
}template
inline CBTNode* CBTree::GetLeftChild(const CBTNode *p) const
{
ASSERT(p);
return p->left;
}template
inline CBTNode*& CBTree::GetRightChild(CBTNode *p)
{
ASSERT(p);
return *(&(p->right));
}template
inline CBTNode* CBTree::GetRightChild(const CBTNode *p) const
{
ASSERT(p);
return p->right;
}template
inline CBTNode*& CBTree::GetLeftSibling(CBTNode *p)
{
ASSERT(p); if (p->parent)
return *(&(p->parent->left));
else
return *(&(p->parent)); // return NULL;
}template
inline CBTNode* CBTree::GetLeftSiblig(const CBTNode *p) const
{
ASSERT(p); if (p->parent)
return p->parent->left;
else
return p->parent; // return NULL;
}template
inline CBTNode*& CBTree::GetRightSibling(CBTNode *p)
{
ASSERT(p); if (p->parent)
return *(&(p->parent->right));
else
return *(&(p->parent)); // return NULL;
}template
inline CBTNode* CBTree::GetRightSibling(const CBTNode *p) const
{
ASSERT(p); if (p->parent)
return p->parent->right;
else
return p->parent; // return NULL;
}template
inline CBTNode*& CBTree::GetParent(CBTNode *p)
{
ASSERT(p);
return *(&(p->parent));
}template
inline CBTNode* CBTree::GetParent(const CBTNode *p) const
{
ASSERT(p);
return p->parent;
}template
inline T& CBTree::GetNodeData(CBTNode *p)
{
ASSERT(p);
return p->data;
}template
inline T CBTree::GetNodeData(const CBTNode *p) const
{
ASSERT(p);
return p->data;
}template
inline void CBTree::SetNodeData(CBTNode *p, const T &data)
{
ASSERT(p);
p->data = data;
}template
inline int CBTree::IsEmpty() const
{
return NULL == m_pNodeRoot;
}template
inline CBTNode*& CBTree::GetRoot()
{
return *(&(m_pNodeRoot));
}template
inline CBTNode* CBTree::GetRoot() const
{
return m_pNodeRoot;
}template
inline void CBTree::DestroyNode(CBTNode *p)
{
if (p)
{
DestroyNode(p->left);
DestroyNode(p->right);
delete p;
}
}template
inline void CBTree::Destroy()
{
DestroyNode(m_pNodeRoot);
m_pNodeRoot = NULL;
}template
inline void CBTree::PreOrderTraverse(void (*Visit)(const T &data)) const
{
PreOrderTraverse(m_pNodeRoot, Visit);
}template
inline void CBTree::PreOrderTraverse(
const CBTNode *p,
void (*Visit)(const T &data)
) const
{
if (p)
{
Visit(p->data);
PreOrderTraverse(p->left, Visit);
PreOrderTraverse(p->right, Visit);
}
}template
inline void CBTree::InOrderTraverse(void (*Visit)(const T &data)) const
{
InOrderTraverse(m_pNodeRoot, Visit);
}template
inline void CBTree::InOrderTraverse(
const CBTNode *p,
void (*Visit)(const T &data)
) const
{
if (p)
{
InOrderTraverse(p->left, Visit);
Visit(p->data);
InOrderTraverse(p->right, Visit);
}
}template
inline void CBTree::PostOrderTraverse(void (*Visit)(const T &data)) const
{
PostOrderTraverse(m_pNodeRoot, Visit);
}template
inline void CBTree::PostOrderTraverse(
const CBTNode *p,
void (*Visit)(const T &data)
) const
{
if (p)
{
PostOrderTraverse(p->left, Visit);
PostOrderTraverse(p->right, Visit);
Visit(p->data);
}
}template
inline unsigned int CBTree::GetNodesCount() const
{
unsigned int unCount;
GetNodesCount(m_pNodeRoot, &unCount);
return unCount;
}template
inline void CBTree::GetNodesCount(
const CBTNode *p,
unsigned int *unCount
) const
{
ASSERT(unCount); unsigned int unLeftCount;
unsigned int unRightCount; if (NULL == p)
*unCount = 0;
else if ((NULL == p->left) && (NULL == p->right))
*unCount = 1;
else
{
GetNodesCount(p->left, &unLeftCount);
GetNodesCount(p->right, &unRightCount);
*unCount = 1 + unLeftCount + unRightCount;
}
}template
inline unsigned int CBTree::GetLeafCount() const
{
unsigned int unCount = 0;
GetLeafCount(m_pNodeRoot, &unCount);
return unCount;
}template
inline void CBTree::GetLeafCount(
const CBTNode *p,
unsigned int *unCount
) const
{
ASSERT(unCount); if (p)
{
// if the node's left & right children are both NULL, it must be a leaf
if ((NULL == p->left) && (NULL == p->right))
++(*unCount);
GetLeafCount(p->left, unCount);
GetLeafCount(p->right, unCount);
}
}template
inline unsigned int CBTree::GetDepth() const
{
// Minus 1 here because I think the root node's depth should be 0.
// So, don't do it if u think the root node's depth should be 1.
return GetDepth(m_pNodeRoot) - 1;
}template
inline unsigned int CBTree::GetDepth(const CBTNode *p) const
{
unsigned int unDepthLeft;
unsigned int unDepthRight; if (p)
{
unDepthLeft = GetDepth(p->left);
unDepthRight = GetDepth(p->right);
return 1 + // if don't plus 1 here, the tree's depth will be always 0
(unDepthLeft > unDepthRight ? unDepthLeft : unDepthRight);
}
else
return 0;
}#endif // __BINARY_TREE_H__

设计一个计算器，当当前节点的左右孩子结点都没得的时候，计算器增加！

#include
#include
using namespace std;
int geshu=0;
template
struct Node
{
T data;
Node *zuohaizi,*youhaizi;
};
template
class shu
{
public:
zhongshu();
~shu();
void qianli(Node *root);
void zhongli(Node *root);
void houli(Node *root);
void menu();
void yezi(Node*root);
private:
Node *root;
Node* chuangzao();
void xiaochu(Node *root);
};
template
shu::zhongshu()
{
root=chuangzao();
}
template
Node* shu::chuangzao()
{
Node *root;
T ch;
cout<<"请输入结点数据,输入#为空"< cin>>ch;
if(ch=="#")root=NULL;
else
{
root=new Node;
root->data=ch;
root->zuohaizi=chuangzao();
root->youhaizi=chuangzao();
}
return root;
}
template
shu::~shu()
{
if(root!=NULL)
xiaochu(root);
}
template
void shu::qianli(Node*root)
{
if(root==NULL)return;
else
{
cout<data< qianli(root->zuohaizi);
qianli(root->youhaizi);
}
}
template
void shu::zhongli(Node*root)
{
if(root==NULL)return;
else
{
zhongli(root->zuohaizi);
cout<data< zhongli(root->youhaizi);
}
}
template
void shu::houli(Node*root)
{
if(root==NULL)return;
else
{
houli(root->zuohaizi);
houli(root->youhaizi);
cout<data< }
}
template
void shu::xiaochu(Node*root)
{
if(root!=NULL)
{
xiaochu(root->zuohaizi);
xiaochu(root->youhaizi);
delete root;
}
}
template
void shu::menu()
{
int t=1;

while(t!=6)
{
cout<<"1.种树"< cout<<"2.前历你棵树"< cout<<"3.中历你棵树"< cout<<"4.后历你棵树"< cout<<"5.叶子结点"< cout<<"6.结束程序"< cin>>t;
system("cls"); switch(t)
{
case 1:zhongshu();break;
case 2:qianli(root);break;
case 3:zhongli(root);break;
case 4:houli(root);break;
case 5:yezi(root);cout<<"叶子个数为"< default:break;
}
};}
template
void shu::yezi(Node*root)
{
if(root!=NULL)
{
if(root->zuohaizi==NULL&&root->youhaizi==NULL){cout<data< else
{
yezi(root->zuohaizi);
yezi(root->youhaizi);
}
}
else return;
}
int main()
{
shushu1;
shu1.menu(); return 0;
}