在二叉树遍历的递归代码基础上衍生出的一类题目

发表于 | 更新于 | 分类于 | 阅读次数：

题目描述

假设二叉树采用二叉链表存储结构，编写算法计算二叉树中既有左孩子又有右孩子的节点数

分析

这种题目通过遍历整个二叉树的全部结点，并对所经过的每一个结点进行如下操作：

  • 判断该结点的左孩子和右孩子是否同时存在，若存在，则说明该结点符合题目要求的条件，计数加1，否则不计数　

算法实现（这里给出两种形式的代码）

代码1

1
2
3
4
5
6
7
8
9
10
int k=0;//计数器初始化为0
int twochild(BiTree Tree){
	if(Tree==NULL) return 0;
	if((Tree->lchild)&&(Tree->rchild)){
		k++;
		twochild(Tree->lchild);
		twochild(Tree->rchild);
	}
	return k;
}

特别要注意的是：

计数变量k必须作为全局变量，否则在每一次进入下一层递归时，k又被初始化为0，从而出错


完整代码实例

  • 首先创建一棵二叉树，形态如下：


  • 算法实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <stdio.h>
#include <stdlib.h>
#define TElemType int
typedef struct BiTNode{
    TElemType data;//数据域
    struct BiTNode *lchild,*rchild;//左右孩子指针
}BiTNode,*BiTree;
void CreateBiTree(BiTree *T){
    *T=(BiTNode*)malloc(sizeof(BiTNode));
    (*T)->data=1;
    (*T)->lchild=(BiTNode*)malloc(sizeof(BiTNode));
    (*T)->lchild->data=2;
    (*T)->rchild=(BiTNode*)malloc(sizeof(BiTNode));
    (*T)->rchild->data=3;
    (*T)->rchild->lchild=NULL;
    (*T)->rchild->rchild=NULL;
    (*T)->lchild->lchild=(BiTNode*)malloc(sizeof(BiTNode));
    (*T)->lchild->lchild->data=4;
    (*T)->lchild->rchild=NULL;
    (*T)->lchild->lchild->lchild=NULL;
    (*T)->lchild->lchild->rchild=NULL;
}
int k=0;
int twochild(BiTree Tree){
	
	if(Tree==NULL) return 0;
	if((Tree->lchild)&&(Tree->rchild)){
		k++;
		twochild(Tree->lchild);
		twochild(Tree->rchild);
	}
	return k;
}
int main() {
	//int k=0;
    BiTree Tree;
    CreateBiTree(&Tree);
    //printf("%d",Tree->lchild->lchild->data);
	int kk=twochild(Tree);
	printf("满足条件的结点数为：%d",kk);
}
  • 输出结果
    1
    满足条件的结点数为：1

代码2

1
2
3
4
5
6
7
8
9
10
11
12
int v2_twochild(BiTree Tree){
	int num1,num2;
	if(Tree==NULL) return 0;
	else{
		num1=v2_twochild(Tree->lchild);
		num2=v2_twochild(Tree->rchild);
	}
	if(Tree->lchild&&Tree->rchild)
		return num1+num2+1;//+1是因为正在被访问的结点满足条件
	else
		return num1+num2;//否则不+1
}

完整代码实例

  • 树的形态同上
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include <stdio.h>
#include <stdlib.h>
#define TElemType int
typedef struct BiTNode{
    TElemType data;//数据域
    struct BiTNode *lchild,*rchild;//左右孩子指针
}BiTNode,*BiTree;
void CreateBiTree(BiTree *T){
    *T=(BiTNode*)malloc(sizeof(BiTNode));
    (*T)->data=1;
    (*T)->lchild=(BiTNode*)malloc(sizeof(BiTNode));
    (*T)->lchild->data=2;
    (*T)->rchild=(BiTNode*)malloc(sizeof(BiTNode));
    (*T)->rchild->data=3;
    (*T)->rchild->lchild=NULL;
    (*T)->rchild->rchild=NULL;
    (*T)->lchild->lchild=(BiTNode*)malloc(sizeof(BiTNode));
    (*T)->lchild->lchild->data=4;
    (*T)->lchild->rchild=NULL;
    (*T)->lchild->lchild->lchild=NULL;
    (*T)->lchild->lchild->rchild=NULL;
}
/*
int k=0;
int twochild(BiTree Tree){
	
	if(Tree==NULL) return 0;
	if((Tree->lchild)&&(Tree->rchild)){
		k++;
		twochild(Tree->lchild);
		twochild(Tree->rchild);
	}
	return k;
}*/



int v2_twochild(BiTree Tree){
	int num1,num2;
	if(Tree==NULL) return 0;
	else{
		num1=v2_twochild(Tree->lchild);
		num2=v2_twochild(Tree->rchild);
	}
	if(Tree->lchild&&Tree->rchild)
		return num1+num2+1;//+1是因为正在被访问的结点满足条件
	else
		return num1+num2;//否则不+1
}

int main() {
	//int k=0;
    BiTree Tree;
    CreateBiTree(&Tree);
    //printf("%d",Tree->lchild->lchild->data);
	int kk=v2_twochild(Tree);
	printf("满足条件的结点数为：%d",kk);
}
  • 输出结果
1
满足条件的结点数为：1

总结

以上两种形式的代码在考题中经常出现，要特别注意第一种写法中的k必须作为全局变量

推广

  • 求解终端结点数，特定度数的结点数等也可以采用以上代码，稍加修改即可
  • 这里给出目前我遇到的类似的题目以及对应的代码实现,以后遇到类似的继续补充

第一题

求二叉树中的非终端结点数

代码1
1
2
3
4
5
6
7
8
9
10
11
int k=0;
int findunleafnode(BiTree Tree){
	if(Tree!=NULL){
		if(Tree->lchild || Tree->rchild){
			k++;
			findunleafnode(Tree->lchild);
			findunleafnode(Tree->rchild);
		}//if
	}//if
	return k;
}

完整代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include <stdio.h>
#include <stdlib.h>
#define TElemType int
typedef struct BiTNode{
    TElemType data;//数据域
    struct BiTNode *lchild,*rchild;//左右孩子指针
}BiTNode,*BiTree;
void CreateBiTree(BiTree *T){
    *T=(BiTNode*)malloc(sizeof(BiTNode));
    (*T)->data=1;
    (*T)->lchild=(BiTNode*)malloc(sizeof(BiTNode));
    (*T)->lchild->data=2;
    (*T)->rchild=(BiTNode*)malloc(sizeof(BiTNode));
    (*T)->rchild->data=3;
    (*T)->rchild->lchild=NULL;
    (*T)->rchild->rchild=NULL;
    (*T)->lchild->lchild=(BiTNode*)malloc(sizeof(BiTNode));
    (*T)->lchild->lchild->data=4;
    (*T)->lchild->rchild=NULL;
    (*T)->lchild->lchild->lchild=NULL;
    (*T)->lchild->lchild->rchild=NULL;
}


int k=0;
int findunleafnode(BiTree Tree){
	if(Tree!=NULL){
		if(Tree->lchild || Tree->rchild){
			k++;
			findunleafnode(Tree->lchild);
			findunleafnode(Tree->rchild);
		}//if
	}//if
	return k;
}

int main() {
	//int k=0;
    BiTree Tree;
    CreateBiTree(&Tree);
    //printf("%d",Tree->lchild->lchild->data);
	//int kk=v2_twochild(Tree);
	int kk=findunleafnode(Tree);
	printf("满足条件的结点数为：%d",kk);
}

运行结果

1
满足条件的结点数为：2
代码2
1
2
3
4
5
6
int v2_findunleafnode(BiTree Tree){
	if(Tree==NULL) return 0;//空树
	else if(Tree->lchild==NULL && Tree->rchild==NULL) return 0;//叶子结点,没有这个就出错了
	else if (Tree->lchild || Tree->rchild)
		return 1+v2_findunleafnode(Tree->lchild)+v2_findunleafnode(Tree->rchild);
}

完整代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <stdio.h>
#include <stdlib.h>
#define TElemType int
typedef struct BiTNode{
    TElemType data;//数据域
    struct BiTNode *lchild,*rchild;//左右孩子指针
}BiTNode,*BiTree;
void CreateBiTree(BiTree *T){
    *T=(BiTNode*)malloc(sizeof(BiTNode));
    (*T)->data=1;
    (*T)->lchild=(BiTNode*)malloc(sizeof(BiTNode));
    (*T)->lchild->data=2;
    (*T)->rchild=(BiTNode*)malloc(sizeof(BiTNode));
    (*T)->rchild->data=3;
    (*T)->rchild->lchild=NULL;
    (*T)->rchild->rchild=NULL;
    (*T)->lchild->lchild=(BiTNode*)malloc(sizeof(BiTNode));
    (*T)->lchild->lchild->data=4;
    (*T)->lchild->rchild=NULL;
    (*T)->lchild->lchild->lchild=NULL;
    (*T)->lchild->lchild->rchild=NULL;
}


int v2_findunleafnode(BiTree Tree){
	if(Tree==NULL) return 0;//空树
	else if(Tree->lchild==NULL && Tree->rchild==NULL) return 0;//叶子结点
	else if (Tree->lchild || Tree->rchild)
		return 1+v2_findunleafnode(Tree->lchild)+v2_findunleafnode(Tree->rchild);
}

int main() {
	//int k=0;
    BiTree Tree;
    CreateBiTree(&Tree);
	int kk=v2_findunleafnode(Tree);
	printf("满足条件的结点数为：%d",kk);
}

运行结果

1
满足条件的结点数为：2

第二题

求二叉树中所有结点数

代码1

1
2
3
4
5
6
7
8
9
int n=0;
int count(BiTree Tree){
	if(Tree!=NULL){
		n++;
		count(Tree->lchild);
		count(Tree->rchild);
	}
	return n;
}

完整代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <stdio.h>
#include <stdlib.h>
#define TElemType int
typedef struct BiTNode{
    TElemType data;//数据域
    struct BiTNode *lchild,*rchild;//左右孩子指针
}BiTNode,*BiTree;
void CreateBiTree(BiTree *T){
    *T=(BiTNode*)malloc(sizeof(BiTNode));
    (*T)->data=1;
    (*T)->lchild=(BiTNode*)malloc(sizeof(BiTNode));
    (*T)->lchild->data=2;
    (*T)->rchild=(BiTNode*)malloc(sizeof(BiTNode));
    (*T)->rchild->data=3;
    (*T)->rchild->lchild=NULL;
    (*T)->rchild->rchild=NULL;
    (*T)->lchild->lchild=(BiTNode*)malloc(sizeof(BiTNode));
    (*T)->lchild->lchild->data=4;
    (*T)->lchild->rchild=NULL;
    (*T)->lchild->lchild->lchild=NULL;
    (*T)->lchild->lchild->rchild=NULL;
}

int n=0;
int count(BiTree Tree){
	if(Tree!=NULL){
		n++;
		count(Tree->lchild);
		count(Tree->rchild);
	}
	return n;
}

int main() {
	//int k=0;
    BiTree Tree;
    CreateBiTree(&Tree);
	int nn=count(Tree);
	printf("满足条件的结点数为：%d",nn);
}

运行结果

1
满足条件的结点数为：4

代码2

1
2
3
4
5
6
7
8
9
int count(BiTree Tree){
	int num1,num2;
	if(Tree==NULL) return 0;
	else{
		num1=count(Tree->lchild);
		num2=count(Tree->rchild);
	}
	return 1+num1+num2;
}

完整代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <stdio.h>
#include <stdlib.h>
#define TElemType int
typedef struct BiTNode{
    TElemType data;//数据域
    struct BiTNode *lchild,*rchild;//左右孩子指针
}BiTNode,*BiTree;
void CreateBiTree(BiTree *T){
    *T=(BiTNode*)malloc(sizeof(BiTNode));
    (*T)->data=1;
    (*T)->lchild=(BiTNode*)malloc(sizeof(BiTNode));
    (*T)->lchild->data=2;
    (*T)->rchild=(BiTNode*)malloc(sizeof(BiTNode));
    (*T)->rchild->data=3;
    (*T)->rchild->lchild=NULL;
    (*T)->rchild->rchild=NULL;
    (*T)->lchild->lchild=(BiTNode*)malloc(sizeof(BiTNode));
    (*T)->lchild->lchild->data=4;
    (*T)->lchild->rchild=NULL;
    (*T)->lchild->lchild->lchild=NULL;
    (*T)->lchild->lchild->rchild=NULL;
}

int count(BiTree Tree){
	int num1,num2;
	if(Tree==NULL) return 0;
	else{
		num1=count(Tree->lchild);
		num2=count(Tree->rchild);
	}
	return 1+num1+num2;
}

int main() {
    BiTree Tree;
    CreateBiTree(&Tree);
	int nn=count(Tree);
	printf("满足条件的结点数为：%d",nn);
}

运行结果

1
满足条件的结点数为：4

第三题

求解二叉链表存储结构下的叶子结点数目

代码1

1
2
3
4
5
6
7
8
9
10
int n=0;
int count(BiTree Tree){
	if(Tree!=NULL){
		//n++;
		if(Tree->lchild==NULL&&Tree->rchild==NULL) n++;
		count(Tree->lchild);
		count(Tree->rchild);
	}
	return n;
}

代码2

1
2
3
4
5
6
7
8
9
10
11
int count(BiTree Tree){
	int num1,num2;
	if(Tree==NULL) return 0;//空树
	else if(Tree->lchild==NULL&&Tree->rchild==NULL) return 1;//只有一个结点（当然该结点为叶子结点），返回1
    //否则该树结点数目大于1，继续遍历其子树
	else{
		num1=count(Tree->lchild);
		num2=count(Tree->rchild);
	}
	return num1+num2;//不用+1，因为要求的是叶子结点数，第一次访问的结点因为有孩子，所以不是叶子结点，所以不用加1
}

第四题

在孩子兄弟链表示的树中求叶子结点数

  • 分析：

    第三题求的是在二叉链表结构存储下的叶子结点数目，这里给的是孩子兄弟存储结构(实质上也是一种二叉链表）

  • 思想：

    若为空树，返回0；
    若长子域（Tree->firstchild）为空，则无孩子，即该结点为叶子结点，计数+1，并接着遍历其兄弟域(Tree->nextsibling)
    以上都不满足，则是第三种情况，即：该结点既有孩子又有兄弟,那就把孩子和兄弟子树都遍历下

  • 在前面的代码基础上，修改树的结构为孩子兄弟结构

    1
    2
    3
    4
    typedef struct CSNode{
        TElemType data;//数据域
        struct CSTNode *firstchild,*nextsibling;//长子兄弟指针
    }CSTNode,*CSTree;

当然，之前创建的树在这里已经不适用，需要重新创建符合要求的孩子兄弟存储结构的一棵树

代码1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int k=0;
int tree_leafconut(CSTree Tree){
	if(Tree==NULL) return 0;
	else{
		if(Tree->firstchild==NULL){
			k++;//无孩子
			tree_leafcount(Tree->nextsibling);//那就遍历兄弟	
		}//if
		else{//有孩子也有兄弟，都需要遍历
			tree->leafcount(Tree->firstchild);
			tree->leafcount(Tree->nextsibling);
		}//else
	
	}//else
	return k;
}

代码2

1
2
3
4
5
6
7
int tree_leafcount(CS Tree){
	if(Tree==NULL) return 0;//空树
	if(Tree->firstchild==NULL)//无孩子，那就去遍历访问兄弟结点试试（如果有的话）
		return 1+tree_leafcount(Tree->nextsibling);
	else//此时该结点既有孩子，也有兄弟
		return tree_leafcount(Tree->firstchild)+tree_leafcount(Tree->nextsibling);
}

more，等遇到再补充

凡希 wechat
喜欢所以热爱，坚持干货分享，欢迎订阅我的微信公众号
呐，请我吃辣条