求二叉树结点总数，求ASCII码最大的结点的层次，详解

求二叉树结点总数 

（1）假设一棵二叉树为A(B(D,E(G,)),C(,F(,H)))，设计一个算法求此二叉树中结点总数并实现。（要求上机实现完整程序代码、核心代码有注释，有运行结果）

解题思路

手绘出二叉树的形状为：

这里使用的是赋值的方法，朴素的搭建起题目要求建的那棵树。

采用递归的方法求出二叉树的结点总数。

总的代码

#include <stdio.h>
#include <stdlib.h>
#include <bits/stdc++.h>
using namespace std;

//定义树的结点
typedef struct bitnode {
	char data;
	struct bitnode *lchild,*rchild;
}bitnode;

int count(bitnode *t) {
	if(t == NULL)
		return 0;
	else return count(t -> lchild) + count(t -> rchild) + 1;
	//采用递归的方法计算结点个数，如果当前结点为空就返回0
}

int main() {
	//初始化树
	bitnode A,B,C,D,E,F,G,H;
	A.data = 'A',A.lchild = &B,A.rchild = &C;
	B.data = 'B',B.lchild = &D,B.rchild = &E;
	C.data = 'C',C.lchild = NULL,C.rchild = &F;
	D.data = 'D',D.lchild = NULL,D.rchild = NULL;
	E.data = 'E',E.lchild = &G,E.rchild = NULL;
	F.data = 'F',F.lchild = NULL,F.rchild = &H;
	G.data = 'G',G.lchild = NULL,G.rchild = NULL;
	H.data = 'H',H.lchild = NULL,H.rchild = NULL;
	
	int num = count(&A);
	
	cout << "二叉树的结点个数为：" << num << endl;
}

运行结果

 求结点中ASCII码最大的和该结点的层次

遍历上述二叉树，求出二叉树中结点ASCII码值最大的结点和该结点的层次（假设根结点层次为1）。（要求程序可执行并附执行结果）

解题思路

我的想法是使用两次先序遍历

        第一次找到ASCII码最大的结点。

        由于先序遍历是一个递归的遍历，如果要找里面的最大值，那么使用一般局部变量和全局变量都不太合适，于是我使用了静态局部变量，确保不会出现定义模糊的情况。

char preorder_max(bitnode *t) {
	static char max = 0;
	//这里采用静态局部变量，防止发生模糊定义的情况
	if(t == NULL)
		return 0;
	if(t -> data > max)
		max = t -> data;
	preorder_max(t -> lchild);
	preorder_max(t -> rchild);
	return max;
}

        第二次先序遍历就可以由这个节点的data值得到它的层次。同样是一个递归的思路，但没上一个好理解，可以边看代码边理解。

int solve(bitnode *t,int max,int h) {
	int l;
	if (t == NULL)
		//如果当前节点为空，返回0
		return 0;
	else if (t -> data == max)
		//如果当前节点的值等于max，返回当前层次h
		return h;
	else 
	//否则,递归在左子树中查找，如果未找到，再在右子树中查找
	{
		l = solve(t -> lchild,max,h+1);	//在左子树中查找
		if (l != 0) 
			//如果找到了，返回结果
			return l;
		else
			//在左子树中未找到，再在右子树中查找
			return(solve(t -> rchild,max,h+1));
	}
}

总的代码

#include <stdio.h>
#include <stdlib.h>
#include <bits/stdc++.h>
using namespace std;

//定义树的结点
typedef struct bitnode {
	char data;
	struct bitnode *lchild,*rchild;
}bitnode;

char preorder_max(bitnode *t) {
	static char max = 0;
	//这里采用静态局部变量，防止发生模糊定义的情况
	if(t == NULL)
		return 0;
	if(t -> data > max)
		max = t -> data;
	preorder_max(t -> lchild);
	preorder_max(t -> rchild);
	return max;
}

int solve(bitnode *t,int max,int h) {
	int l;
	if (t == NULL)
		//如果当前节点为空，返回0
		return 0;
	else if (t -> data == max)
		//如果当前节点的值等于max，返回当前层次h
		return h;
	else 
	//否则,递归在左子树中查找，如果未找到，再在右子树中查找
	{
		l = solve(t -> lchild,max,h+1);	//在左子树中查找
		if (l != 0) 
			//如果找到了，返回结果
			return l;
		else
			//在左子树中未找到，再在右子树中查找
			return(solve(t -> rchild,max,h+1));
	}
}

int main() {
	//初始化树
	bitnode A,B,C,D,E,F,G,H;
	A.data = 'A',A.lchild = &B,A.rchild = &C;
	B.data = 'B',B.lchild = &D,B.rchild = &E;
	C.data = 'C',C.lchild = NULL,C.rchild = &F;
	D.data = 'D',D.lchild = NULL,D.rchild = NULL;
	E.data = 'E',E.lchild = &G,E.rchild = NULL;
	F.data = 'F',F.lchild = NULL,F.rchild = &H;
	G.data = 'G',G.lchild = NULL,G.rchild = NULL;
	H.data = 'H',H.lchild = NULL,H.rchild = NULL;
	
	char max = preorder_max(&A);
	cout << "ASCII码值最大的结点为：";
	cout << max << endl;
	
	int layer = solve(&A,max,1);
	cout << "这个结点的层数为：" << layer << endl;
}

运行结果