二算法设计题
二叉树的遍历算法可写为通用形式例如通用的中序遍历为
void Inorder(BinTreeTvoid(* visit)(DataType x)){
if (T){
Inorder(T>lchildVisit);//遍历左子树
Visit(T>data);//通过函数指针调用它所指的函数来访问结点
Inorder(T>rchildVisit);//遍历右子树
}
}
其中Visit是一个函数指针它指向形如void f(DataType x)的函数因此我们可以将访问结点的操作写在函数f中通过调用语句Inorder(rootf)将f的地址传递给Visit来执行遍历操作请写一个打印结点数据的函数通过调用上述算法来完成书中节的中序遍历
解这个函数如下
void PrintNode(BinTree T)
{
printf(%cT>data);
}
为了验证这个函数是否正确要先建立一棵二叉树然后调用这个中序遍历算法 //定义二叉树链式存储结构
typedef char DataType;//定义DataType类型
typedef struct node{
DataType data;
struct node *lchild *rchild;//左右孩子子树
}BinTNode; //结点类型 typedef BinTNode *BinTree ;//二叉树类型 #include
#include
void CreatBinTree(BinTree *T)//输入序列是先序序列
{ //构造二叉链表T是指向根的指针故修改了*T就修改了实参
char ch;
if ((ch=getchar())== )
*T=NULL;
else{ //读入非空格
*T=(BinTNode *)malloc(sizeof(BinTNode));//生成结点
(*T)>data=ch;
CreatBinTree(&(*T)>lchild); //构造左子树
CreatBinTree(&(*T)>rchild); //构造右子树
}
}
//
void PrintNode(DataType x)
{ //题目要求的打印函数
printf(%cx);
}
//
void Inorder(BinTree Tvoid(* Visit)(DataType x))
{
if(T)
{
Inorder(T>lchildVisit);//遍历左子树
Visit(T>data); //通过函数指针调用它所指的函数访问结点
Inorder(T>rchildVisit);//遍历右子树
}
}
void main()
{ //现在开始测试啦 BinTree root; //定义一个根结点
CreatBinTree(&root); //建立二叉链表
printf(\n);
Inorder(rootPrintNode);//调用函数注意传递的是函数名(它就是地址)
printf(\n);
}
//运行时请输入ab c (注意b后和c后面各两个空格)再回车可生成一个以a为根的两片叶子的二叉树看看打印的结果对不对?
以二叉链表为存储结构分别写出求二叉树结点总数及叶子总数的算法
解利用中序遍历我们很容易地就能找到这个算法每访问一次非空结点就给变量nodes加上; 每访问到一个其左右子树皆空的结点就给变量leaves加上最后就得到结果了
完整程序如下所示 //定义二叉树链式存储结构等内容为方便起见我们将这一段内容存为bintreeh文件以后只在程序中加入这个头文件就是了 //bintreeh 文件开始 typedef char DataType;//定义DataType类型
typedef struct node{
DataType data;
struct node *lchild *rchild;//左右孩子子树
}BinTNode; //结点类型 typedef BinTNode *BinTree ;//二叉树类型 #include
#include
void CreatBinTree(BinTree *T)
{ //构造二叉链表注意:输入序列是先序序列
char ch;
if ((ch=getchar())== )
*T=NULL;
else{ //读入非空格
*T=(BinTNode *)malloc(sizeof(BinTNode));//生成结点
(*T)>data=ch;
CreatBinTree(&(*T)>lchild); //构造左子树
CreatBinTree(&(*T)>rchild); //构造右子树
}
}//文件结束 //以下两个函数为题目要求算法 int Node(BinTree T)
{ //算结点数
int static nodes=;//静态变量保留每次递归调用后的值
if(T)
{ //使用中序遍历
Node(T>lchild); //遍历左子树
nodes++; //结点数加
Node(T>rchild); //遍历右子树
}
return nodes;
} int Leaf(BinTree T)
{ //算叶子数
int static leaves=;//静态变量保证其值不会随递归调用而消失
if(T)
{ //使用中序遍历
Leaf(T>lchild); //遍历左子树
if(!(T>lchild||T>rchild))//左右孩子均为空
leaves++; //叶子数加
Leaf(T>rchild); //遍历右子树
}
return leaves;
}//算法结束 #include
void main()
{ //测试程序
BinTree root;
CreatBinTree(&root);
int nodes=Node(root);
int leaves=Leaf(root);
printf(\nnodes=%d leaves=%dnodesleaves);
}
以二叉链表为存储结构分别写出求二叉树高度及宽度的算法所谓宽度是指二叉树的各层上具有结点数最多的那一层上的结点总数
解要想求出二叉树的高度可以采用前序遍历设一个个记录高度的变量h 在访问结点时查询该结点是否有孩子有则高度加其中根结点比特殊自身算一层 要求二叉树的宽度的话则可根据树的高度设置一个数组在访问结点时计算该结点下一层的孩子数并存入相应数组元素中遍历左子树后向上返回一层计算右子树的宽度并取出最大的一个数组元素作为树的宽度
#include
#include bintreeh
#define M //假设二叉树最多的层数
int Height(BinTree T)//求树的深度
{ //求深度算法由阮允准更正在此深表感谢
int lhighrhighhigh=;
if(T!=NULL)
{
lhigh=Height(T>lchild);//左子树高度
rhigh=Height(T>rchild);//右子树高度
high=(lhigh>rhigh?lhigh:rhigh)+;//树的高度等于左子树右子树之间的大者加上根结点
}
return high;
} int Width(BinTree T)
{
int static n[M];//向量存放各层结点数
int static i=;
int static max=;//最大宽度
if(T)
{
if(i==) //若是访问根结点
{
n[i]++; //第层加
i++; //到第层
if(T>lchild)//若有左孩子则该层加
n[i]++;
if(T>rchild)//若有右孩子则该层加
n[i]++;
}
else
{ //访问子树结点
i++; //下一层结点数
if(T>lchild)
n[i]++;
if(T>rchild)
n[i]++;
}
if(max Width(T->lchild);//遍历左子树
i--; //往上退一层
Width(T->rchild);//遍历右子树
}
return max;
}//算法结束 void main()
{ //测试程序
BinTree root;
CreatBinTree (&root);
printf("\nHeight of BinTree:%d",Height(root));
printf("\nWidth of BinTree:%d",Width(root));
}
6.25 以二叉链表为存储结构， 写一算法交换各结点的左右子树。TW.WinGwiT.Com
要交换各结点的左右子树，最方便的办法是用后序遍历算法，每访问一个结点时把两棵子树的指针进行交换，最后一次访问是交换根结点的子树。
#include
#include "bintree.h"
void ChangeBinTree(BinTree *T)
{ //交换子树
if(*T)
{ //这里以指针为参数使得交换在实参的结点上进行
//后序遍历
BinTree temp;
ChangeBinTree(&(*T)->lchild);
ChangeBinTree(&(*T)->rchild);
temp=(*T)->lchild;
(*T)->lchild=(*T)->rchild;
(*T)->rchild=temp;
}
}
void PrintNode(BinTree T)
{ //以前序序列打印结点数据
if(T)
{
printf("%c",T->data);
PrintNode(T->lchild);
