SearchBTree(&(*T)->rchild,x); } }
int InLevel(BinTree T,DataType x) {
int static l=0;//设一静态变量保存层数 if(T) {
if(l==0)//若是访问根结点 {
l++;//第1层
if(T->data==x)return l; if(T->lchild||T->rchild)
l++;//若根有子树，则层数加1 } else
{ //访问子树结点
if(T->data==x)return l; if(T->lchild||T->rchild)
l++;//若该结点有子树，则层数加1 else return 0; }
InLevel(T->lchild,x);//遍历左子树 InLevel(T->rchild,x);//遍历右子树 } } 关闭
6.28 一棵n个结点的完全二叉树以向量作为存储结构，试写一非递归算法实现对该树的前序遍历。 解：
以向量为存储结构的完全二叉树，其存储在向量中的结点其实是按层次遍历的次序存放的，可以根据课本第74页的内容设计出算法： typedef char DataType;//设结点数据类型为char #define M 100//设结点数不超过100 typedef DataType BinTree[M]; void Preorder(BinTree T) { //前序遍历算法 int n=T[0];
int p[M];//设置一队列存放结点值 int i,j;
for(i=1;i<=n;i++) {
if (i==1)//根结点
j=1;
else if(2*j<=n)//左子树 j=2*j;
else if(j%2==0&&j else if(j>1)//双亲之右兄弟 j=j/2+1; p[i]=T[j];//入队 printf(\打印结点值 } } 关闭 6.29 以二叉链表为存储结构，一算法对二叉树进行层次遍历(层次遍历的定义见6.13).提示：应使用队列来保存各层的结点。 答： #define M 100 //假设结点数最多为100 typedef char DataType;//队列结点值类型 typedef struct//定义一个队列 { int front; int rear; int count; DataType data[M]; }QBTree; static QBTree Q;//设一全局静态变量保存遍历结果 void Levelorder(BinTree T) {//层次遍历 if(T) { if(QueueEmpty(&Q)) { //根结点及子树结点入队 EnQueue(&Q,T->data); if(T->lchild) EnQueue(&Q,T->lchild->data); if(T->rchild) EnQueue(&Q,T->rchild->data); } else { //子树结点入队 if(T->lchild) EnQueue(&Q,T->lchild->data); if(T->rchild) EnQueue(&Q,T->rchild->data); } Levelorder(T->lchild);//遍历左子树 Levelorder(T->rchild);//遍历右子树 } } 关闭 6.30以二叉链表为存储结构，写一算法用括号形式(key LT,RT)打印二叉树，其中key是根结点数据，LT和RT是括号形式的左子树和右子树。并且要求空树不打印任何信息，一个结点x的树的打印形式是x而不是(x,)的形式。 答： 算法如下： void PrintTree(BinTree T) {//打印二叉树 (以前序遍历实现) if(T)//非空树 { printf(\打印结点值 if(T->lchild||T->rchild) printf(\打印括号 PrintTree(T->lchild);//打印左子树 if(T->lchild&&T->rchild) printf(\若存在两棵子树打印逗号 PrintTree(T->rchild);//打印右子树 if(T->lchild||T->rchild) printf(\ } } void PrintTree1(BinTree T) { //由于题目存在两义性，所以这里另作了一个打印算法打印二叉树 (以前序遍历实现) if(T)//非空树 { printf(\打印括号和结点值 PrintTree1(T->lchild);//打印左子树 if(T->lchild&&T->rchild) printf(\ PrintTree1(T->rchild);//打印右子树 printf(\ } } 关闭6.31 以线索链表作为存储结构。分别写出在前序线索树中查找给定结点*p的前序后继，以及在后序线索树中查找 *p的后序前趋的算法。 解： 算法如下： BinThrNode * SearchPostInPre(BinThrNode *p) {//查找结点*p的前序后继 if(p) { if(p->rtag==Link)&&(p->ltag==link)//当左、右都为孩子指针 return p->lchild;//*p的前序后继为左孩子 else return p->rchild; } } BinThrNode *SearchPreInPost(BinThrNode *p) { //查找*p结点的后序前趋 if(p) { if(p->ltag==thread)||(p->rtag==thread)//当有左线索或无有孩子 return p->lchild; //*p的后续前趋为p->lchild else return p->rchild; } } 关闭 6.32 完成6.6.1节算法CreatHuffmanTree中调用的三个函数：InitHuffmanTree,InputWeight 和SelectMin。 解： 整个程序如下： #define n 7 //叶子数目,根据实际需要定义 #define m 2*n-1 //结点数目 typedef struct { float weight; int lchild,rchild,parent;//左右孩子及双亲指针 }HTNode; typedef HTNode HuffmanTree[m];//是向量类型的 void InitHuffmanTree(HuffmanTree T) {//初始化 int i; for (i=0; i T[i].weight=0; T[i].lchild=-1; T[i].rchild=-1; T[i].parent=-1; } } void InputWeight(HuffmanTree T) {//输入权值 float w; int i; for (i=0; i printf(\输入第%d个权值:\ scanf(\ T[i].weight=w; } } void SelectMin(HuffmanTree T, int i, int *p1,int *p2) {//选择两个小的结点 float min1=999999;//预设两个值 float min2=999999;//并使它大于可能出现的最大权值 int j; for (j=0;j<=i;j++) if(T[j].parent==-1) if(T[j].weight min2=min1;//改变最小权，次小权及其位置 min1=T[j].weight;//找出最小的权值 *p2=*p1; *p1=j; } else if(T[j].weight {min2=T[j].weight;//改变次小权及位置 *p2=j;} }//选择结束 关闭 第六章 树（算法设计） *6.22 【答案】二叉树的遍历算法可写为通用形式。例如通用的中序遍历为： void Inorder(BinTree,T,void(* visit)(DataType x)){ if (T){ Inorder(T->lchild,Visit);//遍历左子树 Visit(T->data);//通过函数指针调用它所指的函数来访问结点 Inorder(T->rchild,Visit);//遍历右子树 } }