數(shù)據(jù)結(jié)構(gòu) 二叉鏈表 C實(shí)現(xiàn)

1、實(shí) 驗(yàn) 報(bào) 告一、 實(shí)驗(yàn)?zāi)康?. 掌握二叉樹的數(shù)據(jù)類型描述及二叉樹的特性。2. 掌握二叉樹的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)（二叉鏈表）的建立算法。3. 掌握二叉鏈表上二叉樹的基本運(yùn)算的實(shí)現(xiàn)。二、 實(shí)驗(yàn)內(nèi)容1. 實(shí)現(xiàn)二叉樹的層次遞進(jìn)。2. 將一顆二叉樹的所有左右子樹進(jìn)行交換。三、 實(shí)驗(yàn)與算法分析二叉樹的遍歷二叉樹的層次遍歷采用的是隊(duì)列。本題用一個(gè)一維數(shù)組來(lái)代替隊(duì)列，同時(shí)設(shè)置隊(duì)列的對(duì)頭指針和隊(duì)尾指針。算法分析：自定義3個(gè)函數(shù)：結(jié)構(gòu) struct bitree；建立二叉鏈表的函數(shù) bitree *create()；按層次遍歷二叉鏈表的函數(shù) void lorder(bitree *t)。結(jié)構(gòu) struct bitree

2、 中包括數(shù)據(jù)域和兩個(gè)指針域（一個(gè)指向左孩子，另一個(gè)指向右孩子）。建立二叉鏈表的函數(shù) bitree *create() 中先建立一個(gè)空隊(duì)列（條件是front=1，rear=0）。 然后建立二叉鏈表，用一個(gè)一維數(shù)組來(lái)代替隊(duì)列，存放輸入的結(jié)點(diǎn)；輸入結(jié)點(diǎn)時(shí)，必須按照完全二叉樹的形式輸入；如果非完全二叉樹，則必須給定一些假象結(jié)點(diǎn)（虛結(jié)點(diǎn)），使之完全符合完全二叉樹形式。當(dāng)我們輸入“，”時(shí)表示虛結(jié)點(diǎn)（結(jié)點(diǎn)不存在）；輸入結(jié)點(diǎn)值時(shí)，存在的結(jié)點(diǎn)則輸入它對(duì)應(yīng)的字符；最后以一個(gè)特殊字符“#”作為輸入的結(jié)束，表示二叉鏈表已經(jīng)完成。層次遍歷二叉鏈表的函數(shù) void lorder(bitree *t) 中遍歷結(jié)束條件為頭指

3、針下標(biāo)大于尾指針下標(biāo)。 將一棵二叉樹的所有左右子樹進(jìn)行交換建立二叉樹及先序void preorder(bitree *root)、中序void inorder(bitree *root)、后序void postorder(bitree *root)3種遍歷算法都寫成子函數(shù)，然后分別在子函數(shù)中調(diào)用。然后再建立一個(gè)實(shí)現(xiàn)左右子樹交換的函數(shù)void leftTOright( bitree *r)。左右子樹交換的遍歷算法為：若二叉樹為空，算法結(jié)束；否則：交換左子樹的左子樹和右子樹；交換右子樹的左子樹和右子樹；交換左子樹和右子樹的位置。最后，是程序的主函數(shù)main（），它包含 建立二叉鏈表，輸出交換前二叉

4、樹的先序、中序、后序的結(jié)果，輸出交換后 二叉鏈表的先序、中序、后序的遍歷結(jié)果。輸出前后結(jié)果，方便比較順序變化。四、 可執(zhí)行程序及注釋二叉樹層次遍歷#include <iostream.h>typedef char elemtype;struct bitreeelemtype data;bitree *lchild,*rchild;bitree *create() /建立二叉連表bitree *q100; /定義q數(shù)組作為隊(duì)列存放二叉鏈表中的結(jié)點(diǎn)，100為最大容量bitree *s; /二叉鏈表中的結(jié)點(diǎn)bitree *root; /二叉鏈表的根指針int front=1,rear=0

5、; /定義隊(duì)列的頭指針、尾指針char ch; /結(jié)點(diǎn)的data域值root=NULL;cout<<"請(qǐng)輸入結(jié)點(diǎn)值（不存在的結(jié)點(diǎn)用,表示，#表示結(jié)束）"<<endl;cin>>ch;while(ch!='#') /輸入值為#號(hào)，算法結(jié)束s=NULL;if(ch!=',') /輸入數(shù)據(jù)不為逗號(hào)，表示不為虛結(jié)點(diǎn)，否則為虛結(jié)點(diǎn)s=new bitree;s->data=ch;s->lchild=NULL;s->rchild=NULL;rear+;qrear=s; /新結(jié)點(diǎn)或虛結(jié)點(diǎn)進(jìn)隊(duì)if(rear

6、=1)root=s;elseif(s!=NULL)&&(qfront!=NULL)if(rear%2=0) /rear為偶數(shù)，s為雙親左孩子qfront->lchild=s;else /rear為奇數(shù)，s為雙親右孩子qfront->rchild=s;if(rear%2=1)front+; /出隊(duì)cin>>ch;return root;void lorder(bitree *t) /按層次遍歷二叉樹bitree *q100,*p; /q代表隊(duì)列int f,r; /f、r類似于隊(duì)列頭指針、尾指針q1=t;f=r=1;cout<<"按層次

7、遍歷二叉樹的結(jié)果為："while (f<=r)p=qf;f+; /出隊(duì)cout<<p->data<<" "if(p->lchild!=NULL) r+; /入隊(duì)qr=p->lchild;if(p->rchild!=NULL)r+; /入隊(duì)qr=p->rchild;cout<<endl;void main()bitree *t;t=create(); /建立二叉連表lorder(t); /按層次遍歷二叉樹將一棵二叉樹的所有左右子樹進(jìn)行交換#include<iostream.h>typ

8、edef char elemtype;struct bitreeelemtype data;bitree *lchild,*rchild;bitree *create() /建立二叉樹bitree *root,*s,*q100;int front=1,rear=0;char ch;root=NULL;cout<<"請(qǐng)輸入結(jié)點(diǎn)值，（,為虛結(jié)點(diǎn)，#結(jié)束）"<<endl;cin>>ch;while(ch!='#')s=NULL;if(ch!=',')s=new bitree;s->data=ch;s->

9、;lchild=NULL;s->rchild=NULL;rear+;qrear=s; /進(jìn)隊(duì)if(rear=1)root=s;elseif(s!=NULL)&&(qfront!=NULL)if(rear%2=0)qfront->lchild=s;elseqfront->rchild=s;if(rear%2=1)front+; /出隊(duì)cin>>ch;return root;void preorder(bitree *root) /先序遍歷bitree *p;p=root;if (p!=NULL)cout<<p->data<&l

10、t;" "preorder(p->lchild);preorder(p->rchild);void inorder(bitree *root) /中序遍歷bitree *p;p=root;if(p!=NULL)inorder(p->lchild);cout<<p->data<<" "inorder(p->rchild);void postorder(bitree *root) /后序遍歷bitree *p;p=root;if(p!=NULL)postorder(p->lchild);postor

11、der(p->rchild);cout<<p->data<<" "void leftToright(bitree *r) /將二叉樹的左右子樹進(jìn)行交換bitree *root=r;if(root!=NULL)leftToright(root->lchild);leftToright(root->rchild);bitree *t=root->lchild;root->lchild=root->rchild;root->rchild=t;void main()bitree *root;root=creat

12、e(); /建立二叉樹cout<<endl<<endl<<"左右子樹交換前的遍歷結(jié)果"<<endl;cout<<"先序遍歷的結(jié)果"<<endl;preorder(root);cout<<endl;cout<<"中序遍歷的結(jié)果"<<endl;inorder(root);cout<<endl;cout<<"后序遍歷的結(jié)果"<<endl;postorder(root);cout<<endl;leftToright(root);cout<<endl<<endl<<"左右子樹交換后的遍歷結(jié)果"<<endl;cout<<"先序遍歷的結(jié)果"<<