如何才能C语言编程实现求一棵二叉树的结点总数？急！！！

听不清啊 · 2018-4-30 01:12:52

int countnode(bt *h) //其中bt是二叉树的结点（结构体）
{if(!bt)return 0;
int a,b;
a=countnode(h^.lchild);
b=countnode(h^.rchild);
return a+b+1;
}

水寒三尺 · 2018-4-30 01:12:53

(1)求结点数的递归定义为：
  若为空树，结点数为0
  若只有根结点，则结点数为1；
  否则，结点数为根结点的左子树结点数+右子树结点数+1

(2)求叶子数的递归定义为：
  若为空树，叶子数为0
  若只有根结点，则叶子数为1；
  否则，叶子数为根结点的左子树叶子数+右子树叶子数

typedef char DataType;//定义DataType类型
typedef struct node{
DataType data;
struct node *lchild, *rchild;//左右孩子子树
  }BinTNode; //结点类型
typedef BinTNode *BinTree;//二叉树类型

int Node(BinTree T)
  {//算结点数
if(T)
if (T-> lchild==NULL )&&( T --> rchild==NULL )
   return 1;
else return Node(T-> lchild ) +Node ( T --> rchild )+1;
else return 0;
  }

int Leaf(BinTree T)
  { //算叶子数
if(T)
if (T-> lchild==NULL )&&( T --> rchild==NULL )
   return 1;
else return Leaf(T-> lchild ) +Node ( T --> rchild );
else return 0;
  }

silencesword · 2018-4-30 01:12:54

用递归啊，除了叶子节点以外，每个节点都有左子树和右子树，只要判断子节点不为空就用递归调用函数统一子树的节点数，例如
f（T)=f(L)+f(R)+1;
节点总数等于左子树的节点数+右子树的节点数+1

johnny川 · 2018-4-30 01:12:55

不明白呀，能说的具体点么？

如何才能C语言编程实现求一棵二叉树的结点总数？急！！！

4 个回复

浏览过的版块