数据结构C++的二叉树，串，队列的一些实现
二叉树：本人原创，有问题请评论，楼主会随时回来查看修改滴~
觉得有用请点个赞哦~~
本例中，二叉树使用了string形式，当然可以将string改成你想要的数据类型，如int char等，只需要相对应的修改Datatype与各个返回类型就ok啦
2020.04二叉树链表
初始化
判空
创建
递归先序遍历
递归中序遍历
递归后续遍历
队列层次遍历
查找任意节点
查找最左节点
查找最右节点
*/
#include<bits/stdc++.h>
using namespace std;
typedef string Datatype;
typedef struct BNode
{
Datatype data;
BNode *lchild;
BNode *rchild;
} BNode,*BTree;
//chushihua
void InitBTree(BTree &bt)
{
bt=NULL;
}
int BTreeEmpty(BTree &bt)//empty return 1
{
if(bt==NULL)
{
return 1;
}
else
{
return 0;
}
}
int create_tree_flag = 0;
//递归创建
void Create(BTree &bt, string str[])
{
string s;
s= str;
create_tree_flag++;
if (s == "#")
{
bt = NULL;
}
else
{
bt = new BNode;
bt->data = s;
Create(bt->lchild, str);
Create(bt->rchild, str);
}
}
//先序
void Pre_Order(BTree bt)
{
if (bt!=NULL)
{
cout << bt->data<<" ";
Pre_Order(bt->lchild);
Pre_Order(bt->rchild);
}
}
//中序
void In_Order(BTree bt)
{
if (bt!=NULL)
{
In_Order(bt->lchild);
cout << bt->data<<" ";
In_Order(bt->rchild);
}
}
//后序
void Post_Order(BTree bt)
{
if (bt!=NULL)
{
Post_Order(bt->lchild);
Post_Order(bt->rchild);
cout << bt->data<<" ";
}
}
//层次遍历
void level_Order(BTree bt)
{
queue<BTree> q;
if (bt != NULL)
{
q.push(bt); //根节点指针进队列
}
while (q.empty()!= true)
{
bt=q.front();
q.pop();
cout<<bt->data<<" ";//输出节点的data值
if (bt->lchild != NULL)
{
q.push(bt->lchild);
}
if (bt->rchild != NULL) //右孩子进队
{
q.push(bt->rchild);
}
}
}
string Search_left(BTree bt)
{
string s;
if(bt->lchild!=NULL)
s=Search_left(bt->lchild);
else
s=bt->data;
return s;
}
string Search_right(BTree bt)
{
string s;
if(bt->rchild!=NULL)
s=Search_right(bt->rchild);
else
s=bt->data;
return s;
}
int In_flag = 0;
bool In_Tree(BTree bt,string s)
{
if (bt!=NULL)
{
if(s.compare(bt->data)==0)//相同
{
In_flag=1;
}
In_Tree(bt->lchild,s);
In_Tree(bt->rchild,s);
}
}
int main()
{
int len=0;
BTree bt;
cout<<"1--初始化"<<endl;
InitBTree(bt);
cout<<"初始化完毕"<<endl;
cout<<"2--创建"<<endl;
string str_q;
string str_z;
for(int i = 0; i<999; i++)
{
str_q="";
str_z="";
}
cout<<"请输入一组数据,每个数据之间换行"<<endl;
cout<<"输入说明：按照先序顺序输入,结点数据为空时输入\"#\",输入\"-1\"结束"<<endl;
for(int i = 0; i<999; i++)
{
cin>>str_q;
if(str_q=="-1")
break;
// len++;
}
// cout<<"本组为第二组：二叉树的中序排列,输入\"-1\"结束"<<endl;
// for(int i = 0; i<999; i++)
// {
// cin>>str_z;
// if(str_z=="-1")
// break;
// }
Create(bt,str_q);
cout<<"创建成功，正在判空"<<endl;
if(BTreeEmpty(bt)!=1)
cout<<"不为空"<<endl;
else
cout<<"为空"<<endl;
cout<<"3--先序遍历"<<endl;
Pre_Order(bt);
cout<<endl;
cout<<"4--中序遍历"<<endl;
In_Order(bt);
cout<<endl;
cout<<"5--后续遍历"<<endl;
Post_Order(bt);
cout<<endl;
cout<<"6--层次遍历"<<endl;
level_Order(bt);
cout<<endl;
cout<<"7--查找最左"<<endl;
string temp =Search_left(bt);
cout<<temp;
cout<<endl;
cout<<"8--查找最右"<<endl;
temp =Search_right(bt);
cout<<temp;
cout<<endl;
cout<<"9--查找元素是否在树,请输入一个元素 ";
string str_temp;
cin>>str_temp;
In_Tree(bt,str_temp);
if(In_flag==1)
{
cout<<"元素在树中"<<endl;
}
else
{
cout<<"元素不在树中"<<endl;
}
cout<<"程序结束"<<endl;
}
/**
test data
1.A B D # # E # # C F # # G # # -1
2.生物 动物 脊椎 # # 无脊椎 # # 植物 有种子 # # 无种子 # # -1
3.A1 A2 A4 # # # A3 A6 # # # -1
*/
本人原创，有问题请评论，楼主会随时回来查看修改滴~
觉得有用请点个赞哦~~https://pic3.zhimg.com/80/v2-b8f9e2b71eaac6991c6bd1ea9dd374c6_720w.jpg
/**
串初始化
创建
判空
判满
求串长
串复制
串比较
串连接
串模式匹配
串输出
*/
#include<bits/stdc++.h>
using namespace std;
typedef struct String
{
char* data;
int length;
int maxLength;
} String;
int Length(char* str)
{
int length=0;
while(str!='\0')
length++;
return length;
}
int getStringLength(String *S)//求串长
{
return S->length;
}
void initString(String *S,char *str)//初始化，创建
{
int len = Length(str);
S->data = (char*)malloc((len+1)*sizeof(char));
S->length=len;
S->maxLength =len;
for(int i = 0 ; i<len ; i++)
{
S->data=str;
}
S->data='\0';
}
void destroyString(String *S)
{
if(S->data == NULL )
{
return ;
}
free(S->data);
S->data = NULL;
S->length = 0;
S->maxLength=0;
}
void clearString(String *S)
{
if(S->data == NULL)
{
return ;
}
S->length = 0;
}
bool stringEmpty(String *S)//判空
{
return S->data != NULL && S->length ==0;
} //data指向一个空间，同时有效字符为0，说明字符串为空
bool stringFull(String *S)//判满
{
return S->length ==S->maxLength;
}
void copyString(String *S,char *str)//串复制
{
if(S->data == NULL)
return ;
int length = Length(str);
if(length > S->maxLength)
{
S->data = (char*)realloc(S->data,(length+1)*sizeof(char));
S->maxLength = length;
}
for(int i = 0; i<length; i++)
{
S->data=str;
}
S->data='\0';
S->length = length;//修改长度
}
int compareString(String *S1,String *S2)//串比较
{
//compare>0:S1>S2; <0:S1<S2; =0:S1==S2
if(S1->data == NULL&&S2->data==NULL)
return 0;
if(S1->data == NULL&&S2->data!=NULL)
return -1;
if(S1->data != NULL&&S2->data==NULL)
return 1;
if(S1->length==0)
return (S2->length==0)?0:-1;//为0则返回0,不为0返回-1
if(S2->length==0)
return (S1->length==0)?0:1;//为0则返回0,不为0返回1
int i = 0;
while(true)
{
if(S1->data>S2->data)
return 1;
else if(S1->data<S2->data)
return -1;
else if (S1->data=='\0' && S1->data==S2->data)
return 0;
i++;
}
}
void concatString (String *S1,String *S2)//拼接
{
if(S1->data ==NULL ||S2->data==NULL)
return ;
int len1 = Length(S1->data);
int len2 = Length(S2->data);
if(S1->maxLength<len1+len2)
{
S1->data = (char*)realloc(S1->data,(len1+len2+1)*sizeof(char));//空间调整为a+b+1个，a为s1个数，b为s2个数，再加上\0
S1->maxLength = len1+len2;
}
for(int i = 0; i<len2; i++)
{
S1->data=S2->data;
}
S1->data='\0';
S1->length = len1+len2;
}
int locate(String *S,char *str,int pos)//串匹配
{
if(S->data==NULL)
return -1;
if(pos<0||pos>=S->length)
return -1;
int len = Length(str);
if(len+pos>S->length)
return -1;
for(int i = pos; i<=S->length - len ; i ++)
{
int j;
for(j = 0 ; j<len; j++)
{
if(S->data!=str)
break;
}
if(j==len)
return i;
}
return -1;
}
void outPutString(String *S)//串输出
{
int i;
for (i=0; i<S->length; i++)
cout<<S->data;
}
int main()
{
int flag =0;
String str1,str2,str3,str4,str5;
initString(&str1,"");
initString(&str2,"");
char ch;
int i=0,p=-1;
while(true)
{
if(i%10==0)
{
if(i!=0)
system("pause") ;
system("cls");
cout<<"============请操控程序============="<<endl;
cout<<"==================================="<<endl;
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<<"===========9 串输出 =========="<<endl;
cout<<"===========10 程序结束 =========="<<endl;
cout<<"==================================="<<endl;
}
i++;
cout<<endl;
cout<<"请输入您的第 "<<i<<" 次操作：";
cin>>p;
if(p>11||p<1)
{
cout<<"无法执行，请检查输入是否错误"<<endl;
continue;
}
switch(p)
{
case 1:
{
if(flag == 1)
{
cout<<"您已经创建过了"<<endl;
break;
}
cout<<"请输入一些字符，分别创建2组字符串"<<endl;
cout<<"两组字符串的顺序为str1,str2"<<endl;
cout<<"str1 功能：主要操作的串"<<endl;
cout<<"str2 功能：为str1执行比较 拼接操作"<<endl;
cout<<"str1:";
scanf("%s",ch);
initString(&str1,ch);
cout<<"\nstr2:";
scanf("%s",ch);
initString(&str2,ch);
cout<<"串已经创建完毕"<<endl;
break;
flag =1;
}
case 2:
{
cout<<"正在主串判空..."<<endl;
if(stringEmpty(&str1))
cout<<"判空结果：空"<<endl;
else
cout<<"判空结果：非空"<<endl;
break;
}
case 3:
{
cout<<"正在主串判满..."<<endl;
if(stringFull(&str1))
cout<<"判空结果：满"<<endl;
else
cout<<"判空结果：非满"<<endl;
break;
}
case 4:
{
cout<<"正在主串求长..."<<endl;
cout<<"求长结果，长度为："<<getStringLength(&str1)<<endl;
break;
}
case 5:
{
cout<<"正在执行串复制,请输入一组字符"<<endl;
scanf("%s",ch);
copyString(&str1,ch);
cout<<"串复制结束"<<endl;
break;
}
case 6:
{
cout<<"正在进行str1和str2比较\n结果为："<<endl;
int temp = compareString(&str1,&str2);
// cout<<temp;
if(temp>0)
cout<<"str1 > str2"<<endl;
if(temp==0)
cout<<"str1 = str2"<<endl;
if(temp<0)
cout<<"str1 < str2"<<endl;
break;
}
case 7:
{
cout<<"正在进行str1和str2拼接"<<endl;
concatString(&str1,&str2);
cout<<"拼接成功"<<endl;
break;
}
case 8:
{
cout<<"正在执行串匹配,请输入一组字符"<<endl;
scanf("%s",ch);
cout<<"请输入起始位置"<<endl;
int pos;
cin>>pos;
int loc = locate(&str1,ch,pos);
if(loc!=-1)
cout<<"串匹配结束，匹配位置为"<<loc<<endl;
else
cout<<"匹配失败，请检查输入是否错误！"<<endl;
break;
}
case 9:
{
cout<<"正在执行串输出"<<endl;
cout<<"str1:";
outPutString(&str1);
cout<<"\nstr2:";
outPutString(&str2);
cout<<endl;
cout<<"串输出成功，请执行输出以检查"<<endl;
break;
}
case 10:
{
cout<<"您已经退出，程序结束"<<endl;
return 0;
break;
}
}
}
}
队列
本人原创，有问题请评论，楼主会随时回来查看修改滴~
觉得有用请点个赞哦~~
1、顺序队https://pic4.zhimg.com/80/v2-d6e49d64c3a50514effb1982eefa64fb_720w.jpg
/**2020.04:queue顺序结构-循环队列判空 判满 求长度 入队 出队 获取队头获取队尾*/
#include<bits/stdc++.h>
using namespace std;
#define QUEUESIZE 100
typedef int DataType;
typedef struct SeqQueue
{
DataType data;
int front;
int rear;
} SeqQueue;
void initQueue(SeqQueue *q)//初始化queue
{
q->front = 0;//前部
q->rear = 0;//尾部
}
void clearQueue(SeqQueue *q)//清空queue
{
q->front = 0;
q->rear = 0;
}
bool queueEmpty(SeqQueue *q)//isEmpty?
{
return q->front == q->rear;
}
bool queueFull(SeqQueue *q)//isFull?
{
return q->front == (q->rear+1)%QUEUESIZE;
}
DataType getHead(SeqQueue *q)//return Head
{
DataType temp;
if(queueEmpty(q))
{
return -1;
}
temp = q->data;//返回队头
return temp;
}
DataType getTail(SeqQueue *q)//return tail
{
DataType temp;
if(queueEmpty(q))
{
return -1;
}
temp = q->data;//返回队尾
return temp;
}
DataType deQueue(SeqQueue *q)//出队
{
DataType temp;
if(queueEmpty(q))
return -1;
temp = q->data;
q->front = (q->front+1) % QUEUESIZE;//形成循环序列，几何上相当于front--
return temp;
}
bool enQueue(SeqQueue *q,DataType e)//入队
{
if(queueFull(q))
return false;
q->data=e;
q->rear=(q->rear+1)%QUEUESIZE;//形成循环序列，几何上相当于rear++
return true;
}
int queueLength(SeqQueue *q)
{
return (q->rear - q->front + QUEUESIZE) %QUEUESIZE;//等同于QUEUESIZE-|front-rear|
}
int Random_number()//随机产生0~222整数
{
return rand()%222;
}
int main()
{
srand(time(NULL)); //根据电脑时间，生成随机种子
SeqQueue sq;
cout<<"1--程序正在执行队列初始化...."<<endl;
initQueue(&sq);
cout<<" 初始化成功,正在入队20个随机元素"<<endl;
cout<<" 入队顺序：";
for(int i = 1; i<21; i++)
{
int temp_num=Random_number();
printf("%5d",temp_num);
enQueue(&sq,temp_num);
if(i%10==0)
cout<<endl<<" ";
}
cout<<endl<<" 20个元素已成功入队!"<<endl<<endl;
cout<<"2--程序正在执行入队....请输入一个正整数元素：";
int temp_en;
cin>>temp_en;
if(enQueue(&sq,temp_en))
cout<<" 入队成功!"<<endl<<endl;
else
cout<<" 入队失败!"<<endl<<endl;
cout<<"3--程序正在判空...."<<endl;
if(queueEmpty(&sq))
cout<<" queue is empty"<<endl<<endl;
else
cout<<" queue is not empty"<<endl<<endl;
cout<<"4--程序正在判满...."<<endl;
if(queueEmpty(&sq))
cout<<" queue is full"<<endl<<endl;
else
cout<<" queue is not full"<<endl<<endl;
cout<<"5--程序正在获取长度...."<<endl;
cout<<" 获取长度为："<<queueLength(&sq)<<endl<<endl;
cout<<"6--程序正在执行出队...."<<endl;
int temp_de=deQueue(&sq);
if(temp_de!=-1)
cout<<" 出队元素为："<<temp_de<<endl<<endl;
else
cout<<" 入队失败!"<<endl<<endl;
cout<<"7--程序正在获取长度...."<<endl;
cout<<" 获取长度为："<<queueLength(&sq)<<endl<<endl;
cout<<"8--程序正在获得队头元素...."<<endl;
int temp_gh=getHead(&sq);
if(temp_gh!=-1)
cout<<" 队头元素为："<<temp_gh<<endl<<endl;
else
cout<<" 获取失败!"<<endl<<endl;
cout<<"9--程序正在获得队尾元素...."<<endl;
int temp_gt=getTail(&sq);
if(temp_gt!=-1)
cout<<" 队尾元素为："<<temp_gt<<endl<<endl;
else
cout<<" 获取失败!"<<endl<<endl;
}
2、链式队https://pic1.zhimg.com/80/v2-0d49de37a48f210f30250b022ce2342c_720w.jpg
/**
2020.04:queue
链式结构-队列
判空
求长度
入队
出队
获取队头
获取队尾
*/
#include<bits/stdc++.h>
using namespace std;
typedef int DataType;
typedef struct QNode
{
DataType data;
struct QNode *next;
} QNode;
typedef struct LinkQueue
{
QNode *front,*rear;
int count;
} LinkQueue;
bool queueEmpty(LinkQueue *q) //isEmpty?
{
return q->front == NULL; //队头为空?
}
void clearQueue(LinkQueue *q) //清空queue
{
QNode *p = q->front;
while(p) //p不为空时
{
QNode *p1 = p;//定义p1,让其指向p当前指向的结点
p=p->next; //p指向下一个结点
free(p1); //释放掉p1指向的结点
}
}
void initQueue(LinkQueue *q) //初始化queue
{
if(queueEmpty(q)==false) //防止初始化一个已经有结点的队列，产生崩溃
clearQueue(q);
else
{
q->front = NULL;
q->rear = NULL;
q->count = 0;
}
}
DataType getHead(LinkQueue *q)//return Head
{
DataType temp;
if(queueEmpty(q))
{
return -1;
}
temp = q->front->data;
return temp;
}
DataType getTail(LinkQueue *q)//return tail
{
DataType temp;
if(queueEmpty(q))
{
return -1;
}
temp = q->rear->data; //返回队尾
return temp;
}
DataType deQueue(LinkQueue *q)//出队
{
DataType temp;
if(queueEmpty(q))
return -1;
QNode *p = q->front; //队头元素
temp = q->front->data;//获取数据
q->front=q->front->next;//队头后u移
free(p);
q->count--; //长度-1
return temp;
}
bool enQueue(LinkQueue *q,DataType e)//入队
{
QNode *p = new QNode;
p->data = e;
p->next = NULL;
if(queueEmpty(q))
{
q->front = p; //令头尾都指向p
q->rear = p;
}
else
{
q->rear->next=p; //尾结点指向p，之后p为队尾结点
q->rear=p; //q->rear为flag，为p结点
}
q->count++;
return true;
}
int queueLength(LinkQueue *q)
{
return q->count;
}
int Random_number() //随机产生0~222整数
{
return rand()%222;
}
int main()
{
srand(time(NULL)); //根据电脑时间，生成随机种子
LinkQueue lq;
lq.front=NULL;//指向空，防止初始化中，判空时对野指针操作(free(p1);语句处)
cout<<"1--程序正在执行队列初始化...."<<endl;
initQueue(&lq);
cout<<" 初始化成功,正在入队20个随机元素"<<endl;
cout<<" 入队顺序：";
for(int i = 1; i<21; i++)
{
int temp_num=Random_number();
if(i!=20)
printf("%5d ->",temp_num);
else
printf("%5d ",temp_num);
enQueue(&lq,temp_num);
if(i%10==0)
cout<<endl<<" ";
}
cout<<endl<<" 20个元素已成功入队!"<<endl<<endl;
cout<<"2--程序正在执行入队....请输入一个正整数元素：";
int temp_en;
cin>>temp_en;
if(enQueue(&lq,temp_en))
cout<<" 入队成功!"<<endl<<endl;
else
cout<<" 入队失败!"<<endl<<endl;
cout<<"3--程序正在判空...."<<endl;
if(queueEmpty(&lq))
cout<<" queue is empty"<<endl<<endl;
else
cout<<" queue is not empty"<<endl<<endl;
cout<<"4--程序正在获取长度...."<<endl;
cout<<" 获取长度为："<<queueLength(&lq)<<endl<<endl;
cout<<"5--程序正在执行出队...."<<endl;
int temp_de=deQueue(&lq);
if(temp_de!=-1)
cout<<" 出队元素为："<<temp_de<<endl<<endl;
else
cout<<" 入队失败!"<<endl<<endl;
cout<<"6--程序正在获取长度...."<<endl;
cout<<" 获取长度为："<<queueLength(&lq)<<endl<<endl;
cout<<"7--程序正在获得队头元素...."<<endl;
int temp_gh=getHead(&lq);
if(temp_gh!=-1)
cout<<" 队头元素为："<<temp_gh<<endl<<endl;
else
cout<<" 获取失败!"<<endl<<endl;
cout<<"8--程序正在获得队尾元素...."<<endl;
int temp_gt=getTail(&lq);
if(temp_gt!=-1)
cout<<" 队尾元素为："<<temp_gt<<endl<<endl;
else
cout<<" 获取失败!"<<endl<<endl;
}复杂度分析
时间复杂度： （注：单个元素操作）
循环顺序队入队O(1) 循环顺序队出队O(1)
链式队入队O(1)链式队出队O(1)
获取顶端元素O(1)判满/空O(1)
空间复杂度：
循环顺序队入队O(1) 循环顺序队出队O(1)
链式队入队O(1)链式队出队O(1)
获取顶端元素O(1)判满/空O(1
可以，学到了 可以，学习了 正愁找不到好的呢，收藏了。 很强大,收藏学习 非常好的东西 Ceffka 发表于 2020-11-13 11:29
为啥不用模板呢，为啥不用stl呢？
stl固然效率方便，但其中的原理只有自己实现一遍才能体会到 注：保证100%亲自手打，这是我之前学数据结构写的实现，知乎的相同文章也是本人原创，不是转载自知乎。
感谢分享感谢分享
页:
[1]