数据结构_二叉树_实验报告 北邮

数据结构实验报告1. 实验目的和内容：掌握二叉树基本操作的实现方法2. 程序分析2.1存储结构链式存储2．程序流程2.3关键算法分析算法一：Create(BiNode<T>* &R,T data[],int i,int n)【1】算法功能：创建二叉树【2】算法基本思想：利用顺序存储结构为输入，采用先建立根结点，再建立左右孩子的方法来递归建立二叉链表的二叉树【3】算法空间时间复杂度分析：O(n)【4】代码逻辑：如果位置小于数组的长度则{ 创建根结点将数组的值赋给刚才创建的结点的数据域创建左子树，如果当前结点位置为i,则左孩子位置为2i创建右子树，如果当前结点位置为i,则右孩子位置为2i+1}否则R为空算法二：CopyTree(BiNode<T>*sR,BiNode<T>* &dR)）【1】算法功能：复制构造函数【2】算法基本思想：按照先创建根结点，再递归创建左右子树的方法来实现。

【3】算法空间时间复杂度分析：O（n)【4】代码逻辑:如果源二叉树根结点不为空则{创建根结点调用函数自身，创建左子树调用函数自身，创建右子树}将该函数放在复制构造函数中调用，就可以实现复制构造函数算法三：PreOrder(BiNode<T>*R)【1】算法功能：二叉树的前序遍历【2】算法基本思想：这个代码用的是优化算法，提前让当前结点出栈。

【3】算法空间时间复杂度分析：O（n）【4】代码逻辑（伪代码）如果当前结点为非空，则{访问当前结点当前结点入栈将当前结点的左孩子作为当前结点}如果为空{则栈顶结点出栈则将该结点的右孩子作为当前结点}反复执行这两个过程，直到结点为空并且栈空算法四：InOrder(BiNode<T>*R)【1】算法功能：二叉树的中序遍历【2】算法基本思想：递归【3】算法空间时间复杂度分析：未知【4】代码逻辑：如果R为非空：则调用函数自身遍历左孩子访问该结点再调用自身访问该结点的右孩子算法五：LevelOrder(BiNode<T>*R)【1】算法功能：二叉树的层序遍历【2】算法基本思想：【3】算法空间时间复杂度分析：O（n）【4】代码逻辑（伪代码）：如果队列不空{对头元素出队访问该元素若该结点的左孩子为非空，则左孩子入队；若该结点的右孩子为非空，则右孩子入队；}算法六：Count(BiNode<T>*R)【1】算法功能：计算结点的个数【2】算法基本思想：递归【3】算法空间时间复杂度分析：未知【4】代码逻辑：如果R不为空的话{调用函数自身计算左孩子的结点数调用函数自身计算右孩子的结点数}template<class T>int BiTree<T>::Count(BiNode<T>*R){if(R==NULL)return 0;else{int m=Count(R->lchild);int n=Count(R->rchild);return m+n+1;}}算法七：Release(BiNode<T>*R)【1】算法功能：释放动态内存【2】算法基本思想：左右子树全部释放完毕后再释放该结点【3】算法空间时间复杂度分析：未知【4】代码逻辑：调用函数自身，释放左子树调用函数自身，释放右子树释放根结点释放二叉树template<class T>void BiTree<T>::Release(BiNode<T>*R) {if(R!=NULL){Release(R->lchild);Release(R->rchild);delete R;}}template<class T>BiTree<T>::~BiTree(){Release(root);}int main(){BiTree<int> BTree(a,10);BiTree<int>Tree(BTree);BTree.PreOrder(BTree.root);cout<<endl;Tree.PreOrder(Tree.root);cout<<endl;BTree.InOrder(BTree.root);cout<<endl;Tree.InOrder(Tree.root);cout<<endl;BTree.PostOrder(BTree.root);cout<<endl;Tree.PostOrder(Tree.root);cout<<endl;BTree.LevelOrder(BTree.root);cout<<endl;Tree.LevelOrder(Tree.root);cout<<endl;int m=BTree.Count(BTree.root);cout<<m<<endl;return 0;}3.测试数据：int a[10]={1,2,3,4,5};1 2 4 5 31 2 4 5 34 25 1 34 5 2 3 11 2 3 4 554.总结：4.1:这次实验大多用了递归的算法，比较好理解。

数据结构实验报告二叉树《数据结构与算法》实验报告专业班级姓名学号实验项目实验三二叉树。

实验目的1、掌握用递归方法实现二叉树的遍历。

2、加深对二叉树的理解，逐步培养解决实际问题的编程能力。

题目：(1)编写二叉树的遍历操作函数。

①先序遍历，递归方法re_preOrder(TREE *tree)②中序遍历，递归方法re_midOrder(TREE *tree)③后序遍历，递归方法re_postOrder(TREE *tree)(2)调用上述函数实现先序、中序和后序遍历二叉树操作。

算法设计分析（一）数据结构的定义要求用c语言编写一个演示程序，首先建立一个二叉树，让用户输入一个二叉树，实现该二叉树的便利操作。

二叉树型存储结构定义为：typedef struct TNode{ char data;//字符型数据struct TNode *lchild,*rchild;//左右孩子指针}TNode,* Tree;（二）总体设计程序由主函数、二叉树建立函数、先序遍历函数、中序遍历函数、后序遍历函数五个函数组成。

其功能描述如下：（1）主函数：统筹调用各个函数以实现相应功能。

int main()（2）二叉树建立函数：根据用户意愿运用先序遍历建立一个二叉树。

int CreateBiTree(Tree &T)（3）先序遍历函数：将所建立的二叉树先序遍历输出。

void PreOrder(Tree T)（4）中序遍历函数：将所建立的二叉树中序遍历输出。

void InOrder(Tree T)（5）后序遍历函数：将所建立的二叉树后序遍历输出。

void PostOrder(Tree T)（三）各函数的详细设计：（1）建立一个二叉树，按先序次序输入二叉树中结点的值（一个字符），‘#’表示空树。

对T动态分配存储空间，生成根节点，构造左、右子树（2）编写先序遍历函数，依次访问根节点、左子结点、右子节点（3）编写中序遍历函数，依次访问左子结点、根节点、右子节点（4）编写后序遍历函数，依次访问左子结点、右子节点、根节点（5）编写主函数，调用各个函数，以实现二叉树遍历的基本操作。

实验报告课程名：数据结构（C语言版）实验名：二叉排序树姓名：班级：学号：撰写时间：一实验目的与要求1.掌握二叉排序树上进行插入和删除的操作2.利用 C 语言实现该操作二实验内容•对于一个线形表, 利用不断插入的方法, 建立起一株二叉排序树•从该二叉排序树中删除一个叶子节点, 一个只有一个子树的非叶子节，一个有两个子树的非叶子节点。

三实验结果与分析#include<>#include<>删结点是叶子结点，直接删除if(p->left == NULL && p->right == NULL){删结点只有左子树else if(p->left && !(p->right)){p->left->parent=p->parent;删结点只有右孩子else if(p->right && !(p->left)){p->right->parent=p->parent;删除的结点既有左孩子，又有右孩子//该结点的后继结点肯定无左子树(参考上面查找后继结点函数)//删掉后继结点,后继结点的值代替该结点else{//找到要删除结点的后继q=searchSuccessor(p);temp=q->key;//删除后继结点deleteNode(root,q->key);p->key=temp;}return 1;}//创建一棵二叉查找树void create(PNode* root,KeyType *keyArray,int length) {int i;//逐个结点插入二叉树中for(i=0;i<length;i++)inseart(root,keyArray[i]);}int main(void){int i;PNode root=NULL;KeyType nodeArray[11]={15,6,18,3,7,17,20,2,4,13,9}; create(&root,nodeArray,11);for(i=0;i<2;i++)deleteNode(&root,nodeArray[i]);printf("%d\n",searchPredecessor(root)->key);printf("%d\n",searchSuccessor(root)->key);printf("%d\n",searchMin(root)->key);printf("%d\n",searchMax(root)->key);printf("%d\n",search(root,13)->key);return 0;}图1：二叉树排序实验结果。

数据结构实验报告实验名称：__ 哈夫曼树________学生姓名：______ 蔡宇豪_________________班级：________ 2 5____________________ 班内序号：__________15__________________学号：_________2012210673___________________ 日期：________2013.11.24____________________2. 程序分析2.1 存储结构哈夫曼树结点的存储结构包括双亲域parent，左子树lchild，右子树rchild，还有字符word，权重weight，编码code对用户输入的信息进行统计，将每个字符作为哈夫曼树的叶子结点。

统计每个字符出现的次数作为叶子的权重，统计次数可以根据每个字符不同的ASCII码，根据叶子结点的权重建立一个哈夫曼树2.2 关键算法分析要实现哈夫曼解/编码器，就必须用二叉树结构建立起哈夫曼树，其中有4个关键算法，首先是初始化函数，统计每个字符的频度，并建立起哈夫曼树；然后是建立编码表，将每个字符的编码输出；再次就是编码算法，根据编码表对输入的字符串进行编码，并将编码后的字符串输出；最后是译码算法，利用已经建好的赫夫曼树对编码后的字符串进行译码，并输出译码结果。

1.初始化函数int i,j;for(i=0;i<MAX;i++)a[i]=0; //先将a[]数组中每个值都赋为，不然程序会运行出错？for(i=0;s[i]!='\0';i++) //'\0'字符串结束标志{for(j=0;j<n;j++){if(s[i]==b[j]) //判断该字符是否已经出现过break;}if(j<n) //该字符出现过，对应计数器加一a[j]++;else//该字符为新字符,上面的循环全部运行完毕，j=n，记录到b[j]中，对应计数器加一{b[j]=s[i];a[j]++;n++; //出现的字符种类数加一}}//cout<<"共有"<<n<<"种字符，分别为:"<<endl;for(i=0;i<n;i++)cout<<b[i]<<"出现次数为:"<<a[i]<<endl;HTree=new HNode[2*n-1] ; //哈夫曼树初始化for(int i=0;i<2*n-1;i++){if(i<n){HTree[i].weight=a[i];}else{HTree[i].weight=0;}HTree[i].LChild=-1;HTree[i].RChild=-1;HTree[i].parent=-1;}int x,y,m1,m2; //x,y用于存放权值最小结点在数组中的下标for(int i=n;i<2*n-1;i++) //开始建哈夫曼树{//找出权值最小的结点m1=m2=MAX; //MAX=1000x=y=0;for(int j=0;j<i;j++){if(HTree[j].weight<m1&&HTree[j].parent==-1){m2=m1;m1=HTree[j].weight;x=j;}else if(HTree[j].weight < m2 && HTree[j].parent==-1){m2=HTree[j].weight;y=j;}}HTree[x].parent=HTree[y].parent=i;HTree[i].weight=HTree[x].weight+HTree[y].weight;HTree[i].LChild=x;HTree[i].RChild=y;HTree[i].parent=-1;2.生成编码表HCodeTable=new HCode[n];for(int i=0;i<n;i++){HCodeTable[i].data=b[i];int child=i;int parent=HTree[i].parent;int k=0;while(parent!=-1){if(child==HTree[parent].LChild)HCodeTable[i].code[k]='0';elseHCodeTable[i].code[k]='1';k++;child=parent;parent=HTree[child].parent;}HCodeTable[i].code[k]='\0';cout<<b[i]<<"的编码:";for(int j=k-1;j>=0;j--)cout<<HCodeTable[i].code[j];cout<<endl;}3.编码cout<<"编码后的字符串为:";while(*d!='\0'){for(int i=0;i<n;i++){if(b[i]==*d) //判断，每当出现一种时，就找到对应编码并输出{int k=strlen(HCodeTable[i].code);for(int j=k-1;j>=0;j--){*s=HCodeTable[i].code[j];cout<<*s;s++;}}}d++;}*s='\0';cout<<endl;【计算关键算法的时间、空间复杂度】关键算法A的时间复杂度为O(n)，关键算法B的时间复杂度为O(n),关键算法C的时间复杂度为O(n)，关键算法D的时间复杂度为O(n).2.3 其他程序完整代码：#include<iostream>using namespace std;const int MAX=1000;struct HNode{int weight;int parent;int LChild;int RChild;};struct HCode{char data;char code[200];};class Huffman{private:HNode *HTree; //哈夫曼树HCode *HCodeTable; //哈夫曼编码表char b[MAX]; //记录出现的字符int a[MAX]; //记录每个字符出现的次数，即权值static int n; //字符的种类数(静态变量)public:void init(char s[]); //初始化void init1(char s[]);void CreateCodeTable(); //创建编码表void Encoding(char *s,char *d); //编码void Decoding(char *s,char *d); //解码int count1() //算编码前长度{int q1=0;for(int i=0;i<n;i++){q1+=8*a[i];}return q1;}int count2() //算编码后长度{int q2=0;for(int i=0;i<n;i++){q2+=strlen(HCodeTable[i].code)*a[i];}return q2;}};int Huffman::n=0;void Huffman::init(char s[]){int i,j;for(i=0;i<MAX;i++)a[i]=0; //先将a[]数组中每个值都赋为，不然程序会运行出错？for(i=0;s[i]!='\0';i++) //'\0'字符串结束标志{for(j=0;j<n;j++){if(s[i]==b[j]) //判断该字符是否已经出现过break;}if(j<n) //该字符出现过，对应计数器加一a[j]++;else//该字符为新字符,上面的循环全部运行完毕，j=n，记录到b[j]中，对应计数器加一{b[j]=s[i];a[j]++;n++; //出现的字符种类数加一}}//cout<<"共有"<<n<<"种字符，分别为:"<<endl;for(i=0;i<n;i++)cout<<b[i]<<"出现次数为:"<<a[i]<<endl;HTree=new HNode[2*n-1] ; //哈夫曼树初始化for(int q=0;q<2*n-1;q++){if(q<n){HTree[q].weight=a[q];}else{HTree[q].weight=0;}HTree[q].LChild=-1;HTree[q].RChild=-1;HTree[q].parent=-1;}int x,y,m1,m2; //x,y用于存放权值最小结点在数组中的下标for(int w=n;w<2*n-1;w++) //开始建哈夫曼树{//找出权值最小的结点m1=m2=MAX; //MAX=1000x=y=0;for(int j=0;j<i;j++){if(HTree[j].weight<m1&&HTree[j].parent==-1){m2=m1;m1=HTree[j].weight;x=j;}else if(HTree[j].weight < m2 && HTree[j].parent==-1){m2=HTree[j].weight;y=j;}}HTree[x].parent=HTree[y].parent=w;HTree[w].weight=HTree[x].weight+HTree[y].weight;HTree[w].LChild=x;HTree[w].RChild=y;HTree[w].parent=-1;}}void Huffman::init1(char s[]){int i,j;for(i=0;i<MAX;i++)a[i]=0; //先将a[]数组中每个值都赋为，不然程序会运行出错？for(i=0;s[i]!='\0';i++) //'\0'字符串结束标志{for(j=0;j<n;j++){if(s[i]==b[j]) //判断该字符是否已经出现过break;}if(j<n) //该字符出现过，对应计数器加一a[j]++;else//该字符为新字符,上面的循环全部运行完毕，j=n，记录到b[j]中，对应计数器加一{b[j]=s[i];a[j]++;n++; //出现的字符种类数加一}}HTree=new HNode[2*n-1] ; //哈夫曼树初始化for(int e=0;e<2*n-1;e++){if(e<n){HTree[e].weight=a[e];}else{HTree[e].weight=0;}HTree[e].LChild=-1;HTree[e].RChild=-1;HTree[e].parent=-1;}int x,y,m1,m2; //x,y用于存放权值最小结点在数组中的下标，m1,m2用于存放两个无父结点且结点权值最小的两个结点for(int r=n;r<2*n-1;r++) //开始建哈夫曼树{//找出权值最小的结点m1=m2=MAX; //MAX=1000x=y=0;for(int j=0;j<r;j++){if(HTree[j].weight<m1&&HTree[j].parent==-1){m2=m1;//y=x;m1=HTree[j].weight;x=j;}else if(HTree[j].weight < m2 && HTree[j].parent==-1){m2=HTree[j].weight;y=j;}}HTree[x].parent=HTree[y].parent=r;HTree[r].weight=HTree[x].weight+HTree[y].weight;HTree[r].LChild=x;HTree[r].RChild=y;HTree[r].parent=-1;}}void Huffman::CreateCodeTable() //生成编码表{HCodeTable=new HCode[n];for(int i=0;i<n;i++){HCodeTable[i].data=b[i];int child=i;int parent=HTree[i].parent;int k=0;while(parent!=-1){if(child==HTree[parent].LChild)HCodeTable[i].code[k]='0';elseHCodeTable[i].code[k]='1';k++;child=parent;parent=HTree[child].parent;}HCodeTable[i].code[k]='\0';cout<<b[i]<<"的编码:";for(int j=k-1;j>=0;j--)cout<<HCodeTable[i].code[j];cout<<endl;}}void Huffman::Encoding(char *s,char *d) // 编码算法 //d为字符串{cout<<"编码后的字符串为:";while(*d!='\0'){for(int i=0;i<n;i++){if(b[i]==*d) //判断，每当出现一种时，就找到对应编码并输出{int k=strlen(HCodeTable[i].code);for(int j=k-1;j>=0;j--){*s=HCodeTable[i].code[j];cout<<*s;s++;}}}d++;}*s='\0';cout<<endl;}void Huffman::Decoding(char *s,char *d) //s为编码串{cout<<"解码后的字符串为:";while(*s!='\0'){int parent=2*n-1-1;while(HTree[parent].LChild!=-1){if(*s=='0')parent=HTree[parent].LChild;elseparent=HTree[parent].RChild;s++;}*d=HCodeTable[parent].data;cout<<*d;d++;}cout<<endl;void main(){int i=0;char d[MAX];char s[MAX];cout<<"请输入字符串:";while((d[i]=getchar())!='\n')i++;d[i]='\0';Huffman h;cout<<"哈夫曼功能："<<endl;cout<<"1.统计字符种类及出现次数"<<endl;cout<<"2.数据的编码解码"<<endl;cout<<"3.分析压缩效果"<<endl;int q;for(;;){cout<<"请输入（1~3）"<<endl;cin>>q;bool x=0;switch (q){case 1:h.init(d);break;case 2:h.init1(d);h.CreateCodeTable();h.Encoding(s,d);h.Decoding(s,d);break;case 3:cout<<"编码前的长度为:"<<h.count1()<<endl;cout<<"编码后的长度为:"<<h.count2()<<endl;cout<<"压缩比为:"<<(h.count2()*1.0/h.count1())<<endl;break;default:cout<<"请输入选择！！！！！"<<endl;break;}}3.}程序运行结果分析输入：I love data Structure, I love Computer。

数据结构实验报告实验名称:实验三树——哈夫曼编／解码器学生姓名:班级:班内序号：学号:日期:２014年12月11日1.实验要求利用二叉树结构实现赫夫曼编/解码器。

基本要求：1、初始化(Iｎiｔ):能够对输入得任意长度得字符串s进行统计,统计每个字符得频度,并建立赫夫曼树2、建立编码表(CreaｔeTabｌｅ)：利用已经建好得赫夫曼树进行编码,并将每个字符得编码输出。

3、编码(Encｏｄing）:根据编码表对输入得字符串进行编码,并将编码后得字符串输出。

4、译码(Ｄecｏding）：利用已经建好得赫夫曼树对编码后得字符串进行译码，并输出译码结果。

5、打印(Ｐrint)：以直观得方式打印赫夫曼树(选作）6、计算输入得字符串编码前与编码后得长度,并进行分析,讨论赫夫曼编码得压缩效果。

测试数据:I lｏvｅdata Sｔｒｕcture, I lovｅputｅr。

I wiｌｌtrｙmy best ｔｏsｔudy ｄata Structure、提示：１、用户界面可以设计为“菜单”方式:能够进行交互。

2、根据输入得字符串中每个字符出现得次数统计频度,对没有出现得ﻩ字符一律不用编码。

2、程序分析2、1存储结构Ｈuffmａn树给定一组具有确定权值得叶子结点,可以构造出不同得二叉树,其中带权路径长度最小得二叉树称为Hｕffｍan树,也叫做最优二叉树。

wｅighｔlchilｄｒcｈｉld paｒｅnt２－1－1-15－1-1-16-1－1-17-１－1-1９-１-1-1wｅigｈt lchild rchilｄparent 2-1-155-1－156-１－167-１－１69-１-177017１3２38165482967-12、2 关键算法分析(1)计算出现字符得权值利用AＳCII码统计出现字符得次数,再将未出现得字符进行筛选,将出现得字符及頻数存储在数组ａ[]中。

void Huffmａn::Iｎｉt(){ﻩｉｎｔｎNｕm［256]＝ {0}；／/记录每一个字符出现得次数ｉnｔ ch = cin、get();ｉnt i=0;ﻩwｈｉle(（ｃｈ!='\r') ＆& （ch!='\n'）)ﻩ｛ﻩﻩｎＮｕm[cｈ]＋＋; ／/统计字符出现得次数ﻩstr[i＋+] ＝ cｈ; //记录原始字符串ﻩcｈ = cin、geｔ（）; //读取下一个字符ﻩ}str[ｉ]='\0';n = 0;for ( ｉ=０;ｉ＜256;i＋+)ﻩ｛ﻩﻩｉｆ(nNｕm[i]>０) /／若nＮum[i］==0,字符未出现ﻩ{l[ｎ] = (cｈａｒ)i;ﻩa［ｎ] = nNum[ｉ]；n++;ﻩ}}}时间复杂度为O(１);（2）创建哈夫曼树:算法过程:Huffman树采用顺序存储---数组;数组得前ｎ个结点存储叶子结点,然后就是分支结点,最后就是根结点；首先初始化叶子结点元素—循环实现；以循环结构，实现分支结点得合成，合成规则按照hｕfｆmaｎ树构成规则进行。

二叉树实验报告1. 引言二叉树是一种常用的数据结构，广泛应用于计算机科学和信息技术领域。

本实验旨在通过对二叉树的理解和实现，加深对数据结构与算法的认识和应用能力。

本报告将介绍二叉树的定义、基本操作以及实验过程中的设计和实现。

2. 二叉树的定义二叉树是一个有序树，其每个节点最多有两个子节点。

树的左子节点和右子节点被称为二叉树的左子树和右子树。

3. 二叉树的基本操作3.1 二叉树的创建在实验中，我们通过定义一个二叉树的节点结构来创建一个二叉树。

节点结构包含一个数据域和左右指针，用于指向左右子节点。

创建二叉树的过程可以通过递归或者迭代的方式来完成。

3.2 二叉树的插入和删除二叉树的插入操作是将新节点插入到树中的合适位置。

插入时需要考虑保持二叉树的有序性。

删除操作是将指定节点从树中删除，并保持二叉树的有序性。

在实验中，我们可以使用递归或者循环的方式实现这些操作。

3.3 二叉树的遍历二叉树的遍历是指按照某种次序访问二叉树的所有节点。

常见的遍历方式包括前序遍历、中序遍历和后序遍历。

前序遍历先访问根节点，然后按照左孩子-右孩子的顺序递归遍历左右子树。

中序遍历按照左孩子-根节点-右孩子的顺序递归遍历左右子树。

后序遍历按照左孩子-右孩子-根节点的顺序递归遍历左右子树。

3.4 二叉树的查找查找操作是指在二叉树中查找指定的值。

可以通过递归或者循环的方式实现二叉树的查找操作。

基本思路是从根节点开始，通过比较节点的值和目标值的大小关系，逐步向左子树或者右子树进行查找，直到找到目标节点或者遍历到叶子节点。

4. 实验设计和实现在本实验中，我们设计并实现了一个基于Python语言的二叉树类。

具体实现包括二叉树的创建、插入、删除、遍历和查找操作。

在实验过程中，我们运用了递归和迭代的方法实现了这些操作，并进行了测试和验证。

4.1 二叉树类的设计我们将二叉树的节点设计为一个类，其中包括数据域和左右子节点的指针。

另外，我们设计了一个二叉树类，包含了二叉树的基本操作方法。

数据结构上机实验报告二叉树问题陈冠豪20102105010101015二O一O年5月26号实验目的建立一棵二叉树，要求分别用递归和非递归方法实现二叉树的先序、中序和后序遍历。

实现代码:#ifndef TREE_H#define TREE_H#include <stdio.h> #include <malloc.h> #include <stack>#include <queue>#include <assert.h> using namespace std; typedefintElemType;typedef struct treeT {ElemType key;struct treeT* left;struct treeT* right; }treeT, *pTreeT;static void visit(pTreeT root){if (NULL != root){printf(" %d\n", root->key);}}static pTreeT BT_MakeNode(ElemType target){pTreeT pNode = (pTreeT) malloc(sizeof(treeT)); assert( NULL != pNode );pNode->key = target;pNode->left = NULL;pNode->right = NULL;return pNode;}pTreeT BT_Insert(ElemType target, pTreeT* ppTree) {pTreeT Node;assert( NULL != ppTree );Node = *ppTree;if (NULL == Node){return *ppTree = BT_MakeNode(target);}if (Node->key == target) //不允许出现相同的元素 {return NULL;}else if (Node->key > target) //向左{return BT_Insert(target, &Node->left);}else{return BT_Insert(target, &Node->right);}}void BT_PreOrder(pTreeT root){if (NULL != root){visit(root);BT_PreOrder(root->left);BT_PreOrder(root->right);}}void BT_PreOrderNoRec(pTreeT root) {stack<treeT *> s;while ((NULL != root) || !s.empty()) {if (NULL != root){visit(root);s.push(root);root = root->left;}else{root = s.top();s.pop();}}void BT_InOrder(pTreeT root){if (NULL != root){BT_InOrder(root->left);visit(root);BT_InOrder(root->right);}}void BT_InOrderNoRec(pTreeT root) {stack<treeT *> s;while ((NULL != root) || !s.empty()) {if (NULL != root){s.push(root);else{root = s.top();visit(root);s.pop();root = root->right;}}}void BT_PostOrder(pTreeT root) {if (NULL != root){BT_PostOrder(root->left); BT_PostOrder(root->right); visit(root);}}void BT_PostOrderNoRec(pTreeT root) {}void BT_LevelOrder(pTreeT root) {queue<treeT *> q;treeT *treePtr;assert( NULL != root );q.push(root);while (!q.empty()){treePtr = q.front();q.pop();visit(treePtr);if (NULL != treePtr->left){q.push(treePtr->left);}if (NULL != treePtr->right) {q.push(treePtr->right); }}}#endif#include <stdio.h>#include <stdlib.h>#include <time.h>#define MAX_CNT 5#define BASE 100void main(int argc, char *argv[]) {int i;char temp;pTreeT root = NULL;srand( (unsigned)time( NULL ) );printf("请输入元素：\nA.自动生成.\nB.手动输入.\n");do{temp=getchar();}while(!(temp=='A'||temp=='a'||temp=='B'||temp=='b'));if((temp)=='A'||(temp)=='a'){for (i=0; i<MAX_CNT; i++){BT_Insert(rand() % BASE, &root);}}else if((temp)=='B'||(temp)=='b'){printf("请输入元素,元素以#结尾\n");while((temp=getchar())!='#')BT_Insert(temp, &root);}//前序printf("PreOrder:\n");BT_PreOrder(root);printf("\n");printf("PreOrder no recursion:\n"); BT_PreOrderNoRec(root);printf("\n");//中序printf("InOrder:\n");BT_InOrder(root);printf("\n");printf("InOrder no recursion:\n"); BT_InOrderNoRec(root);printf("\n");//后序printf("PostOrder:\n");BT_PostOrder(root);printf("\n");//层序printf("LevelOrder:\n");BT_LevelOrder(root);printf("\n");}。

实验报告：二叉树题目：建立一棵二叉树，数据以字符串形式从键盘输入，在此二叉树上完成：（1）前序、中序、后序遍历（2）求出叶子数（3）求树高（4）左右子树交换，输出交换后的前序、中序遍历序列分析：建树：输入的字符串序列为带有空节点的前序遍历序列（空节点用*表示）。

①：前序，中序，后序遍历：递归遍历②：求叶子数：当一个节点的左右孩子都是NULL时，此节点即为叶子节点。

③：求树高当前节点的树高等于其左右孩子树高大的加1。

④：左右子树交换：对于每个节点，将其左右孩子交换，再递归对其左右子树交换。

测试结果：附：源码#include <iostream>#include <stdlib.h>using namespace std;struct Bintree{char data;Bintree* lchild;Bintree* rchild;};Bintree *head;int sp;/* 已知一棵二叉树的前序序列，建立这棵树*/ void CreateTree(Bintree *&p,char a[]){Bintree *temp;if(a[sp]!=0){if(a[sp]=='*'){p=NULL;sp++;return ;}p=new Bintree;p->data=a[sp++];CreateTree(p->lchild,a);CreateTree(p->rchild,a);}else p=NULL;}/* 求一棵树的高度*/int Depth(Bintree *&t){int lh , rh ;if( t == NULL ){return 0 ;}else{lh = Depth( t->lchild ) ;rh = Depth( t->rchild ) ;return ( lh > rh ? lh : rh ) + 1 ;}}/* 将二叉树的左右子树互换*/ void Exchange1(Bintree *&t){Bintree *temp;if(t){Exchange1(t->lchild);Exchange1(t->rchild);temp=t->lchild;t->lchild=t->rchild;t->rchild=temp;}}/* 按照前序递归遍历二叉树*/ void Preorder1(Bintree *&t){if(t!=NULL){printf("%c",t->data);Preorder1(t->lchild);Preorder1(t->rchild);}}/* 按照中序递归遍历二叉树*/ void Inorder1(Bintree *&t){if(t!=NULL){Inorder1(t->lchild);printf("%c",t->data);Inorder1(t->rchild);}}/* 按照后序递归遍历二叉树*/void Posorder1(Bintree *&t){if(t!=NULL){Posorder1(t->lchild);Posorder1(t->rchild);printf("%c",t->data);}}/* 递归法求叶子结点个数*/int Leaves_Num1(Bintree *&t){if(t){if(t->lchild==NULL&&t->rchild==NULL){return 1;}return Leaves_Num1(t->lchild)+Leaves_Num1(t->rchild);}return 0;}/*******************************************/int main (){char a[100];memset(a,0,sizeof(a));cout<<"输入带有空节点的前序遍历序列（空节点用*表示）"<<endl;cin>>a;sp=0;CreateTree(head,a);cout<<"前序遍历："<<endl;Preorder1(head);cout<<endl;cout<<"中序遍历："<<endl;Inorder1(head);cout<<endl;cout<<"后序遍历："<<endl;Posorder1(head);cout<<endl;cout<<"叶子数："<<Leaves_Num1(head)<<endl;cout<<"树高："<<Depth(head)<<endl;cout<<"左右子树交换后"<<endl;Exchange1(head);cout<<"前序遍历："<<endl;Preorder1(head);cout<<endl;cout<<"中序遍历："<<endl;Inorder1(head);cout<<endl;cout<<"后序遍历："<<endl;Posorder1(head);cout<<endl;return 0;}。