樹

實驗五 樹

一、實驗目的

熟悉二叉樹的鏈式存儲結(jié)構(gòu)

掌握二叉樹的建立、深度優(yōu)先遞歸遍歷等算法

能夠利用遍歷算法實現(xiàn)一些應用

二、實驗內(nèi)容

已知二叉樹采用二叉鏈表存儲結(jié)構(gòu)，如果左、右子樹非空，且左子樹根結(jié)點大于右子樹根結(jié)點，則交換根結(jié)點的左、右子樹。即按要求交換二叉樹及子樹的左、右子樹。

采用二叉鏈表結(jié)構(gòu)存儲一棵二叉樹，編寫一個算法統(tǒng)計該二叉樹中結(jié)點總數(shù)及葉子結(jié)點總數(shù)。

Tips

使用遞歸算法，判斷條件交換左右字數(shù)即可

遍歷過程中統(tǒng)計結(jié)點數(shù)，判斷葉子結(jié)點數(shù)

Answer

5.1

//交換左右子樹的程序代碼 #include<stdio.h> //#include<malloc.h> #include<stdlib.h> //二叉鏈表的結(jié)構(gòu)類型定義 const int maxsize=1024; typedef char datatype; typedef struct node {datatype data;struct node *lchild,*rchild; }bitree;bitree* creattree(); void preorder(bitree*); void swap(bitree*); void swap2(bitree*);//void main() int main() {bitree*pb;pb=creattree();preorder(pb);printf("\n");swap(pb);preorder(pb);printf("\n");return 0; }//二叉樹的建立 bitree*creattree() {char ch;bitree*Q[maxsize];int front,rear;bitree*root,*s;root=NULL;front=1;rear=0;printf("按層次輸入二叉樹，虛結(jié)點輸入'@'，以'#'結(jié)束輸入：\n");while((ch=getchar())!='#'){s=NULL;if(ch!='@'){s=(bitree*)malloc(sizeof(bitree));s->data=ch;s->lchild=NULL;s->rchild=NULL;}rear++;Q[rear]=s;if(rear==1){root=s;}else{if(s&&Q[front]){if(rear%2==0){Q[front]->lchild=s;}else{Q[front]->rchild=s;}}if(rear%2==1){front++;}}}return root; }//先序遍歷按層次輸出二叉樹 void preorder(bitree*p) {if(p!=NULL){printf("%c",p->data);if(p->lchild!=NULL||p->rchild!=NULL){printf("(");preorder(p->lchild);if(p->rchild!=NULL)printf(",");preorder(p->rchild);printf(")");}} }//交換左右子樹 void swap(bitree*p) {bitree*t;if(p!=NULL){if(p->lchild!=NULL && p->rchild!=NULL && p->lchild->data > p->rchild->data){t=p->lchild;p->lchild=p->rchild;p->rchild=t;}swap(p->lchild);swap(p->rchild);} }

5.2

//統(tǒng)計結(jié)點總數(shù)及葉子結(jié)點總數(shù)的程序代碼 #include<stdio.h> //#include<malloc.h> #include<stdlib.h> //二叉鏈表的結(jié)構(gòu)類型定義 const int maxsize=1024; typedef char datatype; typedef struct node {datatype data;struct node *lchild,*rchild; }bitree;bitree*creattree(); void preorder(bitree*); int countnode(bitree*); int countleaf(bitree*);//void main() int main() {bitree*root;int leafnum,nodenum;root=creattree();printf("刪除子樹之前的二叉樹：");preorder(root);printf("\n");nodenum=countnode(root);printf("結(jié)點總數(shù)是：%d\n",nodenum);leafnum=countleaf(root);printf("葉子結(jié)點總數(shù)是：%d\n",leafnum);return 0; }//建立二叉樹 bitree*creattree() {datatype ch;bitree*Q[maxsize];int front,rear;bitree*root,*s;root=NULL;front=1;rear=0;printf("按層次輸入結(jié)點值，虛結(jié)點輸入'@'，以換行符結(jié)束：");while((ch=getchar())!='\n'){s=NULL;if(ch!='@'){s=(bitree*)malloc(sizeof(bitree));s->data=ch;s->lchild=NULL;s->rchild=NULL;}rear++;Q[rear]=s;if(rear==1){root=s;}else{if(s&&Q[front]){if(rear%2==0){Q[front]->lchild=s;}else{Q[front]->rchild=s;}}if(rear%2==1){front++;}}}return root; }//先序遍歷輸出二叉樹 void preorder(bitree*p) {if(p!=NULL){printf("%c",p->data);if(p->lchild!=NULL||p->rchild!=NULL){printf("(");preorder(p->lchild);if(p->rchild!=NULL) printf(",");preorder(p->rchild);printf(")");}} }//統(tǒng)計結(jié)點個數(shù) int countnode(bitree *p) {static int node=0;if(p!=NULL){node++;node = countnode(p->lchild);node = countnode(p->rchild);}return node; }//統(tǒng)計葉子結(jié)點個數(shù) int countleaf(bitree *p) {static int leaf=0;{if(p!=NULL){leaf = countleaf(p->lchild);if((p->lchild==NULL) && (p->rchild==NULL)){leaf = countleaf(p->rchild);}}}return leaf; }

轉(zhuǎn)載于:https://www.cnblogs.com/vanlion/p/datastructure-exp-5.html

總結(jié)

以上是生活随笔為你收集整理的《软件技术基础》实验指导 实验五的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。