C语言版数据结构程序设计求大神帮助

Question

用C语言编制实现中序线索二叉树程序，并在此线索树中进行中序遍历

Answer 1

/* 二叉树应用 */ #include "stdio.h" #include "stdlib.h" typedef char ElemType; /* 结点数据的类型 */ typedef struct BiTNode{ ElemType data; struct BiTNode *lchild,*rchild; }BiTNode; /* 树结点类型 */ /*栈的定义及基本操作*/ #define MaxSize 100 typedef BiTNode* SElemType; /* 栈和队列的结点类型，用于存放树结点 */ typedef struct { SElemType elem[MaxSize]; int top; }SqStack; /* 栈 */ void InitStack(SqStack *pS) /* 初始化栈,开始时栈为空 */ { pS->top=0; /* top指向栈顶的上一个元素 */ } int Push(SqStack *pS,SElemType e) /* 进栈 */ { if (pS->top==MaxSize-1) /* 栈满 */ return 0; pS->elem[pS->top]=e; pS->top=pS->top+1; return 1; } int Pop(SqStack *pS,SElemType *pe) /* 出栈 */ { if (pS->top==0) /* 栈空 */ return 0; pS->top = pS->top - 1; *pe = pS->elem[pS->top]; return 1; } /*队列（循环队列）的定义及基本操作*/ typedef struct { SElemType elem[MaxSize]; int front,rear; }SqQueue; /* 队列 */ void InitQueue(SqQueue* pQ) /* 初始化队列,开始时队列为空 */ { pQ->front=pQ->rear=0; } int EnQueue(SqQueue* pQ,SElemType e) /* 进队 */ { if ((pQ->rear+1)%MaxSize == pQ->front) /* 队满 */ return 0; pQ->elem[pQ->rear] = e; pQ->rear = (pQ->rear+1)%MaxSize; return 1; } int DeQueue(SqQueue* pQ,SElemType* pe) /* 出队 */ { if (pQ->rear == pQ->front) /* 队空 */ return 0; *pe = pQ->elem[pQ->front]; pQ->front = (pQ->front+1)%MaxSize; return 1; } /* 先根遍历 */ void preorder(BiTNode *bt) { if(bt!=NULL) { printf("%c ",bt->data); preorder(bt->lchild); preorder(bt->rchild); } } /* 中根遍历 */ void inorder(BiTNode *bt) { if(bt!=NULL) { inorder(bt->lchild); printf("%c ",bt->data); inorder(bt->rchild); } } /* 后根遍历 */ void postorder(BiTNode *bt) { if(bt!=NULL) { postorder(bt->lchild); postorder(bt->rchild); printf("%c ",bt->data); } } /* 非递归算法的中根遍历（后进先出，用了栈的思想） */ void inorder_fdg(BiTNode *bt) { BiTNode *p; SqStack s; InitStack(&s); p=bt; do { while(p!=NULL) { Push(&s,p); p=p->lchild; } if(s.top!=0) { Pop(&s,&p); printf("%c ",p->data); p=p->rchild; } }while(s.top!=0||p!=NULL); } /* 用队列实现层次遍历 */ void lev_traverse(BiTNode* bt) { SqQueue q; BiTNode *p; p=bt; InitQueue(&q); EnQueue(&q,p); while(!(q.rear==q.front)) { /* 当队列不空 */ DeQueue(&q,&p); printf("%c ",p->data); if(p->lchild!=NULL) EnQueue(&q,p->lchild); if(p->rchild!=NULL) EnQueue(&q,p->rchild); } } /* 利用先根序列建立二叉树，空的子树也要输入，用空格表示,建立的树通过函数返回,避免使用指针的指针 */ BiTNode *crt_bt_pre() { char ch; BiTNode *bt; scanf("%c",&ch); if(ch==' ') bt=NULL; else { bt=(BiTNode *)malloc(sizeof(BiTNode)); bt->data=ch; bt->lchild=crt_bt_pre(); bt->rchild=crt_bt_pre(); } return(bt); } /* 利用先根序列建立二叉树，空的子树也要输入，用空格表示,建立的树通过参数返回,注意和上述方法比较，想想还有什么办法？ */ void crt_bt_pre_2(BiTNode **bt) { char ch; scanf("%c",&ch); if(ch==' ') (*bt)=NULL; else { (*bt)=(BiTNode *)malloc(sizeof(BiTNode)); (*bt)->data=ch; crt_bt_pre_2(&(*bt)->lchild); crt_bt_pre_2(&(*bt)->rchild); } } /* 求叶子数 */ int leaf(BiTNode *bt) { if (bt==NULL) return 0; else { if (bt->lchild==NULL&&bt->rchild==NULL) return 1; else return leaf(bt->lchild)+leaf(bt->rchild); } } /* 求树的高度 */ int high(BiTNode *bt) { if (bt==NULL) return 0; else { return max(high(bt->lchild),high(bt->rchild))+1; } } /* 二叉树的释放*/ void freetree(BiTNode *bt) { if(bt!=NULL) { freetree(bt->lchild); freetree(bt->rchild); free(bt); bt=NULL; } } main() { BiTNode *T,*temp[20]; /* 笨方法建立二叉树 */ /* temp[0]=(BiTNode*)malloc(sizeof(BiTNode)); temp[0]->data = '-'; temp[1]=(BiTNode*)malloc(sizeof(BiTNode)); temp[1]->data = '+'; temp[0]->lchild = temp[1]; temp[2]=(BiTNode*)malloc(sizeof(BiTNode)); temp[2]->data = '/'; temp[0]->rchild = temp[2]; temp[3]=(BiTNode*)malloc(sizeof(BiTNode)); temp[3]->data = 'a'; temp[3]->lchild=NULL; temp[3]->rchild=NULL; temp[1]->lchild = temp[3]; temp[4]=(BiTNode*)malloc(sizeof(BiTNode)); temp[4]->data = '*'; temp[1]->rchild = temp[4]; temp[5]=(BiTNode*)malloc(sizeof(BiTNode)); temp[5]->data = 'e'; temp[5]->lchild=NULL; temp[5]->rchild=NULL; temp[2]->lchild = temp[5]; temp[6]=(BiTNode*)malloc(sizeof(BiTNode)); temp[6]->data = 'f'; temp[6]->lchild=NULL; temp[6]->rchild=NULL; temp[2]->rchild = temp[6]; temp[7]=(BiTNode*)malloc(sizeof(BiTNode)); temp[7]->data = 'b'; temp[7]->lchild=NULL; temp[7]->rchild=NULL; temp[4]->lchild = temp[7]; temp[8]=(BiTNode*)malloc(sizeof(BiTNode)); temp[8]->data = '-'; temp[4]->rchild = temp[8]; temp[9]=(BiTNode*)malloc(sizeof(BiTNode)); temp[9]->data = 'c'; temp[9]->lchild=NULL; temp[9]->rchild=NULL; temp[8]->lchild = temp[9]; temp[10]=(BiTNode*)malloc(sizeof(BiTNode)); temp[10]->data = 'd'; temp[10]->lchild=NULL; temp[10]->rchild=NULL; temp[8]->rchild = temp[10]; T=temp[0]; */ /*输出树和各种遍历、叶子数、树的高度*/ /*printf("\ntree:\n"); printf(" -\n"); printf(" + /\n"); printf(" a * e f\n"); printf("0 0b - 0 00 0\n"); printf(" 0 0c d\n"); printf("\n\nPreOrder:\n"); preorder(T); printf("\nInOrder:\n"); inorder(T); printf("\nPostOrder:\n"); postorder(T); printf("\ninorder_fdg:\n"); inorder_fdg(T); printf("\nlev_traverse:\n"); lev_traverse(T); printf("\nleaf num:%d",leaf(T)); printf("\nTree high:%d",high(T)); freetree(T); */ /* 按先序列建树，用空格表示空子树*/ printf("\n\nplease input inorder:such as 'abc de g f '\n"); /*T = crt_bt_pre();*/ crt_bt_pre_2(&T); printf("\n\nPreOrder:\n"); preorder(T); printf("\nInOrder:\n"); inorder(T); printf("\nPostOrder:\n"); postorder(T); printf("\ninorder_fdg:\n"); inorder_fdg(T); printf("\nlev_traverse:\n"); lev_traverse(T); printf("\nleaf num:%d",leaf(T)); printf("\nTree high:%d",high(T)); freetree(T); getch(); }