【数据结构填空题】关于递归求二叉树度为2的数目【C/C++编程】【数据结构填空题】关于递归求二叉树度为2的数目【C/C++编程】

62 阅读 0 评论 41 点赞

我是靠谱客的博主欣喜歌曲，最近开发中收集的这篇文章主要介绍【数据结构填空题】关于递归求二叉树度为2的数目【C/C++编程】【数据结构填空题】关于递归求二叉树度为2的数目【C/C++编程】，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

【数据结构填空题】关于递归求二叉树度为2的数目【C/C++编程】

前言：
昨天跟同学研究这道题目;然后一直在想,想出来了很多种,但是都是由于第二个if的原因最后递归调用不到.
因为我是从低向上去想这道题目的,然后填空的.最后还是经过不断努力还是想出来了.

题目如下:
二又链表类型定义：
typedef struct BiTNode{
TElemType data;
struct BiTNode *lchild,*rchild;
},BiTNode,*BiTree;
算法binode (BiTree T）实现计算二叉树T中度为2的节点数目.
请在空确处填写合适的内容，使其成为完整的算法。
int binode (BiTree T）/计算二叉树T中度为2的结点的数目/
{
if(NULL==T）return （1）；
if(（2））return1；
return binode(T->lchild)+binode（3）
}

题目:二又链表类型定义：

typedef struct BiTNode{
  TElemType data;
  struct BiTNode *lchild,*rchild;
},BiTNode,*BiTree;

/*
算法binode (BiTree T）实现计算二叉树T中度为2的节点数目.
请在空确处填写合适的内容，使其成为完整的算法。
*/
int binode (BiTree T）/*计算二叉树T中度为2的结点的数目*/
{
   if(NULL==T）return  （1）；
   if(（2））return1；
  return binode(T->lchild)+binode（3）
}

图片版题目
我们先画个二叉树作参考（度为2的的数目为2个）,本二叉树的先序遍历为A—B—D—E—C—F—G

int binode(Bitree T) {
	if (T == NULL) return 0;
	if (T->lchild != NULL && T->rchild != NULL &&
	T->lchild->lchild == NULL && T->lchild->rchild == NULL &&
        T->rchild->lchild == NULL  && T->rchild->rchild == NULL) return 1;
	printf("t%c", T->data);
	return B(T->lchild) + B(T->rchild)+(T->rchild!=NULL && T->lchild!=NULL? 1:0);
}

第一空:0
第二空:T->lchild != NULL && T->rchild != NULL &&T->lchild->lchild == NULL && T->lchild->rchild == NULL &&T->rchild->lchild == NULL && T->rchild->rchild == NULL
注:第二空也可直接写false
第三空:(T->rchild)+(T->rchild!=NULL && T->lchild!=NULL? 1:0)

运行结果

在让我们测试另一颗二叉树

这是一棵有3个度为2的节点
先序遍历为A—B—D—E—C—F—G—H

度为2的的数目为3个

运行结果

以上为本人的答案;其实计算二叉树度为2的数目，我们一般这样写

int binode(Bitree T) {
	if (T == NULL) return 0;
	if(T->lchild != NULL &&T->rchild != NULL)  return B(T->lchild)+B(T->rchild)+1;
	return B(T->lchild)+B(T->rchild);
}