數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)-大數(shù)相乘等

1、精品文檔?數(shù)據(jù)結(jié)構(gòu)?課程設(shè)計(jì)報(bào)告班 級(jí) 學(xué) 號(hào) 姓 名 指導(dǎo)教師 課題一、大數(shù)相乘一、問(wèn)題描述要求：輸入兩個(gè)較大的整數(shù)，進(jìn)行乘法運(yùn)算，能夠通過(guò)程序計(jì)算出其正確的結(jié)果，并輸出結(jié)果，使整數(shù)相乘不受計(jì)算機(jī)內(nèi)存空間的限制。二、設(shè)計(jì)思路及步驟1、首先，要輸入兩個(gè)大數(shù)，所以在void multil()大數(shù)相乘操作函數(shù)中，定義兩個(gè)字符型數(shù)組AN和BN，其中，N為數(shù)組的最大長(zhǎng)度，以字符串的形式來(lái)記錄這兩個(gè)較大的整數(shù)，定義字符型指針res記錄這兩個(gè)整數(shù)相乘結(jié)果的返回地址，用于輸出結(jié)果。2、在大數(shù)乘法計(jì)算過(guò)程中，首先，將字符串各位的字符先轉(zhuǎn)化為所對(duì)應(yīng)的數(shù)字，然后再進(jìn)行一系列的計(jì)算，由于整數(shù)乘法計(jì)算是從低位到高位依

2、次計(jì)算，所以為符合這一規(guī)律，先對(duì)兩個(gè)大數(shù)字符串先進(jìn)行逆序操作void swap(char* str, int p, int q)逆序操作函數(shù)，最后再將所得的結(jié)果進(jìn)行逆序操作，并輸出結(jié)果。3、在char* LargeNum_ multi (char* A, char* B)大數(shù)相乘函數(shù)中，分別定義整型變量m和 n分別記錄數(shù)組AN和數(shù)組BN的長(zhǎng)度，定義字符型指針變量result記錄兩大數(shù)相乘后的地址用于返回地址，result的最大長(zhǎng)度為m+n，定義整型變量multiFlag和addFlag分別表示乘法進(jìn)位和加法進(jìn)位，初始化均為0，在之后的運(yùn)算過(guò)程中記錄乘法進(jìn)位和加法進(jìn)位。 三、函數(shù)清單 void

3、swap(char* str, int p, int q); /逆序操作函數(shù) void menu(); /菜單函數(shù) void multil(); /大數(shù)相乘操作函數(shù) char* LargeNum_ multi (char* A, char* B); /大數(shù)相乘函數(shù)四、源程序代碼#include <stdio.h> #include <stdlib.h>#include <string.h> #define N 100 void swap(char* str, int p, int q); /逆序 void menu(); /菜單void multil();

4、/大數(shù)相乘操作char* LargeNum_multi(char* A, char* B); /大數(shù)相乘 void swap(char* str, int p, int q) /逆序 char temp; while(p < q) temp = strp; strp = strq; strq = temp; p +; q -; char* LargeNum_multi(char* A, char* B) /大數(shù)相乘 if(A0>='1'&&A0<='9')&&(B0>='1'&&am

5、p;B0<='9') /正 &&正 int m = strlen(A); int n = strlen(B); int i; char *result; int multiFlag; / 乘積進(jìn)位 int addFlag; / 加法進(jìn)位 result=(char*)malloc(sizeof(char)*(m+n+1); for(i=0;i<m+n;i+) *(result+i)='0' resultm+n = '0' swap(A, 0, m-1); swap(B, 0, n-1); for(i=0; i <=

6、 n-1; i+) / B的每一位 multiFlag = 0; addFlag = 0; for(int j=0; j <= m-1; j+) / A的每一位 int temp1 = (Aj - '0') * (Bi - '0') + multiFlag; multiFlag = temp1 / 10; temp1 = temp1 % 10; int temp2 = (resulti+j - '0') + temp1 + addFlag; addFlag = temp2 / 10; resulti+j = temp2 % 10 + 

7、9;0' resulti + m += multiFlag + addFlag; /最高位 swap(result, 0, m+n-1); / 逆序 return result; else if(A0='-'&&B0='-') /負(fù) && 負(fù) LargeNum_multi(A+1),(B+1); else if(A0='-'&&(B0>='1'&&B0<='9') /負(fù) && 正 printf("-&quo

8、t;); LargeNum_multi(A+1),B); else if(B0='-'&&(A0>='1'&&A0<='9') / 正 && 負(fù) printf("-"); LargeNum_multi(A,(B+1); else if(B0='0'&&(A0>='1'&&A0<='9') /正 && 0 printf("0"); menu()

9、; else if(A0='0'&&(B0>='1'&&A0<='9') /0 && 正 printf("0"); menu(); else if(B0='0'&&A0='-') /負(fù) && 0 printf("0"); menu(); else if(B0='-'&&A0='0') /0 && 負(fù) printf(&quo

10、t;0"); menu(); else if(B0='0'&&A0='0') / 0 && 0 printf("0"); menu(); void multil() /大數(shù)相乘操作 char AN; char BN; printf("t輸入第一個(gè)數(shù)字:a="); scanf("%s",A); printf("t輸入第二個(gè)數(shù)字:b="); scanf("%s",B); printf("t輸出結(jié)果:a*b="

11、;); char *res = LargeNum_multi(A, B); if(res0 != '0') printf("%c", res0); printf("%s", res+1); menu(); void menu() /菜單 printf("nnt+-大數(shù)相乘-+n"); printf("t+ 1、進(jìn)行大數(shù)相乘計(jì)算 +n"); printf("t+ 2、退出程序 +n"); printf("t+ (請(qǐng)正確輸入數(shù)據(jù)) +n"); int item;

12、printf("nt請(qǐng)輸入菜單項(xiàng)選擇項(xiàng)："); scanf("%d",&item); switch(item) case 1:printf("nt+進(jìn)行大數(shù)相乘計(jì)算:n");multil();break;case 2:printf("nt+退出程序成功n");exit(0);break;default:printf("nt(+請(qǐng)?jiān)?和2中進(jìn)行選擇+)");menu();break; int main() menu(); return 0; 五、運(yùn)行截圖1、 正&&正2、

13、負(fù)&&正3、正&&負(fù)4、負(fù)&&負(fù)5、0&&06、0&&正7、正&&08、0&&負(fù)9、負(fù)&&0六、缺乏之處與解決方案缺乏之處1：本程序只能解決整型范圍內(nèi)的大數(shù)相乘問(wèn)題，而不能解決浮點(diǎn)型范圍內(nèi)的大數(shù)相乘。解決方案1：把浮點(diǎn)型大數(shù)分為整數(shù)局部和小數(shù)局部，分別對(duì)其進(jìn)行大數(shù)相乘函數(shù)的調(diào)用并輸出結(jié)果，這僅是一種思路，可上機(jī)進(jìn)行調(diào)試和運(yùn)行。 課題二、簡(jiǎn)單m 元多項(xiàng)式加法一、問(wèn)題描述要求：輸入兩個(gè)簡(jiǎn)單的m 元多項(xiàng)式，進(jìn)行加法運(yùn)算，并輸出結(jié)果。二、設(shè)計(jì)思路及步驟1、定義簡(jiǎn)單m元多項(xiàng)式的

14、結(jié)構(gòu)，其中包括：系數(shù)cofe，変元 var，指數(shù)exp；2、定義link_Polynode creat()創(chuàng)立簡(jiǎn)單m元多項(xiàng)式函數(shù)，即定義一個(gè)帶頭結(jié)點(diǎn)的單鏈表，通過(guò)link_Polynode creat()創(chuàng)立簡(jiǎn)單m元多項(xiàng)式函數(shù)分別生成兩個(gè)簡(jiǎn)單的m元多項(xiàng)式，并打印。3、定義void print(link_Polynode h) 打印多項(xiàng)式函數(shù)，標(biāo)準(zhǔn)化打印多項(xiàng)式。4、定義link_Polynode merge(link_Polynode h1,link_Polynode h2) 單鏈表連接函數(shù)，將兩個(gè)簡(jiǎn)單m元多項(xiàng)式的單鏈表合并成一個(gè)單鏈表，并進(jìn)行打印操作。5、定義link_Polynode Uni

15、tePoly(link_Polynode h)合并同類項(xiàng)函數(shù)，將連接后的單鏈表進(jìn)行合并同類項(xiàng)操作，即即單鏈表中変元var和指數(shù)exp完全相同的項(xiàng)，對(duì)其系數(shù)進(jìn)行相加或相減的操作，最后只保存一項(xiàng)変元var和指數(shù)exp和原來(lái)相同的項(xiàng)，最后，進(jìn)行打印操作，顯示進(jìn)行m 元多項(xiàng)式加法后的結(jié)果。三、m元多項(xiàng)式數(shù)據(jù)定義typedef struct node int cofe; /系數(shù) char var; /變?cè)?int exp; /指數(shù)struct node *next; node,*link_Polynode; 函數(shù)清單link_Polynode creat();/創(chuàng)立簡(jiǎn)單m元多項(xiàng)式link_Polynod

16、e merge(link_Polynode h1,link_Polynode h2);/單鏈表連接void print(link_Polynode h);/打印多項(xiàng)式 link_Polynode UnitePoly(link_Polynode h);/合并同類項(xiàng)void menu();/菜單 四、源程序代碼#include "stdio.h"#include "stdlib.h"typedef struct node int cofe; /系數(shù) char var; /變?cè)?int exp; /指數(shù)struct node *next; node,*link

17、_Polynode;link_Polynode creat(); /創(chuàng)立多項(xiàng)式 link_Polynode merge(link_Polynode h1,link_Polynode h2);/合并單鏈表void print(link_Polynode h);/打印多項(xiàng)式 link_Polynode UnitePoly(link_Polynode h);/合并同類項(xiàng)void menu();/菜單 link_Polynode creat()link_Polynode h,p,q;int c,e;char v;h=(link_Polynode)malloc(sizeof(node);p=h; pri

18、ntf("t 輸入系數(shù):"); scanf("%d",&c); /*輸入系數(shù)*/ printf("t 輸入變?cè)?"); getchar(); scanf("%c",&v); /*輸入變?cè)?/ printf("t 輸入指數(shù):"); scanf("%d",&e); /*輸入指數(shù)*/ if(c!=0) while(c!=0&&v!='0') q=(link_Polynode)malloc(sizeof(node); q->

19、;cofe=c; q->var=v; q->exp=e; p->next=q; p=q; printf("t 輸入系數(shù):"); scanf("%d",&c); /*輸入系數(shù)*/ if(c=0) break; printf("t 輸入變?cè)?"); getchar(); scanf("%c",&v); /*輸入變?cè)?/ printf("t 輸入指數(shù):"); scanf("%d",&e); /*輸入指數(shù)*/ p->next=NULL;

20、 else p->next=NULL;return h;void print(link_Polynode h)link_Polynode p;p=h->next; if(p=NULL)printf("0");while(p) if(p->cofe>0&&p!=h->next) if(p->exp>0) printf("+%d%c%d",p->cofe,p->var,p->exp); else if(p->exp<0) printf("+%d%c(%d)&qu

21、ot;,p->cofe,p->var,p->exp); else printf("+%d",p->cofe); else if(p->cofe<0&&p!=h->next) if(p->exp>0) printf("%d%c%d",p->cofe,p->var,p->exp); else if(p->exp<0) printf("%d%c(%d)",p->cofe,p->var,p->exp); else printf

22、("%d",p->cofe); else if(p->exp>0) printf("%d%c%d",p->cofe,p->var,p->exp); else if(p->exp<0) printf("%d%c(%d)",p->cofe,p->var,p->exp); else printf("%d",p->cofe); p=p->next; link_Polynode merge(link_Polynode h1,link_Polynod

23、e h2) /合并單鏈表 link_Polynode p1,p2,q1,q2,f; p1=h1->next; p2=h2->next; if(p1=NULL) return h2; else if(p2=NULL) return h1; else for(p1=h1->next;p1;p1=p1->next) q1=p1->next; if(q1=NULL) f=p1; f->next=p2; return h1; link_Polynode UnitePoly(link_Polynode h)/合并同類項(xiàng) link_Polynode p1,p2,q1,q2

24、,temp; q1=h; p1=q1->next; while(p1!=NULL) p2=p1->next; q2=p1; while(p2!=NULL) if(p1->exp=p2->exp)&&(p1->var=p2->var) p1->cofe=p1->cofe+p2->cofe; if(p1->cofe=0) temp=p2; q2->next=p2->next; free(temp); temp=p1; q1->next=p1->next; p1=q1; free(temp); bre

25、ak; else temp=p2; q2->next=p2->next; p2=p2->next; free(temp); else q2=p2; p2=p2->next; q1=p1; p1=p1->next; return h;void polynomial()link_Polynode t1,t2,t3,t4;printf("t請(qǐng)正確輸入第一個(gè)多項(xiàng)式:nt (系數(shù)cofe為 0 結(jié)束)：n");t1=creat(); printf("t請(qǐng)正確輸入第二個(gè)多項(xiàng)式:nt (系數(shù)cofe為 0 結(jié)束)：n");t2=creat

26、();printf("t顯示第一個(gè)多項(xiàng)式:m1=");print(t1);printf("n");printf("t顯示第二個(gè)多項(xiàng)式:m2="); print(t2);printf("n");printf("t顯示兩個(gè)多項(xiàng)式合并后的多項(xiàng)式:m1+m2=");t3=merge(t1,t2);print(t3);printf("n");printf("t合并同類項(xiàng)輸出最后結(jié)果:M="); t4=UnitePoly(t3);print(t4);printf(&q

27、uot;n");menu();void menu()printf("nt+-簡(jiǎn)單多元多項(xiàng)式加法-+n"); printf("t+ 1、進(jìn)行多項(xiàng)式加法計(jì)算 +n"); printf("t+ 2、退出程序 +n"); printf("t+ (正確輸入數(shù)據(jù)喲，否那么會(huì)出錯(cuò)喲)+n");int item;printf("t輸入菜單項(xiàng)選擇項(xiàng)："); scanf("%d",&item);switch(item)case 1:polynomial();break;case

28、 2:printf("t 退出程序n");exit(0);break;default:printf("nt *(請(qǐng)?jiān)?或2中選擇)*");printf("n");menu();break; int main()menu();五、運(yùn)行截圖1、多項(xiàng)式&&多項(xiàng)式2、0&&03、0&&多項(xiàng)式4、 多項(xiàng)式&&0六、缺乏之處及解決方案缺乏之處1：本程序只能進(jìn)行兩個(gè)簡(jiǎn)單多元多項(xiàng)式的加法運(yùn)算，而不能進(jìn)行減法運(yùn)算。解決方案1：可對(duì)第二個(gè)多項(xiàng)式的所有系數(shù)進(jìn)行取反操作，然后在調(diào)用多項(xiàng)式加法運(yùn)算

29、函數(shù)，并輸出結(jié)果。缺乏之處2：本程序可操作數(shù)的范圍較小，僅為整型。解決方案2：可對(duì)程序中的系數(shù)和指數(shù)定義為浮點(diǎn)型，進(jìn)一步擴(kuò)大它們的范圍。缺乏之處3：本程序不能進(jìn)行兩個(gè)多項(xiàng)式的乘法運(yùn)算。解決方案3:暫無(wú)課題三、二叉樹一般操作及線索化一、問(wèn)題描述要求：實(shí)現(xiàn)二叉樹的一般操作及中序線索化。二、設(shè)計(jì)思路及步驟1、定義所需的數(shù)據(jù)，如：二叉樹數(shù)據(jù)定義，棧的定義，隊(duì)列的定義，等等。2、要進(jìn)行二叉樹的一般操作，首先，要?jiǎng)?chuàng)立一個(gè)二叉樹，所以定義二叉樹創(chuàng)立函數(shù)，包括：先序遍歷二叉樹的創(chuàng)立函數(shù)Btree CreateBtree1()和 層次遍歷二叉樹創(chuàng)立函數(shù)Btree create_level_Btree2()。3、

30、二叉樹創(chuàng)立后就進(jìn)行其一般的遍歷操作，于是就定義其各類遍歷函數(shù)：先序遞歸遍歷，先序非遞歸遍歷，中序遞歸遍歷，中序非遞歸遍歷，后序遞歸遍歷，后序非遞歸遍歷，層次遍歷；其中，一些遍歷函數(shù)會(huì)用到?；蜿?duì)列的操作。4、在進(jìn)行遍歷后，可進(jìn)行其他的一般操作，如：節(jié)點(diǎn)數(shù)計(jì)算，深度計(jì)算，/葉子節(jié)點(diǎn)數(shù)計(jì)算，等等。5、最后，可對(duì)二叉樹進(jìn)行中序線索化操作，并對(duì)線索化后的二叉樹進(jìn)行線索化遍歷。三、二叉樹數(shù)據(jù)定義typedef struct Bnodechar data;int ltag,rtag; struct Bnode *lchild,*rchild;Bnode,*Btree; /定義二叉樹數(shù)據(jù)棧定義typedef

31、struct nodeBtree data100; /指針數(shù)組int top;seqstack,*pseqstack; /定義棧隊(duì)列定義typedef struct snodeBtree data100;int front ,rear;seqQuese,*pseqQuese; /定義隊(duì)列函數(shù)清單int count_tree(Btree t); /節(jié)點(diǎn)數(shù)計(jì)算 Btree CreateBtree1(); /先序遍歷二叉樹創(chuàng)立Btree create_level_Btree2(); /層次遍歷二叉樹創(chuàng)立int Depth(Btree t); /深度計(jì)算void inOrder(Btree t); /

32、中序線索遍歷void InOrder1(Btree t); /中序遞歸序列void InOrder2(Btree t); /中序非遞歸序列Btree InOrderThread(Btree t); /中序線索化二叉樹void inQuese(pseqQuese Q, Btree x); /數(shù)據(jù)入隊(duì)列void inThread(Btree p); /線索化 int leaf(Btree t); /葉子節(jié)點(diǎn)數(shù)void LevelOrder(Btree t); /層次遍歷Btree outQuese(pseqQuese Q); /數(shù)據(jù)出隊(duì)列Btree pop(pseqstack s); /數(shù)據(jù)出棧

33、void PostOrder1(Btree t); /后序遞歸序列void PostOrder2(Btree t); /后序非遞歸序列void PreOrder1(Btree t); /先序遞歸序列void PreOrder2(Btree t); /先序非遞歸序列void push(pseqstack s,Btree x); /數(shù)據(jù)入棧 void menu(); /菜單 四、源程序代碼#include<stdio.h>#include<stdlib.h>typedef struct Bnodechar data;int ltag,rtag; struct Bnode *

34、lchild,*rchild;Bnode,*Btree; /定義二叉樹數(shù)據(jù)typedef struct nodeBtree data100; /指針數(shù)組int top;seqstack,*pseqstack; /定義棧typedef struct snodeBtree data100;int front ,rear;seqQuese,*pseqQuese; /定義隊(duì)列Btree pre; /全局變量 / 函數(shù)清單 int count_tree(Btree t); /節(jié)點(diǎn)數(shù)計(jì)算 Btree CreateBtree1(); /先序遍歷二叉樹創(chuàng)立Btree create_level_Btree2()

35、; /層次遍歷二叉樹創(chuàng)立int Depth(Btree t); /深度計(jì)算void inOrder(Btree t); /中序線索遍歷void InOrder1(Btree t); /中序遞歸序列void InOrder2(Btree t); /中序非遞歸序列Btree InOrderThread(Btree t); /中序線索化二叉樹void inQuese(pseqQuese Q, Btree x); /數(shù)據(jù)入隊(duì)列void inThread(Btree p); /線索化 int leaf(Btree t); /葉子節(jié)點(diǎn)數(shù)void LevelOrder(Btree t); /層次遍歷Btre

36、e outQuese(pseqQuese Q); /數(shù)據(jù)出隊(duì)列Btree pop(pseqstack s); /數(shù)據(jù)出棧 void PostOrder1(Btree t); /后序遞歸序列void PostOrder2(Btree t); /后序非遞歸序列void PreOrder1(Btree t); /先序遞歸序列void PreOrder2(Btree t); /先序非遞歸序列void push(pseqstack s,Btree x); /數(shù)據(jù)入棧 void menu(); /菜單 void submenu(); /子菜單 void push(pseqstack s,Btree x)

37、/數(shù)據(jù)入棧 s->top+;s->datas->top=x;Btree pop(pseqstack s) /數(shù)據(jù)出棧 Btree t;t=s->datas->top;s->top-;return t;void inQuese(pseqQuese Q, Btree x) /數(shù)據(jù)入隊(duì)列Q->rear=(Q->rear+1)%100;Q->dataQ->rear=x; Btree outQuese(pseqQuese Q) /數(shù)據(jù)出隊(duì)列Btree q;Q->front=(Q->front+1)%100;q=Q->dataQ

38、->front;return q;Btree create_level_Btree2() /層次遍歷二叉樹創(chuàng)立char ch;Btree root,p,s;pseqQuese Q;Q=(pseqQuese)malloc(sizeof(seqQuese);Q->front=Q->rear=0; /初始化ch=getchar(); if(ch='#') root=NULL; root=(Btree)malloc(sizeof(Bnode); /生成根節(jié)點(diǎn) root->data=ch; root->ltag=0;root->rtag=0; Q-&g

39、t;dataQ->rear+=root; while(Q&&Q->front<Q->rear) p=Q->dataQ->front+; ch=getchar(); if(ch!='#') s=(Btree)malloc(sizeof(Bnode); s->data=ch; s->ltag=0; s->rtag=0; p->lchild=s; Q->dataQ->rear+=s; else p->lchild=NULL; ch=getchar(); if(ch!='#')

40、 s=(Btree)malloc(sizeof(Bnode); s->data=ch; s->ltag=0; s->rtag=0; p->rchild=s; Q->dataQ->rear+=s; else p->rchild=NULL; return root; Btree CreateBtree1() /先序遍歷二叉樹創(chuàng)立Btree t;char ch;ch=getchar();if(ch='#')t=NULL;elset=(Btree)malloc(sizeof(Bnode);t->data=ch;t->ltag=0;t

41、->rtag=0;t->lchild=CreateBtree1();t->rchild=CreateBtree1();return t; void PreOrder1(Btree t) /先序遞歸序列if(t)printf("%c",t->data);PreOrder1(t->lchild);PreOrder1(t->rchild);void PreOrder2(Btree t) /先序非遞歸序列Btree p=t;Btree q;seqstack s;s.top=-1;while(p|s.top!=-1)if(p)printf(&quo

42、t;%c",p->data);push(&s,p);p=p->lchild;elseq=pop(&s);p=q->rchild;void InOrder1(Btree t) /中序遞歸序列if(t)InOrder1(t->lchild);printf("%c",t->data);InOrder1(t->rchild);void InOrder2(Btree t) /中序非遞歸序列Btree p=t;Btree q;seqstack s;s.top=-1;while(p|s.top!=-1)if(p)push(&a

43、mp;s,p);p=p->lchild;elseq=pop(&s);printf("%c",q->data);p=q->rchild;void PostOrder1(Btree t) /后序遞歸序列if(t)PostOrder1(t->lchild);PostOrder1(t->rchild);printf("%c",t->data);void PostOrder2(Btree t) /后序非遞歸序列seqstack s1;seqstack s2;Btree p=t;Btree q1,q2;s1.top=-1;

44、s2.top=-1;while(p|s2.top!=-1)if(p)push(&s1,p);push(&s2,p);p=p->rchild;elseq2=pop(&s2);p=q2->lchild;while(s1.top!=-1)q1=pop(&s1);printf("%c",q1->data);void LevelOrder(Btree t) /層次遍歷 Btree p=t; Btree q; seqQuese Q;Q.front=Q.rear=0; /初始化 inQuese(&Q,p); q=outQuese(

45、&Q); printf("%c",q->data);if(q->lchild!=NULL) inQuese(&Q,q->lchild); if(q->rchild!=NULL) inQuese(&Q,q->rchild); while(Q.front!=Q.rear) q=outQuese(&Q); printf("%c",q->data); if(q->lchild!=NULL) inQuese(&Q,q->lchild); if(q->rchild!=NUL

46、L) inQuese(&Q,q->rchild); int leaf(Btree t) /葉子節(jié)點(diǎn)數(shù)if(!t)return 0;else if(!t->lchild&&!t->rchild)return 1;elsereturn (leaf(t->lchild)+leaf(t->rchild);int Depth(Btree t) /深度計(jì)算int h1,h2;if(t=NULL)return 0;elseh1=Depth(t->lchild);h2=Depth(t->rchild);if(h1>h2)return h1

47、+1;return h2+1;int count_tree(Btree t) /節(jié)點(diǎn)數(shù)計(jì)算 int lcount,rcount;if(t=NULL)return 0;lcount=count_tree(t->lchild);rcount=count_tree(t->rchild);return lcount+rcount+1; /=中序線索化= void inThread(Btree p) /線索化 if(p)inThread(p->lchild); /左子樹線索化 if(p->lchild=NULL) /前驅(qū)線索 p->lchild=pre; /建立當(dāng)前節(jié)點(diǎn)的前

48、驅(qū)線索 p->ltag=1;elsep->ltag=0;if(pre->rchild=NULL) /后繼線索pre->rchild=p;pre->rtag=1; elsepre->rtag=0;pre=p;inThread(p->rchild); /右子樹線索化 Btree InOrderThread(Btree t) /中序線索化二叉樹 Btree root;root=(Btree)malloc(sizeof(Bnode);/創(chuàng)立根節(jié)點(diǎn)root->ltag=0;root->rtag=1;root->rchild=t;if(t=NUL

49、L)root->lchild-root;elseroot->lchild=t; pre=root; /pre是 p 的前驅(qū)節(jié)點(diǎn) inThread(t); / 中序遍歷線索化二叉樹 pre->rchild=root;pre->rtag=1;root->rchild=pre; /根節(jié)點(diǎn)右線索化 return root; void inOrder(Btree t) /中序線索遍歷 Btree p=t->lchild; while(p!=t) while(p->ltag=0) p=p->lchild; printf("%c",p-&g

50、t;data); while(p->rtag=1&&p->rchild!=t) p=p->rchild; printf("%c",p->data); p=p->rchild; void Binary_Tree_pre()Btree t; printf("t 先序輸入二叉樹(#表示空節(jié)點(diǎn)):nt "); t=CreateBtree1(); /先序遍歷創(chuàng)立二叉樹 printf("t顯示二叉樹信息：n"); printf("t 先序遍歷(遞歸):");PreOrder1(t); printf("n");printf("t 先序遍歷(非遞歸):");PreOrder2(t);printf("n");printf("t 中序遍歷(遞歸):");InOrder1(t); printf("n");printf("t 中序遍歷(非遞歸):&q