数据结构C++的二叉树，串，队列的一些实现

Wubolun100 · 发表于 2020-11-13 10:05

二叉树：
本人原创，有问题请评论，楼主会随时回来查看修改滴~
觉得有用请点个赞哦~~
本例中，二叉树使用了string形式，当然可以将string改成你想要的数据类型，如int char等，只需要相对应的修改Datatype与各个返回类型就ok啦

[C++] 纯文本查看 复制代码

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];
    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[999];
    string str_z[999];
    for(int i = 0; i<999; i++)
    {
        str_q[i]="";
        str_z[i]="";
    }
    cout<<"请输入一组数据,每个数据之间换行"<<endl;
    cout<<"输入说明：按照先序顺序输入,结点数据为空时输入\"#\",输入\"-1\"结束"<<endl;
    for(int i = 0; i<999; i++)
    {
        cin>>str_q[i];
        if(str_q[i]=="-1")
            break;
//       len++;
    }
//    cout<<"本组为第二组：二叉树的中序排列,输入\"-1\"结束"<<endl;
//    for(int i = 0; i<999; i++)
//    {
//        cin>>str_z[i];
//        if(str_z[i]=="-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
*/

本人原创，有问题请评论，楼主会随时回来查看修改滴~
觉得有用请点个赞哦~~

[C++] 纯文本查看 复制代码

/**
串初始化 
创建 
判空 
判满 
求串长 
串复制 
串比较 
串连接 
串模式匹配 
串输出
*/
#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[length]!='\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[i]=str[i];
    }
    S->data[len]='\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[i]=str[i];
    }
    S->data[length]='\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[i]>S2->data[i])
            return 1;
        else if(S1->data[i]<S2->data[i])
            return -1;
        else if (S1->data[i]=='\0' && S1->data[i]==S2->data[i])
            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[len1+i]=S2->data[i];
    }
    S1->data[len1+len2]='\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[i+j]!=str[j])
                break;
        }
        if(j==len)
            return i;
    }
    return -1;
}
void outPutString(String *S)//串输出
{
    int i;
    for (i=0; i<S->length; i++)
        cout<<S->data[i];
}

int main()
{
    int flag =0;
    String str1,str2,str3,str4,str5;
     initString(&str1,"");
      initString(&str2,"");
    char ch[999];
    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、顺序队

/**2020.04:queue顺序结构-循环队列判空判满求长度入队出队获取队头获取队尾

[C++] 纯文本查看 复制代码

*/
#include<bits/stdc++.h>
using namespace std;
#define QUEUESIZE 100
typedef int DataType;
typedef struct SeqQueue
{
    DataType data[QUEUESIZE];
    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[q->front];//返回队头
    return temp;
}
DataType getTail(SeqQueue *q)//return tail
{
    DataType temp;
    if(queueEmpty(q))
    {
        return -1;
    }
    temp = q->data[q->rear-1];//返回队尾
    return temp;
}
DataType deQueue(SeqQueue *q)//出队
{
    DataType temp;
    if(queueEmpty(q))
        return -1;
    temp = q->data[q->front];
    q->front = (q->front+1) % QUEUESIZE;//形成循环序列，几何上相当于front--
    return temp;
}
bool enQueue(SeqQueue *q,DataType e)//入队
{
    if(queueFull(q))
        return false;
    q->data[q->rear]=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、链式队

[C++] 纯文本查看 复制代码

/**
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

ma4out7 · 发表于 2020-11-14 23:09

可以，学到了

wuai_leader · 发表于 2020-11-13 11:33

可以，学习了

lm877966 · 发表于 2020-11-13 11:41

正愁找不到好的呢，收藏了。

304775988 · 发表于 2020-11-13 19:43

很强大,收藏学习

xiaoyudian · 发表于 2020-11-13 23:19

非常好的东西

Wubolun100 · 发表于 2020-11-15 11:27

Ceffka 发表于 2020-11-13 11:29
为啥不用模板呢，为啥不用stl呢？

stl固然效率方便，但其中的原理只有自己实现一遍才能体会到

Wubolun100 · 发表于 2020-11-15 11:31

注：保证100%亲自手打，这是我之前学数据结构写的实现，知乎的相同文章也是本人原创，不是转载自知乎。

zorion · 发表于 2020-11-16 09:22

感谢分享感谢分享

帐号		自动登录	找回密码
密码			注册[Register]

[C&C++ 原创] 数据结构C++的二叉树，串，队列的一些实现

免费评分