求二叉树中度为1的结点个数

别团等shy哥发育

发布于 2023-02-27 10:40:37

3860

发布于 2023-02-27 10:40:37

文章被收录于专栏：全栈开发那些事

一、问题引入

已知一颗以二叉链表方式存储的二叉树，编写算法计算二叉树的单孩子的结点数。单孩子是指该结点只有左孩子或只有右孩子(其实就是求度为1的结点个数)

二、算法实现

typedef struct Node {
	DataType data;//数据域
	struct Node *leftchild;//左子树指针
	struct Node *rightchild;//右子树指针
}BiTreeNode;

用递归实现特别简单

//计算二叉树中度为1的结点总数
int leaf_1(BiTreeNode *T) {
	if (T==NULL) {
		return 0;
	}
	if ((T->leftchild == NULL && T->rightchild != NULL) || (T->leftchild != NULL && T->rightchild == NULL))
	{
		return 1 + leaf_1(T->leftchild) + leaf_1(T->rightchild);
	}
	return leaf_1(T->leftchild) + leaf_1(T->rightchild);
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2020-07-25，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法