1、/* 二叉树的层次遍历 */ #include #include #include #include #define TREEMAX 50 typedef struct node char data; struct node *lchild; struct node *rchild; Node; / 递归创建二叉树 Node *CreateBT() Node *t; char x; scanf(“%c“, fflush(stdin); if(x=#) t=NULL; else t=new Node; t-data=x; printf(“tt 请输入 %c 结点的左子结点 : “,t-data)
2、; t-lchild=CreateBT(); printf(“tt 请输入 %c 结点的右子结点 : “,t-data); t-rchild=CreateBT(); return t; / 递归先序遍历二叉树 void Preorder(Node *T) if(T) printf(“%3c“,T-data); Preorder(T-lchild); Preorder(T-rchild); / 递归中序遍历二叉树 void Inorder(Node *T) if(T) Inorder(T-lchild); printf(“%3c“,T-data); Inorder(T-rchild); / 递归
3、后序遍历二叉树 void Postorder(Node *T) if(T) Postorder(T-lchild); Postorder(T-rchild); printf(“%3c“,T-data); / 非递归先序遍历二叉树 void noRecursivePreorder(Node *T) Node *StTREEMAX,*p; int top=-1; if(T!=NULL) top+; Sttop=T; while(top-1) p=Sttop; top-; printf(“%c“,p-data); if(p-rchild!=NULL) top+; Sttop=p-rchild; if
4、(p-lchild!=NULL) top+; Sttop=p-lchild; printf(“n“); / 非递归中序遍历二叉树 void noRecursiveInorder(Node *T) Node *StTREEMAX,*p; int top=-1; if(T!=NULL) p=T; while(top-1|p!=NULL) while(p!=NULL) top+; Sttop=p; p=p-lchild; if(top-1) p=Sttop; top-; printf(“%c“,p-data); p=p-rchild; printf(“n“); / 非递归后序遍历二叉树 void n
5、oRecursivePostorder(Node *T) Node *StTREEMAX,*p; int flag,top=-1; if(T!=NULL) do while(T!=NULL) top+; Sttop=T; T=T-lchild; p=NULL; flag=1; while(top!=-1 if(T-rchild=p) printf(“%c“,T-data); top-; p=T; else T=T-rchild; flag=0; while(top!=-1); printf(“n“); / 层次遍历二叉树，用 queue 数组充当顺序队列 void LevelOrder(Nod
6、e *T) Node *queueTREEMAX, *p; int pre=-1, rear=-1; / 树根结点先进队 queue+pre=T; / 当队列不为空时，出队一个结点的同时将其左右孩子进队 while(pre-rear+TREEMAX)%TREEMAX!=0) p=queue+rear; / 出队一个结点并输出 printf(“%3c“, p-data); if(p-lchild!=NULL) / 左孩子存在则进队 queue+pre=p-lchild; if(p-rchild!=NULL) / 右孩子存在则进队 queue+pre=p-rchild; void list() p
7、rintf(“n“); printf(“ntt 二叉链表 “); printf(“ntt*“); printf(“ntt* 1.建立二叉树 *“); printf(“ntt* 2.递归前序遍历 *“); printf(“ntt* 3.递归中序遍历 *“); printf(“ntt* 4.递归后序遍历 *“); printf(“ntt* 5.非递归前序遍历 *“); printf(“ntt* 6.非递归中序遍历 *“); printf(“ntt* 7.非递归后序遍历 *“); printf(“ntt* 8.层次遍历 *“); printf(“ntt* 9.清屏 *“); printf(“ntt*
8、 0.退出程序 *“); printf(“ntt*“); printf(“ntt 请输入菜单项： “); void main() Node *T=NULL; char a,b; b=m; while(b=m|b=M) list(); scanf(“%c“, fflush(stdin); switch(a) case1: printf(“ntt 请按先序序列输入二叉树的结点（输入 #表示结点为空）：n“); printf(“ntt 请输入根结点： “); T=CreateBT(); printf(“ntt 二叉树成功建立 -n“); break; case2: printf(“ntt 该二叉树递
9、归前序遍历为： “); Preorder(T); break; case3: printf(“ntt 该二叉树递归中序遍历为： “); Inorder(T); break; case4: printf(“ntt 该二叉树递归后序遍历为： “); Postorder(T); break; case5: printf(“ntt 该二叉树非递归前序遍历为： “); noRecursivePreorder(T); break; case6: printf(“ntt 该二叉树非递归中序遍历为： “); noRecursiveInorder(T); break; case7: printf(“ntt 该二
10、叉树非递归后序遍历为： “); noRecursivePostorder(T); break; case8: printf(“ntt 该二叉树的层次遍历序列为： “); LevelOrder(T); break; case9: system(“cls“); break; case0: b=n; break; default: printf(“ntt*对不起，输入有误！ *“); /* 多项式运算【链式结构】 */ #include “stdio.h“ #include “stdlib.h“ typedef struct _node float coe; int index; struct _n
11、ode *next; Node, *NodePtr; / 整理多项式链表，将链表中的结点根据各项指数进行升序排列 void sortPoly(NodePtr list) NodePtr p=list-next, q=list, r, ptr; / 让 p 指向链表的第二个数据结点， / p 为空则说明链表为空，不用整 理了。 if(p) p=p-next; else return; / 先从链表的第一个数据结点后断开链表 ptr=q-next; ptr-next=NULL; / 再将链表的第二个直至最后一个数据结点依次插入链表 while(p) q=list; ptr=q-next; whil
12、e(ptr-index index) q=ptr; ptr=ptr-next; if(ptr=NULL) break; if(ptr=NULL) q-next=p; ptr=p; p=p-next; ptr-next=NULL; else if(ptr-index = p-index) ptr-coe += p-coe; r=p-next; free(p); p=r; else if(ptr-index p-index) r=p-next; p-next=ptr; q-next=p; p=r; /* 创建一个多项式链表，返回创建链表的头指针 */ NodePtr createPoly() in
13、t i=1, index; float coe; NodePtr resultPtr, q; / 开辟头结点空间 resultPtr = (NodePtr)malloc(sizeof(Node); resultPtr-next=NULL; printf(“请输入多项式第 %d 项的系数和指数 (输入 0 0 时结束 )： “, i+); scanf(“%f%d“, while(1) if(index else if(index=0 else / 开辟新结点空间 q=(NodePtr)malloc(sizeof(Node); q-coe=coe; q-index=index; q-next=NU
14、LL; / 将新结点插入多项式链表 q-next=resultPtr-next; resultPtr-next=q; / 输入下一项 printf(“请输入多项式第 %d 项的系数和指数 (输入 0 0 时结束 )： “, i+); scanf(“%f%d“, / 将输入的多项式链表整理后返回 sortPoly(resultPtr); return resultPtr; / 判断多项式链表是否已输入或是否为空 int isEmpty(NodePtr list1, NodePtr list2) if(list1=NULL) return 1; else if(list2=NULL) return
15、 2; else if(list1-next=NULL) return -1; else if(list2-next=NULL) return -2; else return 0; / 两个多项式相加 NodePtr addPoly(NodePtr list1, NodePtr list2) NodePtr resultPtr, p=list1-next, q=list2-next, r; if(isEmpty(list1, list2)=1) printf(“多项式链表 L1 不存在，请先选择菜单 1 输入多项式 L1！ n“); return NULL; else if(isEmpty(l
16、ist1, list2)=2) printf(“多项式链表 L2 不存在，请先选择菜单 2 输入多项式 L2！ n“); return NULL; / 创建结果多项式的头结点 resultPtr=(NodePtr)malloc(sizeof(Node); resultPtr-next=NULL; while(p!=NULL r-coe=q-coe; r-index=q-index; r-next=NULL; / 将新结点插入结果链表 r-next=resultPtr-next; resultPtr-next=r; q=q-next; else if(p-index index) r=(NodePtr)malloc(sizeof(Node); r-coe=p-coe; r-index=p-index; r-next=NULL;
