天津理工大學數據結構實驗報告3

計算機科學與工程系PAGEPAGE6計算機科學與工程系實驗（三）實驗名稱二叉樹的遍歷軟件環(huán)境Windows98/2000,VC++6.0或turboC硬件環(huán)境PⅡ以上微型計算機實驗目的理解二叉樹的邏輯特點，掌握二叉鏈表存儲結構，掌握二茬樹遍歷算法的遞歸與非遞歸實現實驗內容（應包括實驗題目、實驗要求、實驗任務等）二叉樹的遍歷利用二叉鏈表作為存儲結構建立一棵二叉樹，每個結點中存放一種水果名(例如apple、orange、banana等，并要求從鍵盤輸入)，結點數不少于5個。要求分別以先序、中序和后序進行遍歷，輸出遍歷結果。并編寫一遞歸算法，交換該二叉樹中所有結點的左、右孩子。實驗過程與實驗結果（可包括實驗實施的步驟、算法描述、流程、結論等）實驗步驟及算法描述和流程：創(chuàng)建二叉鏈表的結點存儲結構及數據的輸入輸出函數因為每個結點所存儲的數據類型為字符串，卻無法使用字符串和String等數據類型，所以使用單鏈表作為結點所存儲的數據類型。數據的輸入函數indata()當輸入的字符不為‘0’時，以尾插法將數據插入單鏈表。數據的輸出函數直接輸出單鏈表。生成二叉鏈表利用先序遍歷生成二叉鏈表：用單鏈表s記錄輸入的數據若單鏈表s為空，則二叉鏈表結點為空，否則根節(jié)點=s，利用遞歸調用分別生成根節(jié)點的左子樹和右子樹返回二叉鏈表先序遍歷、中序遍歷、后序遍歷二叉鏈表先序遍歷：訪問根節(jié)點，左子樹，右子樹的順序中序遍歷：訪問左子樹，根節(jié)點，右子樹的順序后序遍歷：訪問左子樹，右子樹，根節(jié)點的順序利用遞歸調用分別用以上三種順序遍歷二叉鏈表。交換二叉鏈表的左右孩子當二叉鏈表的結點左孩子或者右孩子都不為空時，利用遞歸調用，分別交換左子樹很右孩子的左右孩子，最后將根節(jié)點的左右孩子指針交換。主函數調用生成二叉鏈表的函數，從鍵盤輸入二叉鏈表的各個結點分別調用先序遍歷、中序遍歷、后序遍歷二叉鏈表函數，輸出所有結點交換二叉鏈表的左右孩子重復5.2結論：輸入各個結點：apple、pear、orange、banana、peach、grape、watermelon先序遍歷輸入與輸入一致中序遍歷輸出：orange、pear、banana、apple、grape、peach、watermelon后序遍歷輸出：orange、banana、pear、grape、watermelon、peach、apple交換二叉樹的左右孩子后先序遍歷輸出：apple、peach、watermelon、grape、pear、banana、orange編程中出現的問題：輸入的二叉鏈表左右子樹必須對稱，如果不對稱，交換二叉樹的左右子樹后，程序出錯，不知道出錯在哪，沒有調試成功。附錄（可包括源程序清單或其它說明）#include<iostream>#include<stdio.h>#include<stdlib.h>#include<string>usingnamespacestd;typedefstructLNode{//二叉鏈表數據存儲結構 chardata; structLNode*next;}LNode,*LinkList;typedefstructBiTNode{//二叉鏈表節(jié)點存儲結構 LinkListdata; structBiTNode*lchild; structBiTNode*rchild;//左右孩子指針}BiTNode,*BiTree;voidoutdata(LinkListL){//輸出數據 LinkListp; p=L->next; while(p!=NULL){ cout<<p->data; p=p->next; } cout<<"";}LinkListindata(){//輸入數據 LinkListL,p,r; charx; r=L=(LinkList)malloc(sizeof(LNode)); L->next=NULL; cin>>x; while(x!='0'){ p=(LinkList)malloc(sizeof(LNode)); p->data=x; p->next=NULL; r->next=p; r=p; cin>>x; } returnL;}BiTreeCreateBiTree(BiTree&T){//先序遍歷生成二叉樹 LinkLists=indata(); if(s->next==NULL)T=NULL; else{ T=(BiTNode*)malloc(sizeof(BiTNode)); if(!T) exit(1); T->data=s; CreateBiTree(T->lchild);//建立左子樹 CreateBiTree(T->rchild);//建立右子樹 } returnT;}voidPreOrder(BiTreeroot){//先序遍二叉樹 if(root==NULL)return; outdata(root->data); PreOrder(root->lchild); PreOrder(root->rchild);}voidInOrder(BiTreeroot){//中序遍歷二叉樹 if(root==NULL)return; InOrder(root->lchild); outdata(root->data); InOrder(root->rchild);}voidPostOrder(BiTreeroot){//后序遍歷二叉樹 if(root==NULL)return; PostOrder(root->lchild); PostOrder(root->rchild); outdata(root->data);}voidexchange(BiTree&root){//交換二叉樹的左右孩子 BiTreetemp; if(root->lchild!=NULL||root->rchild!=NULL){ exchange(root->lchild); exchange(root->rchild); temp=root->lchild; root->lchild=root->rchild; root->rchild=temp; }}voidmain(){ BiTreeT; cout<<"請輸入水果名作為數的每個節(jié)點，空節(jié)點請輸入0，每個單詞后以0結尾"<<endl; CreateBiTree(T); cout<<"先序遍歷二叉樹："; PreOrder(T); cout<<endl<<"中序遍歷二叉樹："; InOrder(T); cout<<endl<<"后序遍歷二叉樹："; PostOrder(T); cout<<endl<<"交換二叉樹的左右孩子"; exchange(T); cout<<endl<<"先序遍歷二叉樹："; PreOrder(T); cout<<endl<<"中序遍歷二叉樹："; InOrder(T); cout<<endl<<"后序遍歷二叉樹："; PostOrder(T); cout<<endl;}運行結果：天津理工大學計算機科學與工程系實驗報告20XX至2