23.编写递归算法,对于二叉树中每一个元素值为x的结点,删去以它为根的子树,并释放相应的空间
24.编写算法，对一棵一孩子-兄弟链表表示的树统计其叶子的个数。
typedef struct TreeNode
{
TreeNode *child;
TreeNode *sibling;
int data;
}TreeNode;
//这是用了递归的思想，需要仔细体会
int GetChildeSiblingTreeDegree(TreeNode *root)
{
//如果当前树的根节点没有孩子和兄弟，那么，该树的度就是0
if (root->child == NULL && root->sibling == NULL)
{
return 0;
}
//如果该树只有兄弟，则该树的度就等效于对他的兄弟分支的子树求度
else if( root->sibling != NULL)
{
return GetChildeSiblingTreeDegree(root->sibling);
}
//如果该树只有孩子，那么先求出该根节点的度，然后再对它孩子分支子树求度，两者取较大者，即该树的度
else if(root->child != NULL)
{
int rootDegree = 1;
TreeNode *p = root->child;
while(p->sibling != NULL)
{
p = p->sibling;
rootDegree++;
}
int childTreeDegree = GetChildeSiblingTreeDegree(root->child);
return rootDegree > childTreeDegree ? rootDegree : childTreeDegree;
}
}
25.对以孩子-兄弟链表表示的树编写计算树的深度的算法
//计算孩子链表表示树的深度
int getDepth(CTree T){
int front=rear=tail=-1;//tail为层最后一个结点
ChildPtr queue[maxSize];
ChildPtr p,q;
ChildPtr root=T->nodes[T->r];
queue[++rear]=root;tail++;
if(root){
int depth=0;
while(front<rear){
while(front<tail){
p=queue[++front];
q=p->next;
while(q){//将p结点所有孩子加入队列
queue[++rear]=q;
q=q->next;
}
}
tail=rear;//此时tail为当前p孩子结点层的最后一个结点
depth++;
}
return depth;
}else
return 0;
}
26.设二叉树按二叉链表存储，写算法判别一棵二叉树是否是一棵正则二叉树。正则二叉树是指在二叉树中不存在子树个数为1的节点。
int IsNormalTree(BiTree bt) ///判断是否为正则树，待完善算法？？？
{
int flag1,flag2;
if(bt)
{
if(bt->lchild && bt->rchild && bt->lchild->data!=' ' && bt->rchild->data!=' ')
{
IsNormalTree(bt->lchild);
IsNormalTree(bt->rchild);
return 1;
}
else if(!bt->lchild&&!bt->rchild)
{
return 1;
}
else return 0;
}
}
27.计算二叉树的最大宽度
int TreeWidth(TreeNode* node) {
if (node == nullptr) {
return 0;
}
std::queue<TreeNode*> q;
int max_witdth = 1; // 最大宽度
q.add(node); // 入队
while (!q.empty()) {
int len = q.size(); // 当前层的节点个数
while (len--) { // 如果当前层，还有节点
TreeNode* t = q.front();
q.pop();
if (t->left != nullptr) {
q.add(t->left); // 下一层节点入队
}
if (t->right != nullptr) {
q.add(t->right); // 下一层节点入队
}
}
max_witdth = std::max(max_witdth, q.size());
}
return max_witdth;
}
28.已知二叉树按照二叉链表方式存储，利用栈的基本操作写出先序遍历非递归形式的算法。
29.已知二叉树按照二叉链表方式存储，编写算法，将二叉树左右子树进行交换
29.编写遍历前序线索树的算法
30.把一个顺序存在一维数组中的完全二叉树按先序遍历访问
#include <stdio.h>
int count=7;
int a[8]={0,1,2,3,4,5,6,7};
void fun(int i)
{
if (i<=count)
{
printf("%d",a[i]);
fun(2*i);
fun(2*i+1);
}
}
int main()
{
fun(1);
putchar('\n');
return 0;
}
30.利用中序和前序构建一棵二叉树算法
typedef struct Node{
int value;
struct Node *left;
struct Node *right;
}Node;
int Find(char array[], int size, char v){
for (int i = 0; i < size; i++){
if (array[i] == v){
return i;
}
}
return -1;
}
Node * BuildTree(char preorder[],char inorder[], int size){
if (size == 0){
return NULL;
}
char rootValue = preorder[0];
int leftSize = Find(inorder, size, rootValue);//i的返回值就是左子树的个数
//根
Node *root = (Node *)malloc(sizeof(Node));
root->value = rootValue;
//左子树
root->left = BuildTree(preorder + 1,inorder,leftSize);
//右子树
root->right = BuildTree(preorder + 1 + leftSize, inorder + leftSize + 1, size-1-leftSize);
return root;
}
31.假设具有n个顶点的连通带权图中所有边的权值均为从1到n之间的整数，能对Kruskal算法进行任何更改，时间复杂性能改进到何程度?若对某常量N,所有边的权值均为从1到N之间的整数，在这种情况下又如何?在上述两种情况下，对Prim算法能进行何改进?
Prim算法的主要运算在于寻找顶点分别在V-U与U .中边权最小的边，找出这样的边后再对U，lowcost和closest进行调整。如果用一个优先队列来完成这些工作，则要求优先队列支持DELETEMIN 和DESCREASE_ KEY运算。如果采用Fibonacci堆来实现优先队列则可以在O(VlogV)时间内完成对优先队列的所有操作。因此，Prim 算法可以在O(EI+IV log|V)时间内完成。如果边权是1到常数N之间的整数，我们可以用一个数组Q[0..N+1]来表示优先队列。如果其中N+1单元存储+∞，其余各单元存储顶点的双链表，其权值等于数组下标。这样一来，DELETEMIN和DECREASE_ KEY都只要O(1 )时间,从而可在O(E)时间内完成Prim算法。
如果边权是1到n之间的整数，则上述方法就不适用了。此时，DECREASE_ KEY仍可在O(1 )时间内完成，但DELETEMIN 运算需要O(n)时间。完成Prim算法就需要O(El+n2)时间。如果用van Emde .Boas优先队列，则可在nloglogn时间内完成所有优先队列操作，从而可在O(El+nloglogn)时间内完成Prim算法，这超出了我们的讨论的范围。
31.采用邻接表存储结构，编写一个判别无向图中任意给定的两个顶点之间是否存在一条长度为k的简单路径的算法（一条路径为简单路径指的是其顶点序列中不含有重现的顶点)。
void DFS(ALGraph G, int i, int j,int k, Status on[], Status &found)
{
Static int n = 0;//记录当前路径上的顶点个数
ArcNode *p;
on[i] = TRUE;
n++;
if(i == j && n == k+1)
found = TRUE;
else
{
p = G.vertices[i].firstarc;
while(!found && p != NULL)
{
if(!on[p->adjvex])
DFS(G, p->adjvex, j, k, on ,found);
p = p->nextarc;
}
}
on[i] = FALSE;//回退操作
n--;
}
Status SimplePath(ALGraph G, int i, int j, int k)
{
int m;
Status on[MAX_VERTEX_NUM];
Status found;
for(m = 1; m <= G.vexnum; m++)
on[m] = FALSE;
found = FALSE;
DFS(G, i, j, k, on, found);
return found;
}
33.试利用栈的基本操作编写，按深度优先搜索策略 遍历一个强连通图的非递归形式的算法。算法中不规定具 体的存储结构，而将图Graph看成是一种抽象的数据类型。
34.试基于图的深度优先搜索策略写一算法， 判别以邻接表方式存储的有向图中是否存在由顶 点vi到顶点vj的路径(i≠j)。 注意：算法中涉及 的图的基本操作必须在此存储结构上实现。
35.同上题要求。试基于图的广度优先搜索策略写一算法。
36.试在邻接矩阵存储结构上实现图的基本操作：InsertVextex(G,v),InsertArc(G,v,w),DeleteVertex(G,v)和DeleteArc(G,v,w).
Status Delete_Arc(MGraph &G,char v,char w)//在邻接矩阵表示的图G上删除边(v,w)
{
if((i=LocateVex(G,v))<0) return ERROR;
if((j=LocateVex(G,w))<0) return ERROR;
if(G.arcs[i][j].adj)
{
G.arcs[i][j].adj=0;
G.arcnum--;
}
return OK;
}//Delete_Arc
37.编写算法，由依次输入的顶点数目，弧数目，和各个弧信息建立有向图的邻接表
int LocateVex(AdjList *G,VertexData x)/*求顶点位置函数*/
{
int j=error,k;
for(k=0;k<G->vexnum,k++)
if(G->vertex[k]==x)
{
j=k;break;
}
return(j);
}
int CreatDN(AdjList *G)/*创建一个有向图*/
{
int i,j,k;
ArcNode *s;
scanf("%d,%d",&G->vexnum,&G->arcnum);/*输入图的顶点数和弧数*/
for(i=0;i<G->vexnum;i++)/*输入图的顶点*/
{
scanf("%c",&G->vertex[i].data);
G->vertex[i].firstarc=Null;
}
for(k=0;k<G->arcnum;k++)
{
scanf("%c,%c,%d",&v1,&v2,&weight);/*输入一条弧及权值*/
i=LocateVex(G,v1);
j=LocateVex(G,v2);
s=(ArcNode *)malloc(sizeof(ArcNode));
s->adjvex=j;
s->info=weight;
/*采用头插法建立有向图*/
s->nextarc=G->vertex[i].firstarc;
G-vertex[i].firstarc=s;
}
return(ok);
}
38.画出对长度为10的有序表进行折半查找的判定树
39.编写一个类C函数，利用折半查找算法在一个有序表中插入一个元素x，并保持表的有序性。
viod insert_search（int a[ ],int n，elementtype X) //数组时机存放元素个数n应比数组长度小1
{
int low=0, high=n-1, mid，i;
while(low<=high)
{
mid=(low+high)/2;
if ( a[mid]<X) high=mid-1;
else low=mid+1;
}
for(i=n-1;i>=mid;i - -)
a[i+1]=a[i];
a[mid]=X;
}
40.试编写利用折半查找确定记录所在块的分块查找算法。
41.已知长度为12的表：（Jan,Feb,Mar,Apr,May,June,July,Aug,Sep,Oct,Nov,Dec）.
（1）试着按表中的顺序依次插入一棵初始为空的二叉排序树，画出插入完成后的二叉排序树并求其等概率的情况下查找成功的平均查找长度。
（2）若对表中的元素先进行排序成有序表，求在等概率的情况下对此有序表进行折半查找时查找成功的平均查找长度。
（3）按表中元素的顺序依次构造一棵平衡二叉树，并求其等概率情况下查找成功的平均查找长度。
