⚽实现要求：
- 实验目的
掌握二叉树的基本概念，二叉树的存储结构使用链表。
- 实验内容
- 输入一个完全二叉树的层次遍历字符串，创建这个二叉树，输出这个二叉树的前序遍历字符串、中序遍历字符串、后序遍历字符串、结点数目、二叉树高度(上述每一个结果独立一行显示)。
- 输入二叉树前序序列和中序序列(各元素各不相同)，创建这个二叉树，输出该二叉树的后序序列、层次遍历。
🏐题目分析：
简单来说实验就是要我们实现三个东西：
一、根据完全二叉树的层次遍历字符串创建这个二叉树。这里这个完全二叉树非常关键，因为如果是一般的二叉树，仅仅有一个层次遍历序列是不能唯一确定一棵二叉树的。
二、前序、中序、后序遍历这个二叉树，然后计算结点数目以及二叉树的高度。这里计算结点数目非常容易，而计算二叉树的高度本质也就是后序遍历的变形。
三、通过一个二叉树的前序序列和中序序列来创建一个二叉树，并后序、层次遍历这个二叉树。这里考察的就是1、根据两个序列创建树。2、层次遍历一棵树
🏀代码展示：
前提类和函数声明：
#include<iostream> #include<queue> using namespace std; int size=0; char result[1000]; class TreeNode{//树中的每一个结点类 public: char data; TreeNode* leftN; TreeNode* rightN; public: TreeNode(){ data=' '; leftN=NULL; rightN=NULL; } TreeNode(char a){ data=a; leftN=NULL; rightN=NULL; } TreeNode(char a,TreeNode* l,TreeNode* r){ data=a; leftN=l; rightN=r; } }; TreeNode* mTree_pre_in(string a,string s);//两个序列创建树的函数声明 class Tree{//树本身的类 public: TreeNode* root; public: Tree(string a,int length){ if(length<=0)return; root=new TreeNode(a[1]); createTree(root,1,a); } Tree(){ root=NULL; } Tree(TreeNode* t){ root=t; } //对树的操作放在树这个类里面 void createTree(TreeNode* a,int index,string s);//根据层次序列构造树 //下面的遍历函数的参数a表示从哪个位置开始遍历 void preOrder(TreeNode* a); void inOrder(TreeNode* a); void proOrder(TreeNode* a); void levelOrder(TreeNode* a); int height(TreeNode* a);//求树的高度 };
🥎模块一（层次—>创建二叉树）：
//s就是层次序列，index表示从哪个下标结点开始创建（我们肯定是从1开始） void Tree::createTree(TreeNode* a,int index,string s){ int length=s.size(); if(2*index<length){//2*index得到的就是目前index下标对应结点的左节点 TreeNode* t=new TreeNode(s[index*2]); a->leftN=t; createTree(a->leftN,index*2,s); } if(index*2+1<length){2*index+1//得到的就是目前index下标对应结点的右节点 TreeNode* t=new TreeNode(s[index*2+1]); a->rightN=t; createTree(a->rightN,index*2+1,s); } }
🎱模块二（三种遍历方式、求树结点数目、求树高）：
//所有遍历的结果存储在result中，注意result应该是一个全局遍历而不是临时变量 //size表示目前result中元素的数目，必须是全局变量，并且在每次遍历后下一个遍历前都要重置为0 void Tree::preOrder(TreeNode* a){//前序遍历 if(a!=NULL){ result[size++]=a->data; preOrder(a->leftN); preOrder(a->rightN); } } void Tree::inOrder(TreeNode* a){//中序遍历 if(a!=NULL){ inOrder(a->leftN); result[size++]=a->data; inOrder(a->rightN); } } void Tree::proOrder(TreeNode* a){//后序遍历 if(a!=NULL){ proOrder(a->leftN); proOrder(a->rightN); result[size++]=a->data; } } int Tree::height(TreeNode* a){ if(a==NULL)//空结点的树高为0，即叶子结点下面的结点高为0 return 0;//递归一定要有终止的地方 else{//每一步重复操作就是递归使用的本质原因 int leftHeight=height(a->leftN); int rightHeight=height(a->rightN); if(leftHeight>rightHeight)return ++leftHeight; else return ++rightHeight; } }
❄️模块三（前序中序创建树、层次遍历树）：
//层次遍历树用到了队列这个数据结构，这里不过多解释 void Tree::levelOrder(TreeNode* a){ if(a==NULL) return; TreeNode* t=a; queue<TreeNode*> q; q.push(a); while(!q.empty()){ t=q.front(); result[size++]=t->data; q.pop(); if(t->leftN)q.push(t->leftN); if(t->rightN)q.push(t->rightN); } } //每次能分析出一个根节点加上左右子树的前后序列，所以每次可以添加一个结点 //创建树的本质就是创建新的结点在合适的位置 TreeNode* mTree_pre_in(string pre,string in,int length){ if(length==0)//如果前后序列为零，则不用创建 return NULL; //前序的第一个元素必定是树的根结点 TreeNode* root=new TreeNode(pre[1]); int count=0; //找到这个根节点在中序序列中的位置，因为中序序列根节点两边分别是左右子树 for(int i=1;i<=length;i++){ if(in[i]==pre[1]) count=i; } //得到左右子树的长度 int leftLength=count-1; int rightLength=length-count; //下面“1”+操作是为了让我们每次都是从下标1开始。主要为了方便树的操作 //下面就是分别对左右子树进行递归操作 //分析可得这个操作是前序遍历的一个变型 if(count!=0){ root->leftN=mTree_pre_in("1"+pre.substr(2,leftLength),"1"+in.substr(1,leftLength),leftLength); root->rightN=mTree_pre_in("1"+pre.substr(2+leftLength,rightLength),"1"+in.substr(count+1,rightLength),rightLength); } return root; }
📌完整代码展示（建议先把分模块的代码搞清楚）：
#include<iostream> #include<queue> using namespace std; int size=0; char result[1000]; class TreeNode{ public: char data; TreeNode* leftN; TreeNode* rightN; public: TreeNode(){ data=' '; leftN=NULL; rightN=NULL; } TreeNode(char a){ data=a; leftN=NULL; rightN=NULL; } TreeNode(char a,TreeNode* l,TreeNode* r){ data=a; leftN=l; rightN=r; } }; TreeNode* mTree_pre_in(string a,string s); class Tree{ public: TreeNode* root; public: Tree(string a,int length){ if(length<=0)return; root=new TreeNode(a[1]); createTree(root,1,a); } Tree(){ root=NULL; } Tree(TreeNode* t){ root=t; } void createTree(TreeNode* a,int index,string s); void preOrder(TreeNode* a);//下面的遍历函数的参数a表示从哪个位置开始遍历 void inOrder(TreeNode* a); void proOrder(TreeNode* a); void levelOrder(TreeNode* a); int height(TreeNode* a); }; TreeNode* mTree_pre_in(string pre,string in,int length){//每次能分析出一个根节点加上左右子树的前后序列，所以每次可以添加一个结点 if(length==0)//如果前后序列为零，则不用创建 return NULL; TreeNode* root=new TreeNode(pre[1]); int count=0; for(int i=1;i<=length;i++){ if(in[i]==pre[1]) count=i; } int leftLength=count-1; int rightLength=length-count; if(count!=0){ root->leftN=mTree_pre_in("1"+pre.substr(2,leftLength),"1"+in.substr(1,leftLength),leftLength); root->rightN=mTree_pre_in("1"+pre.substr(2+leftLength,rightLength),"1"+in.substr(count+1,rightLength),rightLength); } return root; } int Tree::height(TreeNode* a){ if(a==NULL)//空结点的树高为0，即叶子结点下面的结点高为0 return 0;//递归一定要有终止的地方 else{//每一步重复操作就是递归使用的本质原因 int leftHeight=height(a->leftN); int rightHeight=height(a->rightN); if(leftHeight>rightHeight)return ++leftHeight; else return ++rightHeight; } } void Tree::createTree(TreeNode* a,int index,string s){ int length=s.size(); if(2*index<length){ TreeNode* t=new TreeNode(s[index*2]); a->leftN=t; createTree(a->leftN,index*2,s); } if(index*2+1<length){ TreeNode* t=new TreeNode(s[index*2+1]); a->rightN=t; createTree(a->rightN,index*2+1,s); } } void printNode(char result[],int size){ for(int i=0;i<size-1;i++){ cout<<result[i]<<","; } cout<<result[size-1]<<endl; } void Tree::preOrder(TreeNode* a){ if(a!=NULL){ result[size++]=a->data; preOrder(a->leftN); preOrder(a->rightN); } } void Tree::inOrder(TreeNode* a){ if(a!=NULL){ inOrder(a->leftN); result[size++]=a->data; inOrder(a->rightN); } } void Tree::proOrder(TreeNode* a){ if(a!=NULL){ proOrder(a->leftN); proOrder(a->rightN); result[size++]=a->data; } } void Tree::levelOrder(TreeNode* a){ if(a==NULL) return; TreeNode* t=a; queue<TreeNode*> q; q.push(a); while(!q.empty()){ t=q.front(); result[size++]=t->data; q.pop(); if(t->leftN)q.push(t->leftN); if(t->rightN)q.push(t->rightN); } } int main(){ cout<<"Input1"<<endl; string s; cin>>s; cout<<"Output1"<<endl; string a="1"+s; int length=a.size(); Tree tree(a,length); tree.preOrder(tree.root);//前序遍历 printNode(result,size); size=0; tree.inOrder(tree.root);//中序遍历 printNode(result,size); size=0; tree.proOrder(tree.root);//后序遍历 printNode(result,size); size=0; int nodeNum=s.size(); int height1=tree.height(tree.root); cout<<nodeNum<<endl; cout<<height1<<endl; cout<<"Input2"<<endl; string s1; cin>>s1; string s2; cin>>s2; cout<<"Output2"<<endl; s1="1"+s1; s2="1"+s2; int l=s1.size()-1; TreeNode* t=mTree_pre_in(s1,s2,l); Tree tree2(t); tree2.proOrder(tree2.root); printNode(result,size); size=0; tree2.levelOrder(tree2.root); printNode(result,size); size=0; cout<<"End"<<endl; }
💓 最后总结：
最后总结与感悟 |
本题要求完成的是数据结构中的树结构，包括树的生成、树的遍历、树高的求解等，树的生成包括给定层次遍历序列生成、给定中序和前序序列生成。 首先明确一个点，树的结构和递归脱不开关系，也就是说树中的操作很多时候都是靠递归方法去解决的，树的整个结构就是一个递归结构。
总的来说就是1、整体过程是生成一棵树 2、子过程是对每一个结点生成并链接它的左右结点。如此，子过程不断重复整个树便可以形成
注意的点：
|
创作不易，如果觉得内容不错，收藏一下呗，小猫求求了~
真的真的不行，就给个免费的赞吧~~
