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

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

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

3、針下標大于尾指針下標。 將一棵二叉樹的所有左右子樹進行交換建立二叉樹及先序void preorder(bitree *root)、中序void inorder(bitree *root)、后序void postorder(bitree *root)3種遍歷算法都寫成子函數(shù)，然后分別在子函數(shù)中調(diào)用。然后再建立一個實現(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ù)組作為隊列存放二叉鏈表中的結(jié)點，100為最大容量bitree *s; /二叉鏈表中的結(jié)點bitree *root; /二叉鏈表的根指針int front=1,rear=0

5、; /定義隊列的頭指針、尾指針char ch; /結(jié)點的data域值root=NULL;cout<<"請輸入結(jié)點值（不存在的結(jié)點用,表示，#表示結(jié)束）"<<endl;cin>>ch;while(ch!='#') /輸入值為#號，算法結(jié)束s=NULL;if(ch!=',') /輸入數(shù)據(jù)不為逗號，表示不為虛結(jié)點，否則為虛結(jié)點s=new bitree;s->data=ch;s->lchild=NULL;s->rchild=NULL;rear+;qrear=s; /新結(jié)點或虛結(jié)點進隊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+; /出隊cin>>ch;return root;void lorder(bitree *t) /按層次遍歷二叉樹bitree *q100,*p; /q代表隊列int f,r; /f、r類似于隊列頭指針、尾指針q1=t;f=r=1;cout<<"按層次

7、遍歷二叉樹的結(jié)果為："while (f<=r)p=qf;f+; /出隊cout<<p->data<<" "if(p->lchild!=NULL) r+; /入隊qr=p->lchild;if(p->rchild!=NULL)r+; /入隊qr=p->rchild;cout<<endl;void main()bitree *t;t=create(); /建立二叉連表lorder(t); /按層次遍歷二叉樹將一棵二叉樹的所有左右子樹進行交換#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<<"請輸入結(jié)點值，（,為虛結(jié)點，#結(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; /進隊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+; /出隊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) /將二叉樹的左右子樹進行交換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é)果"<<