急求一个关于二叉链表问题的算法题

来源:百度知道 编辑:UC知道 时间:2024/09/21 13:39:30
假设以二叉链表作为二叉树的存储结构,试定义二叉链表数据类型,并编写求二叉树叶结点数的算法。

(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;
}

6.23 以二叉链表为存储结构,分别写出求二叉树结点总数及叶子总数的算法。

解:
(1)求结点数的递归定