Question

若用二叉链表作为二叉树的存储表示，试针对以下问题编写算法：统计二叉树终结点的个数

要使用C++编写的 谢拉

Answer 1

void CountLeaf (BiTree T, int& count)
{ //递归方法，
if ( T )
{
if ((!T->lchild)&& (!T->rchild))
count++;
CountLeaf( T->lchild, count); // 统计左子树中叶子结点个数
CountLeaf( T->rchild, count); // 统计右子树中叶子结点个数
}
}
----------
非递归，就是采用前序/中序/后序遍历所有节点，并统计。下面就给你提供分别用三个函数的统计方法(PS：因为计数器定义为全局，所以三个函数不能同时使用，使用其中一个就能统计你要的节点数)。
#include "stdlib.h"
#define MAXNODE 20
#define ISIZE 8
#define NSIZE0 7
#define NSIZE1 8
#define NSIZE2 15
//SHOWCHAR = 1(显示字符) SHOWCHAR = 0(显示数字)
#define SHOWCHAR 1

//二叉树结构体
struct BTNode
{
int data;
BTNode *rchild;
BTNode *lchild;
};
//非递归遍堆栈
struct ABTStack
{
BTNode *ptree;
ABTStack *link;
};
static pCounter = 0; //计数器，记录节点个数
/*
前序遍历函数pre_Order_Access()<非递归算法>
参数描述：
BTNode *head: 根节点指针
*/
void pre_Order_Access(BTNode *head)
{
BTNode *pt;
ABTStack *ps,*top;
pt = head;
top = NULL;
printf("\n二叉树的前序遍历结果<非递归>：\t");
while(pt!=NULL ||top!=NULL) /*未遍历完,或堆栈非空*/
{
while(pt!=NULL)
{
if(SHOWCHAR)
printf("%c ",pt->data); /*访问根节点*/
else
printf("%d ",pt->data); /*访问根节点*/
ps = (ABTStack *)malloc(sizeof(ABTStack)); /*根节点进栈*/
ps->ptree = pt;
ps->link = top;
top = ps;
pt = pt->lchild; /*遍历节点右子树,经过的节点依次进栈*/
pCounter++;
}
if(top!=NULL)
{
pt = top->ptree; /*栈顶节点出栈*/
ps = top;
top = top->link;
free(ps); /*释放栈顶节点空间*/
pt = pt->rchild; /*遍历节点右子树*/
}
}
}

/*
中序遍历函数mid_Order_Access()<非递归算法>
参数描述：
BTNode *head: 根节点指针
*/
void mid_Order_Access(BTNode *head)
{
BTNode *pt;
ABTStack *ps,*top;
int counter =1;
pt = head;
top = NULL;
printf("\n二叉树的中序遍历结果<非递归>：\t");
while(pt!=NULL ||top!=NULL) /*未遍历完,或堆栈非空*/
{
while(pt!=NULL)
{
ps = (ABTStack *)malloc(sizeof(ABTStack)); /*根节点进栈*/
ps->ptree = pt;
ps->link = top;
top = ps;
pt = pt->lchild; /*遍历节点右子树,经过的节点依次进栈*/
pCounter++;
}
if(top!=NULL)
{
pt = top->ptree; /*栈顶节点出栈*/
ps = top;
top = top->link;
free(ps); /*释放栈顶节点空间*/
if(SHOWCHAR)
printf("%c ",pt->data); /*访问根节点*/
else
printf("%d ",pt->data); /*访问根节点*/
pt = pt->rchild; /*遍历节点右子树*/
}
}
}

/*
后序遍历函数last_Order_Access()<非递归算法>
参数描述：
BTNode *head: 根节点指针
*/
void last_Order_Access(BTNode *head)
{
BTNode *pt;
ABTStack *ps,*top;
int counter =1;
pt = head;
top = NULL;
printf("\n二叉树的后序遍历结果<非递归>：\t");
while(pt!=NULL ||top!=NULL) /*未遍历完,或堆栈非空*/
{
while(pt!=NULL)
{
ps = (ABTStack *)malloc(sizeof(ABTStack)); /*根节点进栈*/
ps->ptree = pt;
ps->link = top;
top = ps;
pt = pt->lchild; /*遍历节点右子树,经过的节点依次进栈*/
pCounter++;
}
if(top!=NULL)
{
pt = top->ptree; /*栈顶节点出栈*/
ps = top;
top = top->link;
free(ps); /*释放栈顶节点空间*/
printf("%c ",pt->data); /*访问根节点*/
pt = pt->rchild; /*遍历节点右子树*/
}
}
}

Answer 2

int tongji(bitree *t)
{if(t!=NULL)
{i++; /*i的初值是0*/
tongji(t->lchild);
tongji(t->rchild);
}
return(i);
}

Answer 3

遍历的时候计数就好了，树的遍历在任何一本算法书都是例子吧