下载文档原格式
数据结构实验报告实验五二叉树的操作班级：12卓越6班学号：***********名：***任课教师：***计算机与信息工程学院2014年5月13 日实验五二叉树的操作一、实验目的1．进一步掌握指针变量、动态变量的含义；2．掌握二叉树的结构特征，以及各种存储结构的特点及适用范围；3．掌握用指针类型描述、访问和处理二叉树的运算。
二、实验要求1．按实验内容编写实验的程序，主程序以菜单形式运行。
2．上机调试运行本程序。
3．保存和打印出程序的运行结果，并结合程序进行分析。
4．提交源程序和运行结果。
三、实验内容1．创建以二叉链表作存储结构的二叉树；2．按中序遍历二叉树；3．按层次遍历二叉树；4．计算二叉树的单枝结点数；5．交换二叉树的左右子树。
解：//声明类BiTree及定义结构BiNode,文件名为bitree.h#ifndef BITREE_H#define BITREE_H//int num;template <class T>struct BiNode //二叉树的结点结构{T data;BiNode<T> *lchild, *rchild;};template <class T>class BiTree{public:BiTree( ); //构造函数，初始化一棵二叉树，其前序序列由键盘输入~BiTree(void); //析构函数，释放二叉链表中各结点的存储空间BiNode<T>* Getroot(); //获得指向根结点的指针void PreOrder(BiNode<T> *root); //前序遍历二叉树void InOrder(BiNode<T> *root); //中序遍历二叉树void PostOrder(BiNode<T> *root); //后序遍历二叉树void LeverOrder(BiNode<T> *root); //层序遍历二叉树int depth(BiNode<T> *root); //求二叉树的深度void nodenum(BiNode<T> *root); //求二叉树的结点个数void leafnum(BiNode<T> *root); //求二叉树的叶子结点个数void empty( ); //判断二叉树是否为空int printnum( ); // 输出（全部、叶子或单分支）结点数void sbnodenum(BiNode<T> *root); //求二叉树的单分支结点个数void exchangetree(BiNode<T> *root); //交换二叉树的左右子树private:BiNode<T> *root; //指向根结点的头指针BiNode<T> *p;BiNode<T> *Creat( ); //有参构造函数调用void Release(BiNode<T> *root); //析构函数调用int num;};#endif//定义类中的成员函数，文件名为bitree.cpp#include<iostream>#include<string>#include"bietree.h"using namespace std;/**前置条件：二叉树不存在*输入：无*功能：构造一棵二叉树*输出：无*后置条件：产生一棵二叉树*/template<class T>BiTree<T>::BiTree( ){this->num=0;this->root = Creat( );}/**前置条件：二叉树已存在*输入：无*功能：释放二叉链表中各结点的存储空间*输出：无*后置条件：二叉树不存在*/template<class T>BiTree<T>::~BiTree(void){Release(root);}*前置条件：二叉树已存在*输入：无*功能：获取指向二叉树根结点的指针*输出：指向二叉树根结点的指针*后置条件：二叉树不变*/template<class T>BiNode<T>* BiTree<T>::Getroot( ){return root;}/**前置条件：二叉树已存在*输入：无*功能：前序遍历二叉树*输出：二叉树中结点的一个线性排列*后置条件：二叉树不变*/template<class T>void BiTree<T>::PreOrder(BiNode<T> *root) {if(root==NULL) return;else{cout<<root->data<<" ";PreOrder(root->lchild);PreOrder(root->rchild);}}*前置条件：二叉树已存在*输入：无*功能：中序遍历二叉树*输出：二叉树中结点的一个线性排列*后置条件：二叉树不变*/template <class T>void BiTree<T>::InOrder (BiNode<T> *root){if (root==NULL) return; //递归调用的结束条件else{InOrder(root->lchild); //中序递归遍历root的左子树cout<<root->data<<" "; //访问根结点的数据域InOrder(root->rchild); //中序递归遍历root的右子树}}/**前置条件：二叉树已存在*输入：无*功能：后序遍历二叉树*输出：二叉树中结点的一个线性排列*后置条件：二叉树不变*/template <class T>void BiTree<T>::PostOrder(BiNode<T> *root){if (root==NULL) return; //递归调用的结束条件else{PostOrder(root->lchild); //后序递归遍历root的左子树PostOrder(root->rchild); //后序递归遍历root的右子树cout<<root->data<<" "; //访问根结点的数据域}}/**前置条件：二叉树已存在*输入：无*功能：层序遍历二叉树*输出：二叉树中结点的一个线性排列*后置条件：二叉树不变*/template <class T>void BiTree<T>::LeverOrder(BiNode<T> *root){const int MaxSize = 100;int front = 0;int rear = 0; //采用顺序队列，并假定不会发生上溢BiNode<T>* Q[MaxSize];BiNode<T>* q;if (root==NULL) return;else{Q[rear++] = root;while (front != rear){q = Q[front++];cout<<q->data<<" ";if (q->lchild != NULL) Q[rear++] = q->lchild;if (q->rchild != NULL) Q[rear++] = q->rchild;}}}/**前置条件：空二叉树*输入：数据ch;*功能：初始化一棵二叉树,构造函数调用*输出：无*后置条件：产生一棵二叉树*/template <class T>BiNode<T>* BiTree<T>::Creat( ){BiNode<T>* root;T ch;cout<<"请输入创建一棵二叉树的结点数据"<<endl;cin>>ch;if (ch=="#") root = NULL;else{root = new BiNode<T>; //生成一个结点root->data=ch;root->lchild = Creat( ); //递归建立左子树root->rchild = Creat( ); //递归建立右子树}return root;}/**前置条件：二叉树已经存在*输入：无*功能：释放二叉树的存储空间，析构函数调用*输出：无*后置条件：二叉树不存在*/template<class T>void BiTree<T>::Release(BiNode<T>* root){if (root != NULL){Release(root->lchild); //释放左子树Release(root->rchild); //释放右子树delete root;}}/**前置条件：二叉树已经存在*输入：无*功能：求二叉树的深度*输出：二叉树的深度*后置条件：二叉树不变*/template<class T>int BiTree<T>::depth(BiNode<T> *root){int n,m;if(root==NULL) return 0;else{n=depth(root->lchild); //左子树的深度m=depth(root->rchild); //右子树的深度if (n>m)return n+1;elsereturn m+1;}}/**前置条件：二叉树已经存在*输入：无*功能：求二叉树的结点个数*输出：二叉树的结点个数*后置条件：二叉树不变*/template<class T>void BiTree<T>::nodenum(BiNode<T> *root){if(root==NULL) return;else{num++;nodenum(root->lchild); //左子树的结点个数nodenum(root->rchild); //右子树的结点个数}}*前置条件：二叉树已经存在*输入：无*功能：求二叉树2 的叶子结点个数*输出：二叉树的叶子结点个数*后置条件：二叉树不变*/template<class T>void BiTree<T>::leafnum(BiNode<T> *root){if(root==NULL) return;else{if(!(root->lchild) && !(root->rchild)) //判断是否为叶子结点num++;leafnum(root->lchild); //左子树中的叶子结点个数leafnum(root->rchild); //右子树中的叶子结点个数}}/*将全局变量num初始化为0*/template<class T>void BiTree<T>::empty( ){num=0;}输出全局变量num的值*/template<class T>int BiTree<T>::printnum( ){return num;}/**前置条件：二叉树已经存在*输入：无*功能：求二叉树的单分支结点个数*输出：二叉树的单分支结点个数*后置条件：二叉树不变*/template<class T>void BiTree<T>::sbnodenum(BiNode<T> *root){if(root==NULL) return;else{if((!(root->lchild) && (root->rchild))||((root->lchild) && !(root->rchild))) //判断是否为叶子结点num++;sbnodenum(root->lchild); //左子树中的叶子结点个数sbnodenum(root->rchild); //右子树中的叶子结点个数}}/**前置条件：二叉树已经存在*输入：无*功能：交换二叉树的左右子树*输出：无*后置条件：二叉树左右子树交换*/template<class T>void BiTree<T>::exchangetree(BiNode<T> *root){if(root==NULL) return;else{if((root->rchild)&&(root->lchild)) //判断左右叶子结点都存在{ p=root->lchild;root->lchild=root->rchild;root->rchild=p;}exchangetree(root->lchild); //左子树中的叶子结点个数exchangetree(root->rchild); //右子树中的叶子结点个数}}/* BiNode<T> * Q[20];BiNode<T> *q;int front=-1;int rear=-1;int n=0;int m=0;Q[++rear]=root;if(root==NULL)cout<<0;else{while(front!=rear){q=Q[++front];if(q->lchild==NULL && q->rchild!=NULL)m++;if(q->lchild!=NULL && q->rchild==NULL)n++;if(q->lchild!=NULL) Q[++rear]=q->lchild;if(q->rchild!=NULL) Q[++rear]=q->rchild;}}cout<<"单分支节点的个数为:"<<m+n<<endl;*///二叉树的主函数，文件名为bitreemain.cpp#include<iostream>#include<string>#include"bietree.cpp"using namespace std;void main(){BiTree<string> bt; //创建一棵树BiNode<string>* root = bt.Getroot( ); //获取指向根结点的指针int s=-1;while(s!=0){cout<<"1.前序遍历"<<endl;cout<<"2.中序遍历"<<endl;cout<<"3.后序遍历"<<endl;cout<<"4.层序遍历"<<endl;cout<<"5.树的深度"<<endl;cout<<"6.叶子节点个数"<<endl;cout<<"7.单分支结点个数"<<endl;cout<<"8.左右子树交换后的结果"<<endl;cout<<"0.退出"<<endl;cin>>s;switch(s){ case 1:bt.PreOrder(root);cout<<endl;break;case 2:bt.InOrder(root);cout<<endl;break;case 3:bt.PostOrder(root);cout<<endl;break;case 4:bt.LeverOrder(root);cout<<endl;break;case 5:cout<<"树的深度为："<<bt.depth(root)<<endl;break;case 6:bt.empty();bt.leafnum(root);cout<<"叶子结点个数为："<<bt.printnum()<<endl;break;case 7:bt.empty();bt.sbnodenum(root);cout<<"单分支结点个数为："<<bt.printnum()<<endl;break;case 8:bt.empty();bt.exchangetree(root);cout<<"左右子树交换后的结果：";bt.PreOrder(root);cout<<endl;break;case 0:exit(0);}}}。
实验四 二叉树(一)一.实验目的（1）进一步掌握指针变量的用途和程序设计方法。
（2）掌握二叉树的结构特征，以及链式存储结构的特点及程序设计方法。
（3）掌握构造二叉树的基本方法。
（4）掌握二叉树遍历算法的设计方法。
二．实验要求（1）认真阅读和掌握和本实验相关的教材内容。
（2）掌握一个实际二叉树的创建方法。
（3）掌握二叉链存储结构下二叉树操作的设计方法和遍历操作设计方法。
三．实验内容（1）定义二叉链存储结构。
（2）按照二叉树的性质5来建立一棵实际二叉树的操作，编写求二叉数的树深的函数。
（3）编写中序遍历二叉树的函数。
（4）编写求二叉数的结点总数的函数。
(5)编写测试主函数并上机运行。
打印出运行结果，并结合程序运行结果进行分析。
四. 实验要求（1）利用二叉树的性质5来建立二叉树，输入数据时需要将结点的序号（按满二叉树编号）和数据同时给出：序号 数据元素。
结合下图的二叉树数的输入据顺序应该是：1 1，2 2，3 3，4 4，6 5，7 6，13 7，14 8，15 9。
本算法采用程序如下，请填空使程序完整。
typedef struct stu{char data; （ ）;} BiTNode ; /* 利用二叉树性质5 ，借助一维数组V 建立二叉树 */BiTNode *creat_bt1() { BiTNode *t,*p,*v[20]; int i; Etype e;/* 输入结点的序号i 、结点的数据e */printf("\n i,data=?");scanf("%d%d",&i,&e);（ ） /* 当 i ,e 都为0时，结束循环 */{ p=(BiTNode *)malloc(sizeof(BiTNode));p->data=e;p->lch=NULL;（ ）;v[i]=p;if (i==1) t=p; /* 序号为1的结点是根 */else{ j=i/2;if(i%2==0) v[j]->lch=p; /* 序号为偶数，做左孩子*/else v[j]->rch=p; /* 序号为奇数，做右孩子*/}printf("\n i,data=?"); scanf("%d,%d",&i,&e);}（ ）;} /* creat_bt1 */Void main( ){BiTNode *t,*q;9t=（）;//中序遍历二叉树//求二叉数的树深printf("\n");}（2）编写中序遍历二叉树的函数；（3）编写求二叉数的树深的函数；（4）编写求二叉数的结点总数的函数。
实验三二叉树基本操作（2课时）一、实验目的1.掌握二叉树的结构特征，以及各种存储结构的特点及使用范围。
2.掌握用指针类型描述、访问和处理二叉树的运算。
二、实验要求1.程序结构清晰、语句完整，包含有头文件和main函数；2.格式正确，语句采用缩进格式；3.运行结果正确，输入输出有提示，格式美观。
三、实验设备、材料和工具1.奔腾2计算机或以上机型2.turboc2,vc++，TC++四、实验内容和步骤实验内容：1.统计一棵二叉树中每种类型结点数（度为0、1、2的结点数）。
2.分别输入一棵有6个结点和8个结点的二叉树，编程序输出先序、中序和后序的遍历结果。
3.哈夫曼树及哈夫曼编码。
五、实验报告要求1．根据实验内容初步设计好程序,并从理论上排除错误；2．针对程序的健壮性准备好测试数据；3．结果分析中如实填写运行后的结果，并记录调试过程中产生的重要问题和解决方法。
六、根据实验过程填写下面内容1：程序：#include"test.h"int LeafCount1=0,LeafCount2=0,LeafCount3=0;void leaf_a(BiTree root){if(root!=NULL){leaf_a(root->LChild);leaf_a(root->RChild);if(root->LChild==NULL&&root->RChild==NULL)LeafCount1++;else if(root->LChild==NULL||root->RChild==NULL)LeafCount2++;else if(root->LChild!=NULL||root->RChild!=NULL)LeafCount3++;elseprintf("不符合题意！");}}void main(){BiTree root;printf("按先序遍历序列建立二叉树，请输入需要插入的序列:\n");CreateBiTree(&root);// PreOrder(root);leaf_a(root);printf("度为0的节点数：%d\n",LeafCount1);printf("度为1的节点数：%d\n",LeafCount2);printf("度为2的节点数：%d\n",LeafCount3);}#include <stdio.h>#include <malloc.h>#include <conio.h>typedef char DataType;void Visit(char ch){printf("%c ",ch);}typedef struct Node{DataType data;struct Node *LChild;struct Node *RChild;}BiTNode, *BiTree;void CreateBiTree(BiTree *bt){char ch;ch = getchar();if(ch=='#')*bt=NULL;else{*bt=(BiTree)malloc(sizeof(BiTNode)); //生成一个新结点(*bt)->data=ch;CreateBiTree(&((*bt)->LChild)); //生成左子树CreateBiTree(&((*bt)->RChild)); //生成右子树}}void PreOrder(BiTree root)/*先序遍历二叉树, root为指向二叉树(或某一子树)根结点的指针*/ {if (root!=NULL){Visit(root->data); /*访问根结点*/PreOrder(root->LChild); /*先序遍历左子树*/PreOrder(root->RChild); /*先序遍历右子树*/ }}void InOrder(BiTree root)/*中序遍历二叉树, root为指向二叉树(或某一子树)根结点的指针*/ {if (root!=NULL){InOrder(root ->LChild); /*中序遍历左子树*/Visit(root ->data); /*访问根结点*/InOrder(root ->RChild); /*中序遍历右子树*/}}void PostOrder(BiTree root)/* 后序遍历二叉树，root为指向二叉树(或某一子树)根结点的指针*/ {if(root!=NULL){PostOrder(root ->LChild); /*后序遍历左子树*/PostOrder(root ->RChild); /*后序遍历右子树*/Visit(root ->data); /*访问根结点*/}}结果分析：（要求完全理解程序，需每人答辩）ab cd ef2：程序：#include"bitree.h"void main(){BiTree T;char ch;printf("按照先序遍历建立二叉树，请输入序列：\n");CreateBiTree(&T);printf("\n先序遍历为:"); //先序遍历PreOrder(T);printf("\n中序遍历为:"); //中序遍历InOrder(T);printf("\n后序遍历为:"); //后序遍历PostOrder(T);}#include <stdio.h>#include <malloc.h>#include <conio.h>#define false 0#define true 1typedef char DataType;typedef struct Node{DataType data;struct Node *LChild;struct Node *RChild;}BiTNode, *BiTree;void CreateBiTree(BiTree *bt){char ch;ch=getchar();if(ch=='#')*bt=NULL;else{*bt=(BiTree)malloc(sizeof(BiTNode)); //生成一个新结点(*bt)->data=ch;CreateBiTree(&((*bt)->LChild)); //生成左子树CreateBiTree(&((*bt)->RChild)); //生成右子树}}void PreOrder(BiTree root)/*先序遍历二叉树, root为指向二叉树(或某一子树)根结点的指针*/ {if (root!=NULL){printf("%c ",root ->data); /*访问根结点*/PreOrder(root ->LChild); /*先序遍历左子树*/PreOrder(root ->RChild); /*先序遍历右子树*/}}void InOrder(BiTree root)/*中序遍历二叉树, root为指向二叉树(或某一子树)根结点的指针*/ {if (root!=NULL){InOrder(root ->LChild); /*中序遍历左子树*/printf("%c ",root ->data); /*访问根结点*/InOrder(root ->RChild); /*中序遍历右子树*/}}void PostOrder(BiTree root)/* 后序遍历二叉树，root为指向二叉树(或某一子树)根结点的指针*/ {if(root!=NULL){PostOrder(root ->LChild); /*后序遍历左子树*/PostOrder(root ->RChild); /*后序遍历右子树*/printf("%c ",root ->data); /*访问根结点*/}}结果分析：（要求完全理解程序，需每人答辩）第一个8个结点的二叉树图形为：b cef g h第二个为6个节点的二叉树图形：ab cd e f对结点的输出实现递归调用，输出各种遍历的情况3：程序：#include <stdio.h>#include <stdlib.h>#include <string.h>#include "huffman.h"//typedef char* HuffmanCode;/*动态分配数组，存储哈夫曼编码*//*typedef struct{unsigned int weight ; /* 用来存放各个结点的权值unsigned int parent, LChild,RChild ; //指向双亲、孩子结点的指针}HTNode, * HuffmanTree; //动态分配数组，存储哈夫曼树*///输出哈夫曼树void outputHuffman(HuffmanTree HT, int m){if(m!=0){printf("%d ", HT[m].weight);outputHuffman(HT,HT[m].LChild);outputHuffman(HT,HT[m].RChild);}}HuffmanTree HT; //ht哈夫曼树HuffmanCode HC; //hc哈弗曼编码int *w;int i,n; // 元素的个数;int wei; // 元素的权值;int m;printf("输入哈夫曼树的总结点树:" );scanf("%d",&n);w=(int *)malloc((n+1)*sizeof(int));for(i=1;i<=n;i++){printf("请输入第%d个元素的权值：",i);fflush(stdin);//清除缓存scanf("%d",&wei);w[i]=wei;}CrtHuffmanTree(&HT,w,n);m = 2*n-1;outputHuffman(HT,m);printf("\n");CrtHuffmanCode(&HT,&HC,n);}#include <stdio.h>#include <stdlib.h>#include <string.h>#define N 20#define M 2*N-1typedef char* HuffmanCode[N+1];/*存储N个哈夫曼编码串的头指针数组*/{unsigned int weight ; /* 用来存放各个结点的权值*/unsigned int parent, LChild,RChild ; /*指向双亲、孩子结点的指针*/ }HTNode, HuffmanTree[M+1]; /*动态分配数组，存储哈夫曼树*/void select(HuffmanTree *ht,int n, int *s1, int *s2){int i;int min;for(i=1; i<=n; i++){if((*ht)[i].parent == 0){ min = i;i = n+1;}}for(i=1; i<=n; i++){if((*ht)[i].parent == 0){if((*ht)[i].weight < (*ht)[min].weight)min = i;}}*s1 = min;for(i=1; i<=n; i++){if((*ht)[i].parent == 0 && i!=(*s1)){ min = i;i = n+1;}}for(i=1; i<=n; i++){if((*ht)[i].parent == 0 && i!=(*s1)){if((*ht)[i].weight < (*ht)[min].weight)min = i;}}*s2 = min;}void CrtHuffmanCode(HuffmanTree *ht, HuffmanCode *hc, int n)/*从叶子结点到根，逆向求每个叶子结点对应的哈夫曼编码*/{char *cd;int i;unsigned int c;int start;int p;hc=(HuffmanCode *)malloc((n+1)*sizeof(char *)); /*分配n个编码的头指针*/cd=(char * )malloc(n * sizeof(char )); /*分配求当前编码的工作空间*/cd[n-1]='\0'; /*从右向左逐位存放编码，首先存放编码结束符*/for(i=1;i<=n;i++) /*求n个叶子结点对应的哈夫曼编码*/{start=n-2; /*初始化编码起始指针*/for(c=i,p=(*ht)[i].parent; p!=0; c=p,p=(*ht)[p].parent) /*从叶子到根结点求编码*/ if( (*ht)[p].LChild == c){cd[start]='0'; /*左分支标0*/--start;}else{cd[start]='1'; /*右分支标1*/--start;}(*hc)[i]=(char *)malloc((n-start)*sizeof(char)); /*为第i个编码分配空间*/strcpy((*hc)[i],&cd[start+1]);}free(cd);for(i=1;i<=n;i++)printf("%d编码为%s\n",(*ht)[i].weight,(*hc)[i]);}void CrtHuffmanTree(HuffmanTree *ht , int *w, int n){ /* w存放已知的n个权值，构造哈夫曼树ht */int m,i;int s1,s2;m=2*n-1;// *ht=(HuffmanTree)malloc((m+1)*sizeof(HTNode)); /*0号单元未使用*/ for(i=1;i<=n;i++){/*1-n号放叶子结点，初始化*/(*ht)[i].weight = w[i];(*ht)[i].LChild = 0;(*ht)[i].parent = 0;(*ht)[i].RChild = 0;}for(i=n+1;i<=m;i++){(*ht)[i].weight = 0;(*ht)[i].LChild = 0;(*ht)[i].parent = 0;(*ht)[i].RChild = 0;} /*非叶子结点初始化*//* ------------初始化完毕！对应算法步骤1---------*/for(i=n+1;i<=m;i++) /*创建非叶子结点,建哈夫曼树*/{ /*在(*ht)[1]~(*ht)[i-1]的范围内选择两个parent为0且weight最小的结点，其序号分别赋值给s1、s2返回*/select(ht,i-1,&s1,&s2);(*ht)[s1].parent=i;(*ht)[s2].parent=i;(*ht)[i].LChild=s1;(*ht)[i].RChild=s2;(*ht)[i].weight=(*ht)[s1].weight+(*ht)[s2].weight;}}/*哈夫曼树建立完毕*/结果分析：（要求完全理解程序，需每人答辩）通过调用select函数找出最小的两个权值，用CrtHuffman函数存放权值构成哈夫曼树再调用CrtHuffmanCode函数实现从叶子结点到根，逆向求每个叶子结点对应的哈弗曼编码。
实验三二叉树的基本运算一、实验目的1、使学生熟练掌握二叉树的逻辑结构和存储结构。
2、熟练掌握二叉树的各种遍历算法。
二、实验内容1、问题描述建立一棵二叉树，试编程实现二叉树的如下基本操作：(1). 按先序序列构造一棵二叉链表表示的二叉树T；(2). 对这棵二叉树进行遍历：先序、中序、后序以及层次遍历，分别输出结点的遍历序列；(3). 求二叉树的深度/结点数目/叶结点数目；(选做)(4). 将二叉树每个结点的左右子树交换位置。
（选做）2、基本要求从键盘接受输入（先序），以二叉链表作为存储结构，建立二叉树（以先序来建立）。
3、测试数据如输入：abc00de0g00f000（其中ф表示空格字符）则输出结果为：先序：a->b->c->d->e->g->f中序：a->b->c->d->e->g->f后序：a->b->c->d->e->g->f三、程序代码#include<malloc.h>#include<iostream.h>#define OK 1#define ERROR -1typedef char TElemType;int i;typedef struct BiTNode{TElemType data;struct BiTNode *lchild,*rchild;}BiTNode,*BiTree;int CreateBiTree(BiTree&T) //创建二叉树{char a;cin>>a;if(a=='0') T=NULL;else{if(!(T=(BiTNode*)malloc(sizeof(BiTNode)))) {return ERROR;}T->data=a;CreateBiTree(T->lchild);CreateBiTree(T->rchild);}return OK;}int PreOrderTraverse(BiTree&T) //先序遍历二叉树{if(T){//cout<<"此为先序遍历"<<endl;cout<<T->data<<"->";if(PreOrderTraverse(T->lchild))if(PreOrderTraverse(T->rchild))return OK;return ERROR;}else return OK;}int InOrderTraverse(BiTree&T) //中序遍历二叉树{if(T){//cout<<"此为中序遍历"<<endl;if(InOrderTraverse(T->lchild)){cout<<T->data<<"->";if(InOrderTraverse(T->rchild))return OK;}return ERROR;}else return OK;}int PostOrderTraverse(BiTree&T) //后序遍历二叉树{if(T){//cout<<"此为后序遍历"<<endl;if (PostOrderTraverse(T->lchild))if(PostOrderTraverse(T->rchild)){cout<<T->data<<"->";i++;return (OK);}return (ERROR);}elsereturn (OK);}int CountDepth(BiTree&T) //计算二叉树的深度{if(T==NULL){return 0;}else{int depl=CountDepth(T->lchild);int depr=CountDepth(T->lchild);if(depl>depr){return depl+1;}else{return depr+1;}}}void main() //主函数{BiTree T;cout<<"请输入二叉树节点的值以创建树"<<endl;CreateBiTree(T);cout<<"此为先序遍历";PreOrderTraverse(T);cout<<"end"<<endl;cout<<"此为中序遍历";InOrderTraverse(T);cout<<"end"<<endl;cout<<"此为后序遍历";PostOrderTraverse(T);cout<<"end"<<endl<<"此树节点数是"<<i<<endl<<"此树深度是"<<CountDepth(T)<<endl;}四、调试结果及运行界面：五、实验心得通过这次程序上机实验让我认识到了以前还不太了解的二叉树的性质和作用，这次实验的的确确的加深了我对它的理解。
二叉排序树的实验报告二叉排序树的实验报告引言：二叉排序树（Binary Search Tree，简称BST）是一种常用的数据结构，它将数据按照一定的规则组织起来，便于快速的查找、插入和删除操作。
本次实验旨在深入了解二叉排序树的原理和实现，并通过实验验证其性能和效果。
一、实验背景二叉排序树是一种二叉树，其中每个节点的值大于其左子树的所有节点的值，小于其右子树的所有节点的值。
这种特性使得在二叉排序树中进行查找操作时，可以通过比较节点的值来确定查找的方向，从而提高查找效率。
二、实验目的1. 理解二叉排序树的基本原理和性质；2. 掌握二叉排序树的构建、插入和删除操作；3. 验证二叉排序树在查找、插入和删除等操作中的性能和效果。
三、实验过程1. 构建二叉排序树首先，我们需要构建一个空的二叉排序树。
在构建过程中，我们可以选择一个节点作为根节点，并将其他节点插入到树中。
插入节点时，根据节点的值与当前节点的值进行比较，如果小于当前节点的值，则将其插入到当前节点的左子树中；如果大于当前节点的值，则将其插入到当前节点的右子树中。
重复这个过程，直到所有节点都被插入到树中。
2. 插入节点在已有的二叉排序树中插入新的节点时，我们需要遵循一定的规则。
首先，从根节点开始，将新节点的值与当前节点的值进行比较。
如果小于当前节点的值，则将其插入到当前节点的左子树中；如果大于当前节点的值，则将其插入到当前节点的右子树中。
如果新节点的值与当前节点的值相等，则不进行插入操作。
3. 删除节点在二叉排序树中删除节点时，我们需要考虑不同的情况。
如果要删除的节点是叶子节点，即没有左右子树，我们可以直接删除该节点。
如果要删除的节点只有一个子树，我们可以将子树连接到要删除节点的父节点上。
如果要删除的节点有两个子树，我们可以选择将其右子树中的最小节点或左子树中的最大节点替代该节点，并删除相应的替代节点。
四、实验结果通过对二叉排序树的构建、插入和删除操作的实验，我们得到了以下结果：1. 二叉排序树可以高效地进行查找操作。
实验报告课程名称：数据结构
第 1 页共4 页
五、实验总结（包括心得体会、问题回答及实验改进意见，可附页）
这次实验主要是建立二叉树，和二叉树的先序、中序、后续遍历算法。
通过这次实验，我巩固了二叉树这部分知识,从中体会理论知识的重要性。
在做实验之前，要充分的理解本次实验的理论依据，这样才能达到事半功倍的效果。
如果在没有真正理解实验原理之盲目的开始实验，只会浪费时间和精力。
例如进行二叉树的遍历的时候，要先理解各种遍历的特点。
先序遍历是先遍历根节点，再依次先序遍历左右子树。
中序遍历是先中序遍历左子树，再访问根节点，最后中序遍历右子树。
而后序遍历则是先依次后续遍历左右子树，再访问根节点。
掌握了这些，在实验中我们就可以融会贯通，举一反三。
其次要根据不光要懂得代码的原理，还要对题目有深刻的了解，要明白二叉树的画法，在纸上先进行自我演练，对照代码验证自己写的正确性。
第 3 页共4 页
第 4 页共4 页。
实验三二叉树的操作实验三二叉树的操作一．实验目的1、基本要求：深刻理解二叉树性质和及各种存储结构的特点及适用范围；掌握用指针类型描述、访问和处理二叉树的运算；熟练掌握二叉树的遍历算法；2、较高要求: 在遍历算法的基础上设计二叉树更复杂操作算法；认识哈夫曼树、哈夫曼编码的作用和意义;掌握树与森林的存储与便利。
二. 实验学时：课内实验学时：3学时课外实验学时：6学时三．备选实验题目1．以二叉链表为存储结构，实现二叉树的创建、遍历（实验类型：验证型）1）问题描述：在主程序中设计一个简单的菜单，分别调用相应的函数功能：1…建立树2…前序遍历树3…中序(非递归)遍历树4…后序遍历树0…结束2）实验要求：在程序中定义下述函数，并实现要求的函数功能：CreateTree(): 按从键盘输入的前序序列，创建树PreOrderTree()：前序遍历树（递归）InOrderTree()：中序(非递归)遍历树LaOrderTree(): 后序遍历树（递归）3）实验提示:二叉链表存储数据类型定义# define ElemType char //元素类型typedef struct BiTNode{ ElemType data;struct BiTNode *lchild,*rchild;}BiTNode,*BiTree;元素类型可以根据实际情况选取。
4）注意问题:注意理解递归算法的执行步骤。
注意字符类型数据在输入时的处理。
重点理解如何利用栈结构实现非递归算法2．编写算法交换二叉树中所有结点的左、右子树（实验类型：综合型）1）问题描述：编写一算法，交换二叉树中所有结点的左、右子树2）实验要求：以二叉链表作为存储结构3) 实现提示：设二叉树的根指针未t，且以二叉链表表示，可利用一个类型为seqstack的指针来实现，且栈单元包含两个域，一个为data，另一个为top，整个栈容量为maxsize，当树非空时，将当前的树根结点入栈，同时将当前栈顶元素出栈当作根结点，然后依据当前的根结点是否具有孩子结点来判定是否将其左、右指针进行交换；再将交换后的左指针或右指针入栈，这样反复进行，直到栈空为止。
实验二二叉树的基本操作
一、实验目的与基本要求
掌握二叉树的结构特性，以及存储结构的特点。
掌握在链式存储结构上实现二叉树的基本操作的编程技术。
掌握用指针类型描述，访问和处理二叉树的运算。
二、实验准备
硬件：一台微机
软件：操作系统和Microsoft VC++ 6.0
三、实验内容
1、编写算法实现完全二叉树的性质5
设对一完全二叉树（含有15个结点个数）有如下说明：
int bt[16]，i；/* 结点编号从1开始*/
任意给定结点i，验证关于完全二叉树的性质，即i的两个子结点为2*i和2*i+1，i的双亲结点为i/2。
2、编写算法实现二叉树三种遍历
（1）功能
建立二叉树，并进行遍历。
（2）输入要求
使用按数组标号法输入的方法构造二叉链表即构造二叉树。
二叉树结点中的数据为字符型，输入元素序号与值顺序为1A，2B，3C，4D，6F, 7G , 输入的两个数据都为0时，结束输入。
（3）测试数据
用三种递归方法输出遍历结果。
概要设计：
模块划分为5个，即（1）用数组表示输入法构造二叉链表,即编写建立二叉树的函数create （2）递归先序、中序、后序遍历3个模块；
（3）主函数。
调用create函数，建立一颗二叉树；然后分别调用先序、中序、后序遍历函数，将二叉树的先序、中序和后序遍历序列输出到屏幕上。
四、实验要求
1．用C完成算法设计和程序设计并上机调试通过。
2．撰写实验报告，提供实验结果和数据。
五、程序实现
写出每个操作的算法（操作过程）
六、程序运行情况
写出输入数据及运行结果
1。
