计算机软件技术(第二部分 数据结构).ppt

电子工程学院 * 二叉树的广度优先遍历算法 void layer(BiTree *T) { BiTree *p; SqQueue *Q; InitQueue(Q); //初始化队列 if (T!=NULL) { Q-rear=(Q-rear+1)%MAXSIZE; //修改循环队列尾指针 Q-data[Q-rear]=T; //入队 while (Q-front !=Q-rear) //循环队列非空 { Q-front=(Q-front+1)%MAXSIZE; //修改队头指针 p=Q-data[Q-front]; //出队 printf(%c,p-data); if (p-lchild!=NULL) //左子树非空 { Q-rear=(Q-rear+1)%MAXSIZE; Q-data[Q-rear]=p-lchild; //左子树根结点入队 } if (p-rchild!=NULL) //右子树非空 { Q-rear=(Q-rear+1)%MAXSIZE; Q-data[Q-rear]=p-rchild; //右子树根结点入队 } } } } 电子工程学院 * 【例】二叉树的广度优先遍历 输出序列为：A,B,C,D,E,F,G 电子工程学院 * （4）从遍历序列恢复二叉树 由DLR和LDR的遍历序列可以唯一地确定一棵二叉树； 由LRD和LDR的遍历序列可以唯一地确定一棵二叉树。 通过DLR或者LRD的遍历序列确定二叉树或子树的根结点；通过LDR确定左、右子树的序列。 电子工程学院 * 【例】由先序序列 { ABHFDECKG } 和中序序列 { HBDFAEKCG }恢复二叉树的过程。 电子工程学院 * （5）深度优先递归算法的应用 ① 统计二叉树的叶子结点数 int count =0; int countleaf(bitree *p) { if ( p != NULL ){ count = countleaf( p-lchild );  // 对左子树上的叶子结点计数  if ( (p-lchild= =NULL)(p-rchild= =NULL))  count=count+1;count = countleaf(p-rchild);  // 对右子树上的叶子结点计数 } return count; } 请考虑如何统计度为1的结点个数，度为2的结点个数。 电子工程学院 * ② 利用二叉树后序遍历计算二叉树的深度 int Depth(BiTree *T) { int depL,depR; if (T!=NULL) { depL=Depth(T-lchild); //计算左子树的深度 depR=Depth(T-rchild); //计算右子树的深度 if (depL=depR) return (depL+1); else return (depR+1); //二叉树的深度为左右子树深度较大者加一（根结点） } else return (0); } 电子工程学院 * ③ 求二叉树结点个数 int Size(BiTree *T) { if (T==NULL) return (0); else return (1 + Size (T-lchild ) + Size ( T-rchild)); //二叉树的结点个数是根结点、左右子树结点个数之和 } 电子工程学院 * ④ 交换左右子树 void Exchange(BiTree *T) { BiTree *S; if (T!=NULL) { S=T-lchild; T-lchild=T-rchild; T-rchild=S; Exchange(T-lchild); //在左子树中交换 Exchange(T-rchild); //在右子树中交换 } } 电子工程学院 * ⑤ 利用先序遍历方法，以嵌套括号的形式输出二叉树的层次结构。 void OutBT(BiTree