* 二叉树的遍历算法可写为通用形式例如通用的中序遍历为
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 ;//二叉树类型
void Inorder(BinTree Tvoid(* Visit)(DataType x))
{
if(T)
{
Inorder(T>lchildVisit);//遍历左子树
Visit(T>data); //通过函数指针调用它所指的函数访问结点
Inorder(T>rchildVisit);//遍历右子树
}
}
以二叉链表为存储结构分别写出求二叉树结点总数及叶子总数的算法
解
()求结点数的递归定义为
若为空树结点数为
若只有根结点则结点数为
否则结点数为根结点的左子树结点数+右子树结点数+
()求叶子数的递归定义为
若为空树叶子数为
若只有根结点则叶子数为
否则叶子数为根结点的左子树叶子数+右子树叶子数
typedef char DataType;//定义DataType类型
typedef struct node{
DataType data;
struct node *lchild *rchild;//左右孩子子树
}BinTNode; //结点类型
typedef BinTNode *BinTree ;//二叉树类型
int Node(BinTree T)
{//算结点数
if(T)
if (T>lchild==NULL)&&(T>rchild==NULL)
return ;
else return Node(T>lchild)+Node(T>rchild)+;
else return ;
}
int Leaf(BinTree T)
{ //算叶子数
if(T)
if (T>lchild==NULL)&&(T>rchild==NULL)
return ;
else return Leaf(T>lchild)+Node(T>rchild);
else return ;
}
以二叉链表为存储结构分别写出求二叉树高度及宽度的算法所谓宽度是指二叉树的各层上具有结点数最多的那一层上的结点总数
解
()根据递归定义二叉树的高度为
当为空树时高度为
当只有一个结点时高度为
其他情况高度为max(根的左子树高度根的右子树高度)+
int Height(BinTree T)
{
int hlhr;
if(T)
{//非空树
if(t>lchild==NUll)&&(t>rchild==NULL)//只含一个根结点
return ;
else
{
hl=height(t>lchild);//根的左子树高度
hr=height(t>rchild);//根的右子树高度
if (hl>=hr)
return hl+;
else return h+;
}
}
else return ;
}
()要求二叉树的宽度的话则可根据树的高度设置一个数组temptemp[i]用于存放第i层上的结点数(即宽度)在访问结点时把相应计算该结点下一层的孩子数并存入相应数组元素中遍历左子树后向上返回一层计算右子树的宽度并取出最大的一个数组元素作为树的宽度
#define M //假设二叉树最多的层数
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<n[i])max=n[i];//取出最大值
Width(T>lchild);//遍历左子树
i; //往上退一层
Width(T>rchild);//遍历右子树
}
return max;
}//算法结束
以二叉链表为存储结构 写一算法交换各结点的左右子树
答
要交换各结点的左右子树最方便的办法是用后序遍历算法每访问一个结点时把两棵子树的指针进行交换最后一次访问是交换根结点的子树
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 CopyTree(BinTree root BinTree *newroot)其中新树的结点是动态申请的为什么newroot要说明为BinTree型指针的指针?
解
因为调用函数只能进行值传递当返回类型为void时就必须把实参的地址传给函数否则函数不会对实际参数进行任何操作也就得不到所需结果了所以newroot要说明为BinTree型指针
void CopyTree(BinTree rootBinTree *newroot)
{ //拷贝二叉树
if(root)//如果结点非空
{ //按前序序列拷贝
*newroot=(BinTNode *)malloc(sizeof(BinTNode));//生成新结点
(*newroot)>data=root>data;//拷贝结点数据
CopyTree(root>lchild&(*newroot)>lchild);//拷贝左子树
CopyTree(root>rchild&(*newroot)>rchild);//拷贝右子树
}
else //如果结点为空
*newroot=NULL;//将结点置空
}
以二叉链表为存储结构分别写出在二叉树中查找值为x的结点及求x所在结点在树中层数的算法
解
根据上几题的算法可以得出本题的算法如下
#define M //假设二叉树最多的层数
BinTree SearchBTree(BinTree *TDataType x)
{//以前序遍历算法查找值为x的结点
if(*T)
{
if((*T)>data==x )return *T;
SearchBTree(&(*T)>lchildx);
SearchBTree(&(*T)>rchildx);
}
}
int InLevel(BinTree TDataType x)
{
int static l=;//设一静态变量保存层数
if(T)
{
if(l==)//若是访问根结点
{
l++;//第层
if(T>data==x)return l;
if(T>lchild||T>rchild)
l++;//若根有子树则层数加
}
else
{ //访问子树结点
if(T>data==x)return l;
if(T>lchild||T>rchild)
l++;//若该结点有子树则层数加
else return ;
}
InLevel(T>lchildx);//遍历左子树
InLevel(T>rchildx);//遍历右子树
}
}
一棵n个结点的完全二叉树以向量作为存储结构试写一非递归算法实现对该树的前序遍历
解
以向量为存储结构的完全二叉树其存储在向量中的结点其实是按层次遍历的次序存放的可以根据课本第页的内容设计出算法
typedef char DataType;//设结点数据类型为char
#define M //设结点数不超过
typedef DataType BinTree[M];
void Preorder(BinTree T)
{ //前序遍历算法
int n=T[];
int<
