二叉鏈表存儲結構、二叉樹相關操作
- 2020 年 4 月 18 日
- 筆記
數據結構與算法實驗報告 姓名：孫瑞霜
一、實驗目的
1、複習二叉樹的二叉鏈表存儲結構，能夠實現二叉樹的創建、遍歷等基本操作；
2、掌握建立二叉鏈表（代碼4.13）、二叉樹的先序中序後序層序等遍歷操作的實現。
二、實驗要求：
1． 認真閱讀和掌握教材上和本實驗相關的內容和算法。
2． 上機將相關算法實現。
3． 實現上面實驗目的要求的功能，並能進行簡單的驗證。
三、實驗內容
1、 必做內容：二叉樹的創建和遍歷操作（遞歸算法）部分
編程實現二叉樹的二叉鏈表存儲表示的基本操作，這些基本操作至少包括：二叉樹的創建、二叉樹的先序遍歷、中序遍歷和後序遍歷的遞歸算法實現。要求能夠進行簡單的輸入輸出驗證。
2、選做內容：二叉樹的遍歷操作的非遞歸算法，求二叉樹的高度、寬度。
#include<queue>
using namespace std;
/*二叉樹存儲結構：二叉鏈表*/
typedef struct TNode * Position;
typedef Position BinTree; //二叉樹類型
struct TNode
{//樹結點結構定義
ElementType Data; //結點數據
BinTree Left; //指向左子樹
BinTree Right; //指向右子樹
};
/*二叉鏈表的操作 表示*/
void PreorderTraversal(BinTree BT); //先序遍歷
void InorderTraversal(BinTree BT); //中序遍歷
void PostorderTraversal(BinTree BT); //後序遍歷
void LevelorderTraversal(BinTree BT); //層序遍歷
void PreorderPrintLeaves(BinTree BT); //先序輸出葉子
int GetHeight(BinTree BT); //求二叉樹高度
BinTree CreatBinTreeFromLevelorder(); //層序建立二叉樹
BinTree CreatBinTreeFromPreorder(); //先序建立二叉樹
int main(void)
{
BinTree BT;
BT=CreatBinTreeFromLevelorder();
// BT=CreatBinTreeFromPreorder();
printf(“\n其先序序列為：“);
PreorderTraversal(BT);
printf(“\n其中序序列為：“);
InorderTraversal(BT);
printf(“\n其後序序列為：“);
PostorderTraversal(BT);
printf(“\n其層序序列為：“);
LevelorderTraversal(BT);
/*
printf(“\n其高度為：%d”,GetHeight(BT));
printf(“\n先序輸出葉子為：\n “);
PreorderPrintLeaves(BT);
*/
return 0;
}
三、算法描述
該算法涉及到了二叉樹的創建（層序建立或先序建立）、二叉樹的先序遍歷、中序遍歷和後序遍歷的遞歸算法實現及二叉樹的層序遍歷，在進行先序輸出葉子結點時首先要明確葉子結點指那些度為零的結點，再按照先序遍歷的順序輸出葉節點，另外還進行了求二叉樹高度的算法，共分為七部進行。
四、詳細設計
五、程序代碼
#include<stdio.h>
#include<stdlib.h>
#include<queue>
#define NoInfo #
using namespace std;
/*二叉樹存儲結構：二叉鏈表*/
typedef char ElementType;
typedef struct TNode * Position;
typedef Position BinTree;//二叉樹類型
struct TNode
{ //樹結點結構定義
char Data;//結點數據
BinTree Left; //指向左子樹
BinTree Right;//指向右子樹
};
/*二叉鏈表的操作表示*/
BinTree CreatBinTreeFromLevelorder();//層序建立二叉樹
//BinTree CreatBinTreeFromPreorder();先序建立二叉樹
void PreorderTraversal(BinTree BT);//先序遍歷
void InorderTraversal(BinTree BT);//中序遍歷
void PostorderTraversal(BinTree BT);//後序遍歷
void LevelorderTraversal(BinTree BT);//層序遍歷
void PreorderPrintLeaves(BinTree BT);//先序輸出葉子
int GetHeight(BinTree BT);//求二叉樹高度
int main(void)
{
BinTree BT;
printf(“層序建立二叉樹：“); //printf(“先序建立二叉樹:”) ;
BT=CreatBinTreeFromLevelorder();// BT=CreatBinTreeFromPreorder();
printf(“\n其先序序列為：“);
PreorderTraversal(BT);
printf(“\n其中序序列為：“);
InorderTraversal(BT);
printf(“\n其後序序列為：“);
PostorderTraversal(BT);
printf(“\n其層序序列為：“);
LevelorderTraversal(BT);
printf(“\n先序輸出葉子為： “);
PreorderPrintLeaves(BT);
printf(“\n其高度為：%d”,GetHeight(BT));
return 0;
}
BinTree CreatBinTreeFromLevelorder(){
ElementType Data;
BinTree BT,T;
queue <BinTree> Q;//生成一個隊列
scanf(“%c”,&Data);//建立第一個結點，即根節點
if(Data!=’#’){ //分配根節點單元，並將結點數據量入列
BT=(BinTree)malloc(sizeof(struct TNode));
BT->Data=Data;
BT->Left=NULL;
BT->Right=NULL;
Q.push(BT);//若第一個數據就是#，返回空間
}
else return NULL;
while(!Q.empty()){
T=Q.front();
Q.pop();
scanf(“%c”,&Data);
if(Data==’#’)
T->Left=NULL;
else{
T->Left=(BinTree)malloc(sizeof(struct TNode));
T->Left->Data=Data;
T->Left->Left=T->Left->Right=NULL;
Q.push(T->Left);
}
scanf(“%c”,&Data);
if(Data==’#’)
T->Right=NULL;
else{
T->Right=(BinTree)malloc(sizeof(struct TNode));
T->Right->Data=Data;
T->Right->Left=T->Right->Right=NULL;
Q.push(T->Right);
}
} //結束while循環
return BT;
}
//以上為層序建立二叉樹的操作
/*或者是BT=CreatBinTreeFromPreorder();如下
BinTree CreatBinTreeFromPreorder(){
ElementType c;
BinTree T;
scanf(“%c”,&c);
if(c==0)
T=NULL;
else{
if(!(T=(BinTree)malloc(sizeof(struct TNode)))) exit(0);
T->Data=c;
T->Left=CreatBinTreeFromPreorder();
T->Right=CreatBinTreeFromPreorder();
}
return T;
}
*/
void PreorderTraversal( BinTree BT ){
if(BT){
printf(“%c”,BT->Data);
PreorderTraversal(BT->Left);
PreorderTraversal(BT->Right);
}
}
//以上為先序遍歷操作
void InorderTraversal( BinTree BT ){
if(BT){
InorderTraversal(BT->Left);
printf(“%c”,BT->Data);
InorderTraversal(BT->Right);
}
}
//以上為中序遍歷操作
void PostorderTraversal( BinTree BT ){
if(BT){
PostorderTraversal(BT->Left);
PostorderTraversal(BT->Right);
printf(“%c”,BT->Data);
}
}
//以上為後序遍歷操作
void LevelorderTraversal( BinTree BT ){
queue <BinTree> Q;
BinTree T;
if(!BT)
return;
Q.push(BT);
while(!Q.empty()){
T=Q.front();
Q.pop();
printf(“%c”,T->Data);
if(T->Left)
Q.push(T->Left);
if(T->Right)
Q.push(T->Right);
}
}
//以上為層序遍歷操作
void PreorderPrintLeaves(BinTree BT){
if(BT){
if(!BT->Left&&!BT->Right)
printf(“%c”,BT->Data);
PreorderPrintLeaves(BT->Left);
PreorderPrintLeaves(BT->Right);
}
}
//以上為先序輸出葉子的操作
int GetHeight( BinTree BT ){
char hl,hr,maxh;
if(BT){
hl=GetHeight(BT->Left);
hr=GetHeight(BT->Right);
maxh=hl>hr?hl:hr;
return(maxh+1);
}
else return 0;
}
//以上為求二叉樹高度的操作
六、測試和結果
七、用戶手冊
打開devC++，新建一個源程序，拷貝5部分的代碼進去，點擊運行，在出現的界面中按照提示輸入數據，一步步按下回車鍵即可運行該程序，最後測試完畢，關閉界面。
