这是我在学习数据结构时写的，可以实现各种功能，有main，danyuan.h，danyuan.cpp使用说明如下： 所有数据单元在输入时都要输入，即使是空节点，比如树： A B C O D E F G # # H 则输入ABCODEFG##H 注意输入的元素之间无空格 理论将输出 前序遍历：ABOG#D#HCEF 中序遍历：GO#B#DHAECF 后序遍历：FECH#D#GOBA 层次遍历：ABCODEFG##H 他的树高4，结点8 请勿输入其它字符 main.cpp文件
#include <iostream> #include "danyuan.h" using namespace std; void creatbycc(danyuan tree[],string s,int n);// void cengci(danyuan tree[],int n);///层次遍历 void qianxu(danyuan tree[],int n,int i);///前序遍历 void houxu(danyuan tree[],int n,int i);///后序遍历 void zhongxu(danyuan tree[],int n,int i);///中序遍历 int depth(int n);//求树高 int find(danyuan tree[],E e,int n);///搜索函数 //int chazhao(E s,danyuan tree[],int n,int i){
// if(i>n||i==-1){
// }else{
// if(tree[i].reit()==s){
// return i; // }else{
// chazhao(s,tree,n,tree[i].releft()); // chazhao(s,tree,n,tree[i].reright()); // } // } //} int main(){
cout<<"------层次建树操作---------"<<endl;
string s;
cout<<"请按照层次遍历的顺序输入，空节点用#表示"<<endl;
cin>>s;//数据单元中的元素
int n=s.length();//最大的编号+1
int k=0;//空节点数
for(int i=0;i<n;i++){
if(s[i]=='#'){
k++;}
}
danyuan tree[n];//建立二叉树
creatbycc(tree,s,n);//通过层次遍历建立二叉树
system("cls");
cout<<"------1.前序遍历-----------"<<endl;
cout<<"------2.中序遍历-----------"<<endl;
cout<<"------3.后序遍历-----------"<<endl;
cout<<"------4.层次遍历-----------"<<endl;
cout<<"------5.求树高和结点个数---"<<endl;
cout<<"------6.层次查找-----------"<<endl;
cout<<"------0.结束程序-----------"<<endl;
int dd;
A:
cout<<"请输入要执行的操作"<<endl;
cin>>dd;
switch(dd){
case 1:{
cout<<"前序遍历"<<endl;
qianxu(tree,n,0);//前序遍历
cout<<endl;
break;
}
case 2:{
cout<<"中序遍历"<<endl;
zhongxu(tree,n,0);//中序遍历
cout<<endl;
break;
}
case 3:{
cout<<"后序遍历"<<endl;
houxu(tree,n,0);//后序遍历
cout<<endl;
break;
}
case 4:{
cout<<"层次遍历"<<endl;
cengci(tree,n);//层次遍历
cout<<endl;
break;
}
case 5:{
cout<<"求树高和结点数"<<endl;
cout<<"树高为"<<depth(n-1)<<endl;//求树高
cout<<"结点数为"<<n-k<<endl;
break;
}
case 6:{
cout<<"请输入要查找的字符，存在则返回该字符的编号，否则返回-1"<<endl;
char as;//查找的字符
cin>>as;
cout<<find(tree,as,n);//查找字符
break;
}
case 0:{
return 0;
break;
}
default:{
cout<<"输入错误，请重新输入"<<endl;
break;
}
}
goto A;
}
danyuan.h文件
#ifndef DANYUAN_H
#define DANYUAN_H
typedef char E;
class danyuan{
private:
E it;
int leftchild;
int rightbro;
public:
void gouzao(E d,int a,int b){
it=d;leftchild=a;rightbro=b;}//构造函数
int releft(){
return leftchild;}//返回左子节点编号
int reright(){
return rightbro;}//返回右兄弟编号
E reit(){
return it;}//返回当前值
};
#endif
danyuan.cpp文件
#include <iostream>
#include "danyuan.h"
using namespace std;
void creatbycc(danyuan tree[],string s,int n){
//通过层次遍历顺序构建树
for(int i=0;i<n;i++){
//建立二叉树
char b=(char)s[i];
if(2*i+1<n){
if(i%2==1&&i+1<n){
tree[i].gouzao(b,2*i+1,i+1);
}else{
tree[i].gouzao(b,2*i+1,-1);
}
}else{
if(i%2==1&&i+1<n){
tree[i].gouzao(b,-1,i+1);
}else{
tree[i].gouzao(b,-1,-1);
}
}
}
tree[-1].gouzao('\0',-1,-1);
}
void cengci(danyuan tree[],int n){
//层次遍历
for(int i=0;i<n;i++){
cout<<tree[i].reit();
}
}
void qianxu(danyuan tree[],int n,int i){
//前序遍历
if(i>n||i==-1){
}else{
cout<<tree[i].reit();
qianxu(tree,n,tree[i].releft());
qianxu(tree,n,tree[i].reright());
}
}
void houxu(danyuan tree[],int n,int i){
//后序遍历
if(i>n||i==-1){
}else{
houxu(tree,n,tree[tree[i].releft()].reright());
houxu(tree,n,tree[i].releft());
cout<<tree[i].reit();
}
}
void zhongxu(danyuan tree[],int n,int i){
//中序遍历
if(i>n||i==-1){
}else{
zhongxu(tree,n,tree[i].releft());
cout<<tree[i].reit();
zhongxu(tree,n,tree[tree[i].releft()].reright());
}
}
int depth(int n){
//求树高
int d=1,c=0;
while(1){
if(c>=n){
return d;
}
if(c==0){
c=2;
}else{
c=c*2+c;
}
d++;
}
}
int find(danyuan tree[],E e,int n){
//查找函数，如果存在则返回编号，否则返回-1
for(int i=0;i<n;i++){
if(tree[i].reit()==e){
return i;
}
}
return -1;
}