二叉链表存储结构、二叉树相关操作

数据结构与算法实验报告             姓名：孙瑞霜 

一、实验目的

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);//确立第一个结点，即根节点

C#多线程系列(3)：原子操作

 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部门的代码进去，点击运行，在泛起的界面中根据提醒输入数据，一步步按下回车键即可运行该程序，最后测试完毕，关闭界面。