层次建树-526互联

function.h

//
// Created by gaogaoaixuexi on 2023/4/2.
//

#ifndef DATASTRUCT_FUNCTION_H
#define DATASTRUCT_FUNCTION_H
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <queue>


//BinaryTree
typedef char TreeElem;
typedef struct BNode{
    TreeElem data;
    struct BNode *rchild;
    struct BNode *lchild;
}BNode, *Tree;

void InitTree(Tree &t);
void PreOrder(Tree t);
void InOrder(Tree t);
void PostOrder(Tree t);
void LevelOrder(Tree t);

//LinkQueue
typedef  BNode* LinkNodeElem;
typedef struct LinkNode{
    LinkNodeElem data;
    LinkNode *next;
}LinkNode;

typedef struct{
    LinkNode *front;
    LinkNode *rear;
}LinkQueue;

void InitQueue(LinkQueue &Q);
void EnQueue(LinkQueue &Q, LinkNodeElem x);
bool DeQueue(LinkQueue &Q, LinkNodeElem &x);
bool IsEmpty(LinkQueue &Q);
bool GetFrontElem(LinkQueue &Q, LinkNodeElem &x);



#endif //DATASTRUCT_FUNCTION_H

queue.h

//
// Created by gaogaoaixuexi on 2023/4/2.
//

#include "function.h"
/**
 * 带有头结点的链队初始化
 * @param Q
 */
void InitQueue(LinkQueue &Q){
    Q.front = (LinkNode *)malloc(sizeof(LinkNode));
    Q.front->next = NULL;
    Q.rear = Q.front;
}
void EnQueue(LinkQueue &Q, LinkNodeElem x){
    LinkNode *s = (LinkNode *)malloc(sizeof (LinkNode));
    s->next = NULL;
    s->data = x;

    Q.rear->next = s;
    Q.rear = s;
}
bool GetFrontElem(LinkQueue &Q, LinkNodeElem &x){
    if (IsEmpty(Q)) return false;
    x = Q.front->next->data;
    return true;
}
bool DeQueue(LinkQueue &Q, LinkNodeElem &x){
    if(Q.front == Q.rear) return false;
    LinkNode *del = Q.front->next;
    x = del->data;
    Q.front->next = del->next;
    if (Q.rear == del){
        Q.rear = Q.front;
    }
    free(del);
}
bool IsEmpty(LinkQueue &Q){
    return Q.front == Q.rear;
}

BinaryTree.h

//
// Created by gaogaoaixuexi on 2023/4/2.
//

#include "function.h"

void InitTree(Tree &t){
    //辅助队列
    LinkQueue q;
    InitQueue(q);
    LinkNodeElem cur;
    char input;
    BNode * bNode;
    while (scanf("%c",&input)){
        if ('\n' != input){
            bNode = (BNode *) calloc(1,sizeof(BNode));
            bNode->data = input;

            EnQueue(q,bNode);

            if (NULL == t){
                t = bNode;
            }else{
                GetFrontElem(q,cur);
                if(cur->lchild == NULL){
                    cur->lchild = bNode;
                }else if (cur->rchild == NULL){
                    cur->rchild = bNode;
                    DeQueue(q,cur);
                }
            }
        }else{
            break;
        }
    }

}
void PreOrder(Tree t){
    if (NULL != t){
        putchar(t->data);
        PreOrder(t->lchild);
        PreOrder(t->rchild);
    }
}
void InOrder(Tree t){
    if (NULL != t){
        InOrder(t->lchild);
        putchar(t->data);
        InOrder(t->rchild);
    }
}
void PostOrder(Tree t){
    if (NULL != t){
        PostOrder(t->lchild);
        PostOrder(t->rchild);
        putchar(t->data);
    }
}
void LevelOrder(Tree t){
    LinkQueue q;
    InitQueue(q);
    EnQueue(q, t);
    LinkNodeElem elem;
    while (!IsEmpty(q)){
        DeQueue(q,elem);
        std::cout<<elem->data;
        if (NULL != elem->lchild){
            EnQueue(q,elem->lchild);
        }
        if (NULL != elem->rchild){
            EnQueue(q,elem->rchild);
        }
    }
}

main.cpp

#include "function.h"
int main(){
    Tree t;
    InitTree(t);
    std::cout<<"PreOrder:"<<std::endl;
    PreOrder(t);
    std::cout<<std::endl;
    std::cout<<"InOrder:"<<std::endl;
    InOrder(t);
    std::cout<<std::endl;
    std::cout<<"PostOrder"<<std::endl;
    PostOrder(t);
    std::cout<<std::endl;
    std::cout<<"LevelOrder"<<std::endl;
    LevelOrder(t);
    return 0;
}

   /**
            a
          b   c
        d  e f




    */