二叉樹的建立課件

1、二叉樹的建立循 環(huán) 鏈 表文 件 操 作1二叉樹的建立2二叉樹的建立建立二叉樹的過程是一個“插入”過程，下面我們用一個例子來講解這一過程。我們想建立這樣一棵二叉樹，樹中的每一個結(jié)點有一個整數(shù)數(shù)據(jù)名為data，有兩個指針：左指針L，右指針R，分別指向這個結(jié)點的左子樹和右子樹，顯然可以用如下名為TREE的結(jié)構(gòu)來描述這種結(jié)點：struct TREEint data;struct TREE *L, *R;3對二叉樹最重要的是根，它起定位的作用，因此，首先建立的是根結(jié)點。也就是說，如果從鍵盤輸入數(shù)據(jù)來建立二叉樹，第一個數(shù)據(jù)就是這棵樹的根的數(shù)據(jù)，之后再輸入的數(shù)據(jù)，每一個都要與根中的數(shù)據(jù)作比較，以便確定該數(shù)

2、據(jù)所在結(jié)點的插入位置。假定我們這里依然用圖1的中序遍歷的方式。即如果待插入結(jié)點的數(shù)據(jù)比根結(jié)點的數(shù)據(jù)小，則將其插至左子樹，否則插入右子樹。定義一個遞歸函數(shù)void insert(struct TREE *proot, struct TREE *p)其中，指針p指向含有待插入數(shù)據(jù)的結(jié)點。proot為樹的根指針的地址。insert函數(shù)棵理解為將p結(jié)點插入到*proot所指向的樹中。4注意在上圖中proot是被調(diào)用函數(shù)的形參。從前面對它的定義看，proot是指針的指針，實際上是指向二叉樹根結(jié)點的指針的指針，或者說是指向二叉樹根結(jié)點的指針的地址。如下圖。因此，在主程序調(diào)用insert函數(shù)時，根結(jié)點pro

3、ot實參&root實參為 &root, p形參為 proot, p下面是建立二叉樹的參考程序。6#include / 預編譯命令#include / 內(nèi)存空間分配#define null 0/ 定義空指針常量#define LEN sizeof(struct TREE)/ 定義常量，表示結(jié)構(gòu)長度struct TREE/ 結(jié)構(gòu)聲明int data;/ 整型數(shù)struct TREE *L,*R;/ TREE結(jié)構(gòu)指針;7/ 被調(diào)用函數(shù)，形參為TREE結(jié)構(gòu)指針，輸出二叉樹內(nèi)容void print(struct TREE *root) / 函數(shù)體開始if (root = null)/ 根或子樹根結(jié)點為空

4、return;/ 返回print(root-L);/ 輸出左子樹內(nèi)容printf(%d,root-data);/ 輸出根結(jié)點內(nèi)容print(root-R);/ 輸出右子樹內(nèi)容/ 被調(diào)用函數(shù)結(jié)束void main()/ 主函數(shù)開始/ 函數(shù)體開始struct TREE *root, *p;/ TREE型結(jié)構(gòu)指針int temp;/ 臨時變量，用于用戶輸入數(shù)據(jù)root = null;/ 初始化二叉樹根結(jié)點為空p = null;/ 初始化待插入結(jié)點的指針為空printf(請輸入待插入結(jié)點的數(shù)據(jù)n);/ 提示信息printf(如果輸入-1表示插入過程結(jié)束n);/ 提示信息scanf(%d,&temp);

5、/ 輸入待插入結(jié)點數(shù)據(jù)9while(temp != -1)/ 當型循環(huán)，-1為結(jié)束標志/ 循環(huán)體開始/ 為待插入結(jié)點分配內(nèi)存單元p = (struct TREE *) malloc(LEN);p-data = temp;/ 將temp賦值給p結(jié)點的數(shù)據(jù)域p-L = p-R = null;/ 將p結(jié)點的左右指針域置為空insert( &root, p );/ 將p結(jié)點插入到根為root的樹中，/ &root表示二叉樹根結(jié)點的地址printf(請輸入待插入結(jié)點的數(shù)據(jù)n);/ 提示信息printf(如果輸入-1表示插入過程結(jié)束n);/ 提示信息scanf(%d,&temp);/ 輸入待插入結(jié)點數(shù)據(jù)/

6、 循環(huán)體結(jié)束if (root=null) / 如果根結(jié)點為空printf(這是一棵空樹。n);/ 輸出空樹信息else/ 根結(jié)點不為空print(root);/ 調(diào)用print函數(shù)，輸出二叉樹內(nèi)容/ 主函數(shù)結(jié)束10循 環(huán) 鏈 表11循環(huán)鏈表例：猴子選大王。n只猴子圍成一圈，順時針方向從1到n編號。之后從1號開始沿順時針方向讓猴子從1，2，m依次報數(shù)，凡報到m的猴子，都讓其出圈，取消候選資格。然后不停地按順時針方向逐一讓報出m者出圈，最后剩下一個就是猴王。12起始位置猴 王123456783615284猴子被淘汰的順序演示：n=8, m=313說明：如圖1所示有8只猴子圍成一圈，m=3。從1#猴

7、的位置開始，順時針1至3報數(shù)，第一個出圈的是3#；第二個出圈的是6#，第3個出圈的是1#；第4個出圈的是5#；第5個是2#，第6個是8#；第7個是4#。最后剩下一個是7#，它就是猴王。我們用循環(huán)鏈表來模擬這個選擇過程。144、建立循環(huán)鏈表的函數(shù)create(int nn)其中nn為形式參數(shù)。要從編號1到編號nn。思路是（1）先做第1個結(jié)點，讓其中的數(shù)據(jù)域p-num賦值為1，讓指針域賦值為null。之后讓鏈頭指針head指向第1個結(jié)點。利用指針q記住這個結(jié)點，以便讓指針p去生成下面的結(jié)點。（2）利用一個計數(shù)循環(huán)結(jié)構(gòu)，做出第2個結(jié)點到第nn個結(jié)點。并將相鄰結(jié)點一個接一個鏈接到一起。（3）最后一個結(jié)

8、點要和頭結(jié)點用下一語句鏈接到一起tail = q; tail-next = head;headtailq165、刪結(jié)點的函數(shù)select(int mm)mm為形式參數(shù)，從1至m報數(shù)，凡報到mm者刪除其所在的結(jié)點。設(shè)計兩個指針p和q。一開始讓q指向鏈表的尾部q=tail。讓p指向q的下一個結(jié)點。開始時讓p指向1#猴所在的結(jié)點。用一個累加器x，初始時x=0，從1#猴所在結(jié)點開始讓x=x+1=1，如果mm是1的話，1#猴所在的p結(jié)點就要被刪除。有三條語句printf(“被刪掉的猴子號為%d號n”,p-num);q-next = p-next;free(p);1head28tailqp演示17這個do

9、-while循環(huán)的退出條件是q=q-next。即當只剩下一個結(jié)點時才退出循環(huán)。當然猴王非其莫屬了。這時，讓頭指針head指向q，head是全局變量，在主程序最后輸出猴王時要用head-num。參考程序如下：7headq19#include / 預編譯命令#include / 內(nèi)存空間分配#define null 0/ 定義空指針常量/ 定義常量，表示結(jié)構(gòu)長度#define LEN sizeof(struct mon)struct mon/ 結(jié)構(gòu)聲明int num;/ 整型數(shù)，用于記錄猴子號struct mon *next;/ mon結(jié)構(gòu)指針;struct mon *head, *tail;/

10、mon結(jié)構(gòu)指針，全局變量20void create(int nn)/ 被調(diào)用函數(shù)/ 函數(shù)體開始 int i;/ 整型變量i，用于計數(shù)struct mon *p,*q;/ 聲明mon結(jié)構(gòu)指針p，q/ 為p分配內(nèi)存空間p=(struct mon *) malloc(LEN);p-num=1;/ 初始化p結(jié)點num域為1p-next=null;/ 初始化p結(jié)點next域為空head=p;/ 鏈表頭指針head賦值為pq=p;/ q賦值為p21for(i=2;inum=i;/ 初始化p結(jié)點num域為i，表示猴子號q-next=p;/ 將p結(jié)點加到鏈表尾部q=p;/ 讓q指向鏈表尾部結(jié)點p-next=n

11、ull;/ 鏈表尾部指向空/ 循環(huán)體結(jié)束tail = q;/ 鏈表尾tail-next=head;/ 鏈表尾部指向鏈表頭，/ 形成循環(huán)鏈表/ 函數(shù)體結(jié)束22/ 被調(diào)用函數(shù)select，mm表示結(jié)點刪除間隔void select(int mm)/ 函數(shù)體開始int x=0;/ 聲明整型值x，并初始化為0struct mon *p,*q;/ 聲明結(jié)構(gòu)指針p，qq=tail;/ q賦值為tail，指向循環(huán)鏈表尾部 do/ 直到型循環(huán)，用于循環(huán)刪除指定間隔的結(jié)點/ 循環(huán)體開始p=q-next;/ p賦值為q相鄰的下一個結(jié)點x=x+1;/ x加1if(x % mm=0)/ x是否整除mm，/ 表示是否跳

12、過指定間隔/ 輸出被刪掉的猴子號printf(被刪掉的猴子號為%d號n,p-num);q-next=p-next;/ 刪除此結(jié)點free(p);/ 釋放空間else q=p;/ q指向相鄰的下一個結(jié)點pwhile(q!=q-next);/ 剩余結(jié)點數(shù)不為1，則繼續(xù)循環(huán)head = q;/ head指向結(jié)點q，q為鏈表中剩余的一個結(jié)點/ 函數(shù)體結(jié)束23void main()/ 主函數(shù)開始/ 函數(shù)體開始int n,m;/ 聲明整型變量n,mhead = null;/ 初始化head為空printf(請輸入猴子數(shù)n);/ 提示信息scanf(%d,&n);/ 輸入待插入結(jié)點數(shù)據(jù)printf(請輸入間

13、隔mn);/ 提示信息scanf(%d,&m);/ 輸入間隔 create(n);/ 調(diào)用函數(shù)create建立循環(huán)鏈表select(m);/ 調(diào)用函數(shù)select，找出剩下的猴子printf(猴王是%d號n,head-num); / 輸出猴王/ 函數(shù)體結(jié)束24有關(guān)文件的概念和名詞文件是信息的集合，是信息存放在外存中的一種形式?？梢蚤L期保存。EOF文件的結(jié)束符。C語言中的文件視為信息流，文件的讀寫是按順序進行的?？梢砸宰址麨閱挝蛔x寫，也可以以“行”為單位讀寫。一行是以“n”為結(jié)束的一串字符。文件指針是指向含有文件信息結(jié)構(gòu)的指針。文件指針又稱內(nèi)部文件名。對文件進行操作，先要將文件打開。所謂“打開文

14、件”，就是在內(nèi)存中為文件建立一個緩沖區(qū)，文件指針就要指向緩沖區(qū)的首地址。26標準文件C語言中規(guī)定的標準文件有三個：1、標準輸入文件（鍵盤），文件指針為stdin;2、標準輸出文件（顯示屏幕），文件指針為stdout;3、標準出錯信息文件，文件指針為stderr。特點是這些文件在操作前或后，系統(tǒng)會自動將其打開或關(guān)閉，程序不需管。27標準文件的操作1、getchar()，從標準輸入文件中使用該函數(shù)可以得到一個字符。返回值是該字符的ASCII碼值。因此可見返回值是int型的。2、putchar()，將字符代碼送至屏幕上，顯示成字符。29#include void main()/ 主函數(shù)/ 主函數(shù)開始

15、int temp;/ 定義整型變量while(temp=getchar()!=EOF)/ 標準輸入未結(jié)束if (temp=a & temp=z)/ 小寫字母/ 將對應(yīng)的大寫字母 輸出到屏幕putchar(temp-a+A);elseputchar(temp);/ 輸出到屏幕/ 主函數(shù)結(jié)束例 文件1.c30說明：1、由于getchar()返回的是整數(shù)（ASCII碼值）,因此，temp定義為整數(shù)型。2、EOF被定義為-1，當getchar()函數(shù)返回-1時結(jié)束，這里EOF被定義為-1，在DOS系統(tǒng)中只有用+Z才能結(jié)束鍵盤輸入。從實驗中可以看出getchar()函數(shù)是將鍵盤輸入的字符的ASCII碼的

16、形式存至緩沖區(qū)，敲入字符之后，須回車才響應(yīng)輸出a / 敲入的小寫字符temp = 97 / 回車之后，輸入a的ASCII碼A / 回應(yīng)大寫字符A，temp = 10 / 輸出回車鍵的ASCII碼值313、在上述程序基礎(chǔ)上，將getchar改為getch，觀察程序運行情況。這時不再顯示敲入的小寫字母，屏幕上看到的都是大寫字母了。但顯示的ASCII碼值仍是小寫字母的碼值。退出方式用+4、將getch改為getche再試，觀察有何變化？5、字符串的讀寫函數(shù)gets()和puts()。32#include / 預編譯命令#define null 0/ 定義null為空void main()/ 主函數(shù)/

17、 主函數(shù)開始char s256;/ 定義字符數(shù)組sint no;/ 定義整型變量nono = 1;/ 初始化no為1while(gets(s)!=null)/ s須為指針/ 循環(huán)體開始printf(“%d:%sn”,no,s);/ 輸出no和sprintf(“%Xn”,s);/ s是指針no=no+1;/ no加1/ 循環(huán)體結(jié)束/ 主函數(shù)結(jié)束例 文件2.c33說明：gets(s)函數(shù)的形參為字符指針，指向一個由鍵盤輸入的字符串。正常時返回一個讀取到的字符串的首地址。出錯時返回NULL。輸入的字符串以n結(jié)束，該函數(shù)在內(nèi)存中將n以0存放，從而使s變?yōu)樽址？聪吕?4puts(s)是將s所指向的

18、字符串寫到屏幕上，寫時將n轉(zhuǎn)換為0。6、使用printf( )，scanf( ) 略#include / 預編譯命令#define null 0/ 定義空指針常量void main()/ 主函數(shù)/ 主函數(shù)開始char s256;/ 定義字符串while(gets(s)!=null)/ 循環(huán)輸入puts(s);/ 輸出s到屏幕/ 循環(huán)體結(jié)束35一般文件的操作1、打開和關(guān)閉文件函數(shù)1.1 打開文件函數(shù) fopen( ) 格式為fopen( “文件名”, 打開方式);“r”：讀方式 “w”：寫方式 “a”：追加方式“rb”：二進制讀方式“wb”：二進制寫方式“ab”：二進制追加方式“rw”：讀寫方式

19、36用“r”只能讀不能寫，用“w”只能寫不能讀。用“a”打開的文件可向已有文件內(nèi)容后邊增加新的內(nèi)容。使原內(nèi)容不被新內(nèi)容所覆蓋。在用文本文件輸入時，將回車換行符轉(zhuǎn)換為一個換行符；在輸出時，把換行符轉(zhuǎn)換成回車符和換行符（兩個字符），在用二進制文件時，不作上述轉(zhuǎn)換，內(nèi)存當中的數(shù)據(jù)形式與輸出到外部文件中的數(shù)據(jù)形式完全一樣。fopen函數(shù)有一個返回值，正常時返回一個文件指針，指向內(nèi)存為該文件開辟的緩沖區(qū)首地址。失敗時返回NULL。比如該文件并不存在，你要打開它，當然要返回NULL。為了寫或追加寫時，如果要打開的文件不存在，這時系統(tǒng)會自動幫你建立一個要打開的文件。37實際使用時要判斷fopen( )函數(shù)的返回值。常用語句為if (fp=fopen(“f1.c”, “rw”)=NULL)printf(“Cant open this file.n”);exit(1);其中的fp是已經(jīng)定義好的文件指針。1.2 關(guān)閉文件的函數(shù)為 fclose(文件指針);這個函數(shù)在正常情況下返回值為0，關(guān)閉有錯時返回非0值，可用ferror()函數(shù)來檢查。382、文件的讀和寫#include char s=“I am a student”;void main()char a100;