Project1.zip

#include<stdio.h> #include<string.h> #include<stdlib.h> typedef char elemtype[20]; typedef struct z { elemtype data; struct z* lchild, * rchild; }bitnode, * bitree; typedef bitree selemtype; typedef struct { int top; int stacksize; elemtype* data; }sqstack; //初始化 int initsqstack(sqstack* ls) { ls->data = (elemtype*)malloc(sizeof(elemtype) * 20); ls->top = -1; ls->stacksize = 20; return 1; } //判空 int emptysqstack(sqstack s) { if (s.top == -1) return 1; else return 0; } //取栈顶 int gettopsqstack(sqstack s, char** e) { if (s.top == -1) return 0; else *e = s.data[s.top]; return 1; } //进栈 int pushsqstack(sqstack* ls, elemtype ch) { if (ls->top + 1 == ls->stacksize) return 0; else ls->top++; strcpy(ls->data[ls->top], ch); return 1; } //出栈 int popsqstack(sqstack* ls, char* e)//栈内元素为字符串 { if (ls->top == -1) return 0; else { strcpy(e, ls->data[ls->top]);//e ls->top--; return 1; } } //遍历栈(从栈顶到栈底） int toptravelsqstack(sqstack s) { int i; printf("%s", s.data[s.top]); for (i = s.top-1; i >= 0; i--) { printf(" %s", s.data[i]); } printf("\n"); return 1; } int bottomtravel(sqstack s)//从栈底到栈顶 { int i; printf("%s", s.data[0]); for (i = 1; i <= s.top; i++) { printf(" %s", s.data[i]); } //printf("\n"); return 1; } typedef struct s { selemtype data; struct s* next; }qnode, * quenelink; typedef struct { quenelink rear; quenelink front; }qlink; //初始化 int inintquenelink(qlink* q) { q->front = q->rear = (quenelink)malloc(sizeof(qnode)); if (q->front == NULL) return 0; q->front->next = NULL;//指针域置空 return 1; } //判队空 int emptyquenelink(qlink q) { if (q.front == q.rear) return 1; else { return 0; } } //进队（队尾） int pushlinkquene(qlink* q,selemtype ch) { quenelink p = (quenelink)malloc(sizeof(qnode)); if (p == NULL) return 0; p->next = NULL; //尾插法指针域置空 p->data=ch; q->rear->next = p; q->rear = p; return 1; } //取队头 int getheadlinkquene(qlink q,bitree* e) { if (q.front == q.rear) return 0; else { *e=q.front->next->data; } } //出队,队头出队 int delinklinkquene(qlink* q,bitree *e) { quenelink p; if (q->front == q->rear) return 0; p = q->front->next; *e=p->data; q->front->next = p->next; if (q->rear == p)//只有一个元素 { q->rear = q->front;//确保指向头结点 } free(p); return 1; } //先序遍历 void preorder(bitree t) { if (t) { printf("%s ", t->data); preorder(t->lchild); preorder(t->rchild); } } //根左右创建 void cuttree(bitree* t) { char ch[20]; scanf("%s", ch); //getchar();%s就会吸收空格，不用多写 if (strcmp(ch, "#") == 0) *t = NULL;//字符串型的用双引号引起 else { (*t) = (bitree)malloc(sizeof(bitnode)); strcpy((*t)->data, ch);//字符串 cuttree(&(*t)->lchild); cuttree(&(*t)->rchild); } } //凹入表显示 void disbitree(bitree t, int level) { int i; if (t) { for (i = 0; i < level; i++) putchar(' '); printf("%s", t->data); printf("\n"); disbitree(t->lchild, level + 1); disbitree(t->rchild, level + 1); } } //查找某个结点返回指针 void prohebit(bitree t, elemtype ch, bitree* p) { if (t) { if (strcmp(ch, t->data) == 0) *p = t; else { if ((*p) == NULL) prohebit(t->lchild, ch, p); if ((*p) == NULL) prohebit(t->rchild, ch, p); } } } //插入 int insertbitree(bitree* t, elemtype fa,elemtype ch) { bitree p=NULL,s;//先对p赋值空，避免会出现野指针 prohebit(*t, fa, &p); if (p) { s = (bitree)malloc(sizeof(bitnode));//申请新结点 s->lchild = s->rchild = NULL; strcpy(s->data, ch); if (!p->lchild) p->lchild = s;//谁空链接谁 else if (!p->rchild) p->rchild = s; return 1; } return 0; } //删除以某个结点为根的子树 void deletenode(bitree t)//不需要返回指针，形参是bitree类型 { if (t) { deletenode(t->lchild); deletenode(t->rchild); free(t);//只能后序遍历，否则找不到左右子树 } } //删除 int deletetree(bitree* t, elemtype ch) { bitree q; if (!(*t)) return 0; else { if (strcmp(ch, (*t)->data)==0) { q = *t; (*t) = NULL; deletenode(q); return 1; } deletetree(&((*t)->lchild), ch); deletetree(&((*t)->rchild), ch); } } //查找某个结点的路径 int treenodepath(bitree t, elemtype ch,sqstack s) { if (!t) return 0; if (strcmp(ch, t->data) == 0) { elemtype x; if (!emptysqstack(s))//栈里有路径结点 { bottomtravel(s);//从栈底到栈顶遍历 printf(" %s", t->data);//当前结点没入栈 } printf("\n"); return 1; } pushsqstack(&s, t->data);//不是所查询结点则入栈 treenodepath(t->lchild, ch, s);//递归查询 treenodepath(t->rchild, ch, s); char p[20];//字符串传参 popsqstack(&s,p);//叶子结点或者左右子树均没找到的结点出栈 return 0; } //输出所有根到叶子结点路径 void getpath(bitree t,sqstack *s) { char p[20];//存pop出的元素 if (t) { pushsqstack(s, t->data); if (!t->lchild && !t->rchild)//叶子结点 { bottomtravel(*s); printf("\n"); } else { getpath(t->lchild,s);//递归遍历 getpath(t->rchild,s); } popsqstack(s, p);//查询完结点出栈 } } //层次遍历输出 void layer(bitree t) { qlink q; inintquenelink(&q); bitree p; if (t) pushlinkquene(&q, t); while (emptyquenelink(q)) { delinklinkquene(&q, &p); printf("%s ", p->data);//出队的同时左右孩子进队 if (p->lchild) pushlinkquene(&q, p->lchild); if (p->rchild) pushlinkquene(&q, p->rchild); } } //统计叶子结点个数 int countleaf(bitree t) { int m, n; if (!t) return 0;//空树 if (!t->lchild && !t->rchild) return 1;//叶子结点 else { m = countleaf(t->lchild); n = countleaf(t->rchild); return (m + n);//第三种情况由递归得出左右叶子结点数量，最终相加 } } //输出所有叶子结点 void leafprint(bitree t) { if (!t) return; else { leafprint(t->lchild); if (!t->lchild && !t->rchild) printf("%s ", t->data); leafprint(t->rchild); } } //层次输出所有分支结点 void nodeprint(bitree t) { qlink q; inintquenelink(&q); bitree p; if (t) pushlinkquene(&q, t); while (emptyquenelink(q)) { delinklinkquene(&q, &p); if (p->lchild != NULL || p->rchild != NULL) printf("%s ", p->data); if (p->lchild) pushlinkquene(&q, p->lchild); if (p->rchild) pushlinkquene(&q, p->rchild); } } //层次读边法创建二叉链表 void create_tree(bitree* t) { qlink q; inintquenelink(&q); *t = NULL; elemtype fa, ch; int flag; scanf("%s,%s,%d", fa, ch, &flag); getchar(); while (strcmp(ch, "#")!=0)//根节点前和最后一层结点后标志# { bitree p, s=NULL; p = (bitree)malloc(sizeof(bitnode)); strcpy(p->data, ch);//创建孩子结点 p->lchild = p->rchild = NULL; pushlinkquene(&q, p); if (strcmp(fa, "#") == 0) *t = p;//根节点 else//在队列中寻找双亲结点 { getheadlinkquene(q, &s); while (strcmp(s->data, fa) != 0) { delinklinkquene(&q, &s); getheadlinkquene(q, &s);//直到s为双亲结点 } //链接左右孩子 if (flag == 0) s->lchild = p; if (flag == 1) s->rchild = p; } scanf("%s,%s,%d", fa, ch, &flag); getchar(); } } //判断完全二叉树,序号排布，最后一层可以不满 int iscomplete(bitree t) { if (!t) return 0; qlink q; inintquenelink(&q); if (t) pushlinkquene(&q, t); bitree p=NULL; while (!emptyquenelink(q)) { delinklinkquene(&q, &p); if (p) { pushlinkquene(&q, p->lchild); pushlinkquene(&q, p->rchild); } else//出现空指针，队列中剩余全是空指针才是完全二叉树 { while (!emptyquenelink(q)) { delinklinkquene(&q, &p); if (p) return 0; } } } return 1; } //深度 int depthbitree(bitree t) { int m, n; if (!t) return 0; else { m = depthbitree(t->lchild); n = depthbitree(t->rchild); if (m > n) return (m + 1); else { return (n + 1); } } } //结点数 int countnode(bitree t) { int m, n; if (!t) return 0; if (!t->lchild && !t->rchild) return 1