基本数据结构简单实现(cpp)

按理说应该用面向对象的方式实现封装，但迫于c++功底并不扎实，就用结构体结合c++的模板函数结合教材和王道复习书来实现吧，方便随时翻看。

线性表

顺序表—SeqList.h

//
// Created by knight1527 on 2022/6/21.
//

#ifndef DATASTRUCTURELIB_SEQLIST_H
#define DATASTRUCTURELIB_SEQLIST_H

#include <cstdlib>
#define InitSize 10
template <typename T>
struct SeqList{
    T* data;
    int MAXSIZE;
    int length;
};

template <typename T>
void initSeqList(SeqList<T> &L){
    L.data = (T*)malloc(sizeof(T) * InitSize);
    L.length = 0;
    L.MAXSIZE = InitSize;
}
template <typename T>
void increaseSize(SeqList<T> &L, int len){
    T* tep = L.data;
    L.data = (T*)malloc(sizeof(T) * (L.MAXSIZE + len));
    for (int i = 0; i < L.length; i++){
        L.data[i] = tep[i];
    }
    L.MAXSIZE += len;
    free(tep);
}
template <typename T>
bool seqListInsert(SeqList<T> &L, int i, T e){
    if(i < 1 || i > L.length + 1)
        return false;
    if(L.length >= L.MAXSIZE){
        //表长达到最大长度，增加空间
        increaseSize(L, InitSize);
    }
    for (int j = L.length; j >= i ; --j) {
        L.data[j] = L.data[j-1];
    }
    L.data[i - 1] = e;
    L.length++;
    return true;
}
template <typename T>
bool seqListDelete(SeqList<T> &L, int i, T &e){
    if(i < 1 || i > L.length + 1)
        return false;
    e = L.data[i-1];
    for (int j = i; j < L.length ; j++) {
        L.data[j-1] = L.data[j];
    }
    L.length--;
    return true;
}
#endif //DATASTRUCTURELIB_SEQLIST_H

单链表—LinkList.h

//
// Created by knight1527 on 2022/6/26.
//

#ifndef DATASTRUCTURELIB_LINKLIST_H
#define DATASTRUCTURELIB_LINKLIST_H

#include <cstdlib>
#include <iostream>

using namespace std;

template <typename T>
struct LNode{
    T data;
    struct LNode<T> *next;
};
template <typename T>
using LinkList = LNode<T> *;

template <typename T>
bool initLinkList(LinkList<T> &L){
    L = (LNode<T> *)malloc(sizeof(LNode<T>));
    if (L == nullptr)
        return false;
    L->next = nullptr;
    return true;
}

template <typename T>
bool linkListInsert(LinkList<T> &L, int i, T e) {
    if (i < 1){
        cout << "请用1序!" << endl;
        return false;
    }
    LNode<T> *p = linkListGetEle(L, i - 1);

    return linkListInsertNext(p, e);
}
template <typename T>
bool linkListInsertNext(LNode<T> *p, T e){ //后插
    if(p == nullptr)
        return false;
    auto *s = (LNode<T> *)malloc(sizeof(LNode<T>));
    s->data = e;
    s->next = p->next;
    p->next = s;
    return true;
}
template <typename T>
bool linkListInsertPre(LNode<T> *p, T e){ //前插(交换值)
    if(p == nullptr)
        return false;
    auto *s = (LNode<T> *)malloc(sizeof(LNode<T>));
    s->next = p->next;
    p->next = s;
    s->data = p->data;
    p->data = e;
    return true;
}
template <typename T>
bool linkListDelete(LinkList<T> &L, int i, T re){
    if(i < 1)
        return false;

    LNode<T> *p = linkListGetEle(L, i - 1);

    if(p == nullptr)
        return false; //i值不合法
    if(p->next == nullptr)//i-1 后没有节点
        return false;
    LNode<T> *q = p->next;
    re = q->data;
    p->next = q->next;
    free(q);
    return true;
}
template <typename T>
bool linkListDeleteNode(LNode<T> *p){ //删除指定节点
    if(p == nullptr)
        return false;
    LNode<T> *q = p->next;
    if(p->next == nullptr){
        std::cout<<"Cannot delete the last node, please change the function!"<<std::endl;
        return false;
    }
    p->data = p->next->data;
    p->next = q->next;
    free(q);
    return true;
}
template <typename T>
LNode<T> * linkListGetEle(LinkList<T> L, int i){
    if(i < 0)
        return nullptr;
    LNode<T> *p;
    int j = 0;//p指向的节点位置
    p = L;
    while (p != nullptr && j < i){
        p = p->next;
        j++;
    }
    return p;
}
template <typename T>
int length(LinkList<T> L){
    int len = 0;
    LNode<T> *p = L;
    while (p->next != nullptr){
        p = p->next;
        len++;
    }
    return len;
}
template <typename T>
void print(LinkList<T> &L){
    LinkList<int> p = L->next;
    cout<<"List : "<<endl;
    while(p != nullptr){
        cout<<p->data<<endl;
        p = p->next;
    }
}


//**************************作业***********************************//
/**
 * 递归删除值为x的节点
 * @param x
 * @param l
 */
void delete_revision(int x, LinkList<int> &l) {
    LinkList<int> p = l;
    LinkList<int> q;
    LinkList<int> tep = p->next;
    if (tep == nullptr)
        return;
    if (tep->data == x){
        q = tep;
        p->next = tep->next;
        free(q);
        delete_revision(x, p);
    } else{
        delete_revision(x, p->next);
    }
}
/**
 * 反向输出单链表
 * @param L
 */
void print_reverse(LinkList<int> &L){
    LinkList<int> p = L->next;
    if(p->next != nullptr){
        print_reverse(p);
    }
    cout<<p->data<<endl;
}
/**
 * 删除最小值
 * @param L
 */
void delete_minVal(LinkList<int> &L){
    LinkList<int> p = L->next, minp = L->next, pre = L;
    while(p->next != nullptr){
        if(p->next->data < p->data){
            pre = p;
            minp = p->next;
        }
        p = p->next;
    }
    cout<<"Deleted Min Val:"<<minp->data<<endl;
    pre->next = minp->next;
    free(minp);
}
/**
 * 空间复杂度O(1)的逆置
 * @param L
 */
void reverse(LinkList<int> &L){
    LinkList<int> p = L->next;
    L->next = nullptr;
    while(p != nullptr){
        LinkList<int> node = p;
        p = p->next; //注意先让p指向下一节点再操作node，他们目前指向同一块地址
        node->next = L->next;
        L->next = node;
    }
}
/**
 * 排序单链表O(n^2)，也可以把数据拿出来排好再插入，以空间换时间
 * @param L
 */
void sort(LinkList<int> &L){
    LinkList<int> p = L->next;
    L->next = nullptr;
    while(p != nullptr){
        LinkList<int> node = p, head = L;
        p = p->next;
        //注意这儿条件，刚开始用的||
        while(head->next != nullptr && head->next->data <= node->data){
            head = head->next;
        }
        node->next = head->next;
        head->next = node;
    }
}
/**
 * 删除指定大小范围的节点
 * @param L
 * @param l
 * @param r
 */
void delete_byrange(LinkList<int> &L, int l, int r){
    LinkList<int> p = L, node;
    while(p->next != nullptr){
        if(p->next->data > l && p->next->data < r){
            node = p->next;
            p->next = p->next->next;
            free(node);
        }
        p = p->next;
    }
}
/**
 * 找到两个链表的公共节点，注意：当两个链表有公共节点时，它们从公共节点开始都是重合的
 * 时间复杂度：O(len1 + len2)
 * @param L1
 * @param L2
 */
LinkList<int> find_sameNode(LinkList<int> &L1, LinkList<int> &L2){
    int len1 = length(L1), len2 = length(L2);
    int dist = abs(len1 - len2);
    LinkList<int> longList, shortList;
    longList = len1<len2?L2->next:L1->next;
    shortList = len1<len2?L1->next:L2->next;
    while(dist--)
        longList = longList->next;
    while(longList != nullptr) {
        if (longList == shortList){
            return longList;
        }else{
            longList = longList->next;
            shortList = shortList->next;
        }
    }
    return nullptr;
}
/**
 * 递增输出并删除节点
 * @param L
 */
void print_increasing(LinkList<int> &L){
    sort(L);
    cout<<"List(increasing) : "<<endl;
    while (L->next != nullptr){
        cout<<L->next->data<<endl;
        LinkList<int> node = L->next;
        L->next = L->next->next;
        free(node);
    }
    if(L->next == nullptr){
        cout<<"Successfully delete!"<<endl;
    }
}
/**
 * 分解：序号奇数在A，偶数在B
 * @param L
 * @return
 */
LinkList<int> decomposition(LinkList<int> &A){
    LinkList<int> p = A->next, q, q2;
    auto B = (LNode<int> *)malloc(sizeof(LNode<int>));
    q = B, q2 = A;
    int index = 1;
    while (p != nullptr){
        LinkList<int> node = p;
        p = p->next;    //先将p指向下一节点，不然node将其next指向null就找不到下一个节点了
        node->next = nullptr;
        if(index % 2 == 1){
            q2->next = node;
            q2 = q2->next;
        }else{
            q->next = node;
            q = q->next;
        }
        index++;
    }
    return B;
}
/**
 * 归并两个递增的链表，不额外开辟链表空间，要求结果降序,(头插法)T(n) = O(len1 + len2)
 * @param L1
 * @param L2
 */
void merge_orderlyList(LinkList<int> &L1, LinkList<int> &L2){
    LinkList<int> p1 = L1->next, p2 = L2->next, tep;
    L1->next = nullptr;
    while(p1 && p2){
        if(p1->data < p2->data){
            tep = p1;
            p1 = p1->next;
            tep->next = L1->next;
            L1->next = tep;
        }else{
            tep = p2;
            p2 = p2->next;
            tep->next = L1->next;
            L1->next = tep;
        }
    }
    p1 = p1==nullptr?p2:p1;
    while(p1 != nullptr){
        tep = p1;
        p1 = p1->next;
        tep->next = L1->next;
        L1->next = tep;
    }
}
/**
 * 判断l2是否l1的连续子序列
 * @param L1
 * @param L2
 * @return
 */
bool subsequence(LinkList<int> &L1, LinkList<int> &L2){
    LNode<int> *pre = L1->next, *p = L1->next, *q = L2->next;
    while(p && q){
        if(p->data == q->data){
            p = p->next;
            q = q->next;
        }else{
            pre = pre->next;
            p = pre;
            q = L2->next;
        }
    }
    return q == nullptr;
}

#endif //DATASTRUCTURELIB_LINKLIST_H

双向链表—DLinkList.h

//
// Created by knight1527 on 2022/6/28.
//

#ifndef DATASTRUCTURELIB_DLINKLIST_H
#define DATASTRUCTURELIB_DLINKLIST_H
#include <cstdlib>
#include <iostream>

template <typename T>
struct DNode{
    T data;
    struct DNode<T> *prior, *next;
};
template <typename T>
using DLinkList = DNode<T> *;

template <typename T>
bool initDLinkList(DLinkList<T> &L){
    L = (DNode<T> *)malloc(sizeof(DNode<T>));
    if (L == nullptr)
        return false;
    L->prior = L;
    L->next = L;
    return true;
}
template <typename T>
bool Empty(DLinkList<T> &L){
    return L->next == nullptr;
}
template <typename T>
bool insertNextDNode(DNode<T> *p, DNode<T> *s){ //将s节点插入到p之后
    s->next = p->next;
    if(p->next != nullptr)
        p->next->prior = s;
    s->prior = p;
    p->next = s;
}
template <typename T>
bool insertNextDNode(DNode<T> *L, T e){
    DNode<int> *p = L;
    auto *s = (DNode<T> *)malloc(sizeof (DNode<T>));
    s->data = e;
    s->next = p->next;
    if(p->next != nullptr)
        p->next->prior = s;
    s->prior = p;
    p->next = s;
    return true;
}
template <typename T>
bool deleteNextDNode(DNode<T> *p){//删除p节点的后继节点
    DNode<T> *q = p->next;
    if(q == nullptr)
        return false;
    p->next = q->next;
    if(q->next != nullptr)
        q->next->prior = p;
    free(q);
    return true;
}
template <typename T>
void destroyDLinkList(DLinkList<T> &L){
    while(L->next != nullptr)
        deleteNextDNode(L);
    free(L);
    L = nullptr;
}
template <typename T>
void print(DLinkList<T> &L){
    if(L == nullptr || L->next == nullptr){
        cout<<"null"<<endl;
        return;
    }
    DNode<int> *p = L->next;
    cout<<"DList: "<<endl;
    while(p != L){
        cout<<p->data<<endl;
        p = p->next;
    }
}
template <typename T>
int length(DLinkList<T> &L){
    if(L == nullptr || L->next == nullptr){
        cout<<"null"<<endl;
        return -1;
    }
    cout<<"debug"<<endl;
    int rel = 0;
    DNode<int> *p = L->next;
    while(p != L){
        rel++;
        p = p->next;
    }
    return rel;
}
//*******************************练习***********************************//
/**
 * 判断双线链表是否对称
 * @param L
 * @return
 */
bool judge_symmetry(DLinkList<int> &L){
    DNode<int> *p = L->next, *q = L->prior;
    while(p != q && q->next != p){ //如果p->next != q,将不会比较最后两个值的大小，最后两个值可能不等
        if(p->data == q->data){
            p = p->next;
            q = q->prior;
        }else{
            cout<<"not symmetry"<<endl;
            return false;
        }
    }
    cout<<"symmetry"<<endl;
    return true;
}
/**
 * 删除最小节点直至表空，再删除头结点
 * @param L
 */
void delete_minToEmpty(DLinkList<int> &L){
    DNode<int> *p, *minpre, *min, *pre;
    while(L->next != L){
        p = L->next;
        pre = L;
        min = p; minpre = pre;
        while(p != L){
            if(p->data < min->data){
                min = p;
                minpre = pre;
            }
            pre = p;
            p = p->next;
        }
        cout<<"deleted val: "<<min->data<<endl;
        minpre->next = min->next;
        min->next->prior = minpre;
        free(min);
    }
    /**
     * 调用free释放掉所分配的内存后，表明该内存可以被别人使用，
     * 也就是说，其他地方调用malloc后，可以分配到该内存,
     * 并不代表free()以后指针指向null
     */
    free(L);
    L = nullptr; //规范
}
#endif //DATASTRUCTURELIB_DLINKLIST_H

栈与队列

顺序栈—SeqStack.h

//
// Created by knight1527 on 2022/7/9.
//

#ifndef DATASTRUCTURELIB_SEQSTACK_H
#define DATASTRUCTURELIB_SEQSTACK_H

#include <cstdlib>
#include <iostream>

using namespace std;
#define MaxSize 10
template <typename T>
struct SeqStack{
    T data[MaxSize];
    int top;
};

template <typename T>
void InitSeqStack(SeqStack<T> &S){
    S.top = -1;
}
template <typename T>
bool isEmpty(SeqStack<T> &S){
    return S.top == -1;
}
/**
 * top指向栈顶元素写法
 * @tparam T
 * @param S
 * @param e
 * @return
 */
template <typename T>
bool Push(SeqStack<T> &S, T e){
    if(S.top == MaxSize - 1){
        cout<<"Insert error: "<<e<<" Stack is full"<<endl;
        return false;
    }
    S.data[++S.top] = e;
    return true;
}
template <typename T>
bool Pop(SeqStack<T> &S, T &e){
    if(S.top == -1){
        cout<<"Stack is empty!"<<endl;
        return false;
    }
    e = S.data[S.top--];
    return true;
}
template <typename T>
bool getTop(SeqStack<T> &S, T &e){
    if(S.top == -1){
        cout<<"Stack is empty!"<<endl;
        return false;
    }
    e = S.data[S.top];
    return true;
}
template <typename T>
void print(SeqStack<T> &S){
    cout<<"SeqStack: top -> bottom:"<<endl;
    if(S.top == -1){
        cout<<"Stack is empty!"<<endl;
        return;
    }
    int index = S.top;
    while(index >= 0){
        cout<<S.data[index--]<<" ";
    }
    cout<<endl;
}
#endif //DATASTRUCTURELIB_SEQSTACK_H

链栈—ListStack.h

//
// Created by knight1527 on 2022/7/10.
//

#ifndef DATASTRUCTURELIB_LISTSTACK_H
#define DATASTRUCTURELIB_LISTSTACK_H


#include <cstdlib>
#include <iostream>

using namespace std;
/**
 * 不带头节点
 * @tparam T
 */
template <typename T>
struct Stack{
    T data;
    struct Stack<T> *next;
};
template <typename T>
using ListStack = Stack<T> *;

template <typename T>
void InitListStack(ListStack<T> &L){
    L = nullptr;
}
template <typename T>
bool isEmpty(ListStack<T> &L){
    return L == nullptr;
}
template <typename T>
bool Push(ListStack<T> &L, T e){
    auto s = (Stack<T> *)malloc(sizeof(Stack<T>));
    s->data = e;
    s->next = L;
    L = s;
    return true;
}
template <typename T>
bool Pop(ListStack<T> &L, T &e){
    if(isEmpty(L)){
        cout<<"Stack is empty!"<<endl;
        return false;
    }
    e = L->data;
    ListStack<T> p = L;
    L = p->next;
    free(p);
    return true;
}
template <typename T>
bool getTop(ListStack<T> &L, T &e){
    if(isEmpty(L)){
        cout<<"Stack is empty!"<<endl;
        return false;
    }
    e = L->data;
    return true;
}
template <typename T>
void print(ListStack<T> &L){
    cout<<"ListStack: top -> bottom:"<<endl;
    ListStack<T> p = L;
    while(p != nullptr){
        cout<<p->data<<" ";
        p = p->next;
    }
    cout<<endl;
}

#endif //DATASTRUCTURELIB_LISTSTACK_H

顺序队列—SeQueue.h

//
// Created by knight1527 on 2022/7/12.
//

#ifndef DATASTRUCTURELIB_SEQUEUE_H
#define DATASTRUCTURELIB_SEQUEUE_H

#include <cstdlib>
#include <iostream>

using namespace std;
#define MaxSize 10
/**
 * 另一种方式：加一个size变量记录大小用于判空，满。
 * @tparam T
 */
template <typename T>
struct SeQueue{
    T data[MaxSize];
    int front, rear;
};

template <typename T>
void InitSeQueue(SeQueue<T> &Q){
    Q.rear = Q.front = 0;
}
template <typename T>
bool isEmpty(SeQueue<T> &Q){
    return Q.front == Q.rear;
}
template <typename T>
bool enQueue(SeQueue<T> &Q, T e){
    if((Q.rear + 1)%MaxSize == Q.front){
        cout<<"enQueue error: "<<e<<" Full!"<<endl;
        return false;
    }
    Q.data[Q.rear] = e;
    Q.rear = (Q.rear + 1)%MaxSize;//循环队列
    return true;
}
template <typename T>
bool deQueue(SeQueue<T> &Q, T &e){
    if(isEmpty(Q)){
        cout<<"queue is empty!"<<endl;
        return false;
    }
    e = Q.data[Q.front];
    Q.front = (Q.front + 1)%MaxSize;
    return true;
}
template <typename T>
bool getFirst(SeQueue<T> &Q, T &e){
    if(isEmpty(Q)){
        cout<<"queue is empty!"<<endl;
        return false;
    }
    e = Q.data[Q.front];
    return true;
}
template <typename T>
int length(SeQueue<T> &Q){
    return (Q.rear + MaxSize - Q.front)%MaxSize;
}
#endif //DATASTRUCTURELIB_SEQUEUE_H

链队列—ListQueue.h

//
// Created by knight1527 on 2022/7/12.
//

#ifndef DATASTRUCTURELIB_LISTQUEUE_H
#define DATASTRUCTURELIB_LISTQUEUE_H

#include <cstdlib>
#include <iostream>

using namespace std;

/*
 * 每一个节点
 */
template <typename T>
struct LinkNode{
    T data;
    struct LinkNode<T> *next;
};
template <typename T>
struct LinkQueue{
    int length;
    LinkNode<T> *front, *rear;
};
/**
 * 带头结点
 * @tparam T
 * @param Q
 */
template <typename T>
void initQueue(LinkQueue<T> &Q){
    Q.length = 0;
    Q.front = Q.rear = (LinkNode<T> *)malloc(sizeof(LinkNode<T>));
    Q.front->next = nullptr;
}
template <typename T>
bool isEmpty(LinkQueue<T> &Q){
    return Q.front == Q.rear;
}
template <typename T>
bool enQueue(LinkQueue<T> &Q, T e){
    auto *s = (LinkNode<T> *)malloc(sizeof(LinkNode<T>));
    s->data = e;
    s->next = nullptr;
    Q.rear->next = s;
    Q.rear = s;
    Q.length++;
    return true;
}
template <typename T>
bool deQueue(LinkQueue<T> &Q, T &e){
    if(Q.front == Q.rear){
        cout<<"delete error: empty"<<endl;
        return false;
    }
    LinkNode<T> *p = Q.front->next;
    e = p->data;
    Q.front->next = p->next;
    if(Q.rear == p)//如果删除的是最后一个节点，特殊出理。
        Q.rear =Q.front;
    free(p);
    Q.length--;
    return true;
}
template <typename T>
bool getFirst(LinkQueue<T> &Q, T &e){
    e = Q.front->next->data;
    return true;
}

#endif //DATASTRUCTURELIB_LISTQUEUE_H

树

二叉树—TreeNode.h

//
// Created by knight1527 on 2022/7/15.
//

#ifndef DATASTRUCTURELIB_TREENODE_H
#define DATASTRUCTURELIB_TREENODE_H

#include <cstdlib>
#include <algorithm>
#include <iostream>
#include "ListQueue.h"
#include "ListStack.h"

using namespace std;
template <typename T>
struct TreeNode{
    T data;
    struct TreeNode<T> *lchild, *rchild;
    //struct TreeNode<T> *parent;
};
template <typename T>
using BitTree = TreeNode<T> *;

template <typename T>
void initTree(BitTree<T> &root, T rootVal){
    root = (TreeNode<T> *)malloc(sizeof(TreeNode<T>));
    root->data = rootVal;
    root->lchild = nullptr;
    root->rchild = nullptr;
}
template <typename T>
void initTree(BitTree<T> &root){
    root = (TreeNode<T> *)malloc(sizeof(TreeNode<T>));
    root->data = NULL;
    root->lchild = nullptr;
    root->rchild = nullptr;
}
/**
 * 创建一个测试满二叉树
 * @param root
 * @param level
 */
void initTestBitTree(BitTree<int> &root, int level){
    root = nullptr;
    if(level == 0)
        return;
    if(root == nullptr){
        initTree(root);
    }
    root->data = rand() % 10;
    initTestBitTree(root->lchild, level - 1);
    initTestBitTree(root->rchild, level - 1);
}
/**
 * 输出二叉树结构(层序遍历)
 * TestBitTree's structure:
 * 1
 * 7 9
 * 4 0 4 8
 * @tparam T
 * @param root
 */
template <typename T>
void print(BitTree<T> root){
    if(!root->lchild && !root->rchild){
        cout<<"empty tree"<<endl;
        return;
    }
    TreeNode<int> *p = root, *last = root, *r = nullptr;
    cout<<"TestBitTree's structure: "<<endl;
    LinkQueue<BitTree<T>> q{};
    initQueue(q);
    enQueue(q, root);
    while(!isEmpty(q)){
        deQueue(q, p);
        cout<<p->data<<" ";
        if(p->lchild){
            enQueue(q, p->lchild);
            r = p->lchild;
        }
        if(p->rchild){
            enQueue(q, p->rchild);
            r = p->rchild;
        }
        if(p == last){
            cout<<endl;
            last = r;
        }
    }
}
template <typename T>
void visit(BitTree<T> root){
    cout<<root->data<<" ";
}
/**
 * 先序遍历
 * @tparam T
 * @param root
 */
template <typename T>
void preOrder(BitTree<T> root){
    if(root){
        visit(root);
        preOrder(root->lchild);
        preOrder(root->rchild);
    }
}
/**
 * 中序遍历
 * @tparam T
 * @param root
 */
template <typename T>
void inOrder(BitTree<T> root){
    if(root){
        inOrder(root->lchild);
        visit(root);
        inOrder(root->rchild);
    }
}
/**
 * 后序遍历
 * @tparam T
 * @param root
 */
template <typename T>
void postOrder(BitTree<T> root){
    if(root){
        postOrder(root->lchild);
        postOrder(root->rchild);
        visit(root);
    }
}
/**
 * 求树深
 * @tparam T
 * @param root
 * @return
 */
template <typename T>
int treeDepth(BitTree<T> root){
    if(!root)
        return 0;
    int l = treeDepth(root->lchild);
    int r = treeDepth(root->rchild);
    return l>r ? l+1 : r+1;
}
//==================================练习==================================
/**
 * 非递归后序遍历
 * @param root
 */
void post_order(BitTree<int> root){
    cout<<endl<<"post order:"<<endl;
    TreeNode<int> *p = root, *r = nullptr;
    ListStack<TreeNode<int> *> stack;
    initListStack(stack);
    while(p || !isEmpty(stack)){
        if(p){
            Push(stack, p);
            p = p->lchild;
        }else{
            getTop(stack, p);
            if(p->rchild && p->rchild != r){
                p = p->rchild;
            }else{
                Pop(stack, p);
                visit(p);
                r = p;
                p = nullptr;
            }
        }
    }
}
/**
 * 非递归先序遍历
 * @param root
 */
void pre_order(BitTree<int> root){
    cout<<endl<<"pre order:"<<endl;
    TreeNode<int> *p = root;
    ListStack<TreeNode<int> *> stack;
    initListStack(stack);
    Push(stack, p);
    while(!isEmpty(stack)){
        Pop(stack, p);
        if(p->rchild)
            Push(stack, p->rchild);
        if(p->lchild)
            Push(stack, p->lchild);
        visit(p);
    }
}
/**
 * 非递归中序遍历
 * @param root
 */
void in_order(BitTree<int> root){
    cout<<endl<<"in order:"<<endl;
    TreeNode<int> *p = root;
    ListStack<TreeNode<int> *> stack;
    initListStack(stack);
    while(p || !isEmpty(stack)){
        if(p){
            Push(stack, p);
            p = p->lchild;
        }else{
            getTop(stack, p);
            visit(p);
            Pop(stack, p);
            p = p->rchild;
        }
    }
}
/**
 * 非递归求树高
 * @param root
 * @return
 */
int depth_non_recursive(BitTree<int> root){
    TreeNode<int> *r = nullptr, *last = root, *tep;
    int depth = 0;
    LinkQueue<TreeNode<int> *> q{};
    initQueue(q);
    enQueue(q, root);
    while(!isEmpty(q)){
        deQueue(q, tep);
        if(tep->lchild){
            enQueue(q, tep->lchild);
            r = tep->lchild;
        }
        if(tep->rchild){
            enQueue(q, tep->rchild);
            r = tep->rchild;
        }
        if(tep == last){
            depth++;
            last = r;
        }
    }
    return depth;
}
/**
 * 给出二叉树先序序列（$pre[1-n]$）和中序序列（$in[1-n]$），构造二叉树的二叉链表。
 * @param pre
 * @param in
 * @param pl 前序序列最左的节点
 * @param pr 前序序列最右的节点
 * @param il 中序序列最左的节点
 * @param ir 中序序列最右的节点
 * @return
 */
BitTree<int> create_by_in_pre(const int pre[], const int in[], int pl, int pr, int il, int ir){
    if(pl > pr || il > ir)return nullptr;
    auto root = (TreeNode<int> *)malloc(sizeof(TreeNode<int>));
    root->data = pre[pl];
    //注意此处应从il开始找中序的根（中序子序列中找）
    int k = il;
    for (k; in[k] != root->data; k++);
    k = k - il;
    root->lchild = create_by_in_pre(pre, in, pl+1, pl+k, il, il+k-1);
    root->rchild = create_by_in_pre(pre, in, pl+k+1, pr, il+k+1, ir);
    return root;
}
/**
 * 判断是否为完全二叉树
 * @description 层序遍历，将所有节点入队包括空节点，如果空节点后面还有非空节点就不是完全二叉树
 * @param root
 * @return
 */
bool judgeFullBinaryTree(BitTree<int> root){
    LinkQueue<TreeNode<int> *> q{};
    TreeNode<int> *p;
    initQueue(q);
    if(!root) return true;//空树为满二叉树
    enQueue(q, root);
    while(!isEmpty(q)){
        deQueue(q, p);
        if(p){
            enQueue(q, p->lchild);
            enQueue(q, p->rchild);
        }else{
            while(!isEmpty(q)){
                deQueue(q, p);
                if(p)
                    return false;
            }
        }
    }
    return true;
}
/**
 * 交换所有左右子树
 * @param root
 */
void swap(BitTree<int> &root){
    if(root){
        BitTree<int> temp = root->lchild;
        root->lchild = root->rchild;
        root->rchild = temp;
        swap(root->lchild);
        swap(root->rchild);
    }
}
/**
 * 返回先序第k个节点的值
 * @param root
 * @param k
 * @return
 */
int pre_find(BitTree<int> root, int k){
    ListStack<TreeNode<int> *> stack;
    initListStack(stack);
    TreeNode<int> *p;
    Push(stack, root);
    while(!isEmpty(stack)){
        Pop(stack, p);
        if(!--k){
            return p->data;
        }
        if(p->rchild)
            Push(stack, p->rchild);
        if(p->lchild)
            Push(stack, p->lchild);
    }
    return NULL;
}
//递归方式
int pre_find_index = 1;
void pre_find_rvi(BitTree<int> root, int k, int &rel){
    if(!root)
        return ;
    if(pre_find_index == k)
        rel = root->data;
    pre_find_index++;
    pre_find_rvi(root->lchild, k, rel);
    pre_find_rvi(root->rchild, k, rel);
}
/**
 * 返回后序第k个节点的值
 * @param root
 * @param k
 * @return
 */
int post_find(BitTree<int> root, int k){
    ListStack<TreeNode<int> *> stack;
    initListStack(stack);
    TreeNode<int> *p = root, *r = nullptr;
    while (p || !isEmpty(stack)){
        if(p){
            Push(stack, p);
            p = p->lchild;
        }else{
            getTop(stack, p);
            if(p->rchild && p->rchild != r){
                p = p->rchild;
            }else{
                Pop(stack, p);
                if(!--k) {
                    return p->data;
                }
                r = p;
                p = nullptr;
            }
        }
    }
    return NULL;
}
/**
 * 返回中序第k个节点的值
 * @param root
 * @param k
 * @return
 */
int in_find(BitTree<int> root, int k){
    ListStack<TreeNode<int> *> stack;
    initListStack(stack);
    TreeNode<int> *p = root;
    while (p || !isEmpty(stack)){
        if(p){
            Push(stack, p);
            p = p->lchild;
        }else{
            getTop(stack, p);
            if(!--k)
                return p->data;
            Pop(stack, p);
            p = p->rchild;
        }
    }
    return NULL;
}
/**
 * 删除所有以x为根的子树,层序遍历所有可能节点
 * @param root
 * @param x
 */
void deleteTree(BitTree<int> &root){//注意删除树的方式
    if(root){
        deleteTree(root->lchild);
        deleteTree(root->rchild);
        free(root);
    }
}
void delete_by_key(BitTree<int> &root, int x) {
    LinkQueue<TreeNode<int> *> q{};
    TreeNode<int> *p;
    if (root->data == x) {
        deleteTree(root);
        return;
    }
    initQueue(q);
    enQueue(q, root);
    while(!isEmpty(q)){
        deQueue(q, p);
        if(p->lchild) {
            if (p->lchild->data == x) {
                deleteTree(p->lchild);
                p->lchild = nullptr;
            } else {
                enQueue(q, p->lchild);
            }
        }
        if(p->rchild) {
            if (p->rchild->data == x) {
                deleteTree(p->rchild);
                p->rchild = nullptr;
            } else {
                enQueue(q, p->rchild);
            }
        }
    }
}
/**
 * 找到值为x的节点的所有祖先,后序遍历遍历到x时,栈中节点都是x的祖先
 * @param root
 * @param x
 */
#define MAXSIZE 1000
void find_ancestor(BitTree<int> root, int x){
    TreeNode<int>* stack[MAXSIZE];
    int top = -1;
    TreeNode<int> *p = root, *r = nullptr;
    while(p || top != -1){
        if(p){
            stack[++top] = p;
            p = p->lchild;
        }else{
            p = stack[top];
            if(p->rchild && p->rchild != r){
                p = p->rchild;
            }else{
                p = stack[top--];
                if(p->data == x)
                    break;
                r = p;
                p = nullptr;
            }
        }
    }
    while(top != -1){
        cout<<endl<<"Ancestors: "<<stack[top--]->data<<" ";
    }
}

/**
 * 找到值为x和y的节点的最近公共祖先,思路同上题一致，只是用了两个数组来存放祖先节点
 * @param root
 * @param x
 */
#define MAXSIZE 1000
bool find_same_nearest_ancestor(BitTree<int> root, int x, int y){
    TreeNode<int>* stack[MAXSIZE];
    int stack2[MAXSIZE], stack3[MAXSIZE]; //分别存放两个节点的祖先
    int top = -1, top2 = -1, top3 = -1;
    TreeNode<int> *p = root, *r = nullptr;
    while(p || top != -1){
        if(p){
            stack[++top] = p;
            p = p->lchild;
        }else{
            p = stack[top];
            if(p->rchild && p->rchild != r){
                p = p->rchild;
            }else{
                p = stack[top--];
                if(p->data == x){
                    top2 = top;
                    for (int i = top; i >= 0 ; --i) {
                        stack2[i] = stack[i]->data;
                    }
                }else if(p->data == y){
                    top3 = top;
                    for (int i = top; i >= 0 ; --i) {
                        stack3[i] = stack[i]->data;
                    }
                }
                r = p;
                p = nullptr;
            }
        }
    }
    for (int i = top3; i >= 0; --i) {
        for (int j = top2; j >= 0; --j) {
            if(stack3[i] == stack2[j]){
                cout<<endl<<"rel:"<<stack3[i];
                return true;
            }
        }
    }
    return false;
}
/**
 * 求非空二叉树宽度,层序遍历
 * @param root
 * @return
 */
int width(BitTree<int> root){
    TreeNode<int> *p = root, *r = nullptr, *last = root;
    int maxWidth = 0, temp = 0;
    LinkQueue<TreeNode<int> *> q{};
    initQueue(q);
    enQueue(q, root);
    while(!isEmpty(q)){
        temp++;
        deQueue(q, p);
        if(p->lchild) {
            r = p->lchild;
            enQueue(q, p->lchild);
        }
        if(p->rchild){
            r = p->rchild;
            enQueue(q, p->rchild);
        }
        if(p == last){
            maxWidth = max(maxWidth, temp);
            temp = 0;
            last = r;
        }
    }
    return maxWidth;
}
/**
 * 已知满二叉树前序序列返回其后续序列
 * @param pre
 * @return
 */
void solve(int pre[], int post[], int prel,int prer,int postl, int postr){
    if(prel > prer || postr < 0)
        return;
    post[postr] = pre[prel];
    int half = (prer - prel)/2;// 注意子树长度应是参数的子序列端点求得
    solve(pre, post, prel+1, prel+half, postl, postl+half-1);
    solve(pre, post, prel+half+1, prer, postl+half, postr-1);
}
int *preToPost(int pre[], int len){
    static int post[MAXSIZE];
    solve(pre, post, 0, len - 1, 0, len - 1);
    return post;
}
/**
 * 将叶节点从左到右连成一个单链表
 * @param root
 * @return
 */
TreeNode<int> *treeToList(BitTree<int> root){
    TreeNode<int> *head, *p, *pre = (TreeNode<int> *)malloc(sizeof(TreeNode<int>));
    head = pre;
    ListStack<TreeNode<int> *> stack;
    initListStack(stack);
    Push(stack, root);
    while(!isEmpty(stack)){
        Pop(stack, p);
        if(p->rchild) {
            Push(stack, p->rchild);
        }
        if(p->lchild) {
            Push(stack, p->lchild);
        }
        if(!p->lchild && !p->rchild){
            pre->rchild = p;
            pre = p;
            p->rchild = nullptr;
        }
    }
    return head;
}
/**
 * 判断两棵树是否相似
 * @param root1
 * @param root2
 * @return
 */
bool judgeSimilarTree(BitTree<int> root1, BitTree<int> root2){
    bool left, right;
    if(root1 == nullptr && root2 == nullptr){
        return true;
    }else if(root1 == nullptr || root2 == nullptr){
        return false;
    }else{
        left = judgeSimilarTree(root1->lchild, root2->lchild);
        right = judgeSimilarTree(root1->rchild, root2->rchild);
        return left && right;
    }
}
/**
 * 二叉树的带权路径长度（叶节点带权路径长度之和，权值*深度）
 * @description 层序遍历
 * @param root
 * @return
 */
int getWPL(BitTree<int> root){
    int wpl = 0, level = 1;
    TreeNode<int> *p, *r = nullptr, *last = root;
    LinkQueue<TreeNode<int> *> q{};
    initQueue(q);
    enQueue(q, root);
    while(!isEmpty(q)){
        deQueue(q, p);
        if(p->lchild){
            enQueue(q, p->lchild);
            r = p->lchild;
        }
        if(p->rchild){
            enQueue(q, p->rchild);
            r = p->rchild;
        }
        if(!p->lchild && !p->rchild){
            wpl += p->data * level;
        }
        if(p == last){
            level++;
            last = r;
        }
    }
    return wpl;
}
/**
 * 指定节点在二叉树的层次
 * @param root
 * @param tar
 * @return
 */
int levelInTree(BitTree<int> root, int tar){
    int level = 0;
    LinkQueue<TreeNode<int> *> q{};
    initQueue(q);
    TreeNode<int> *p = root, *last = root, *r = nullptr;
    enQueue(q, root);
    while(!isEmpty(q)){
        deQueue(q, p);
        if(p->lchild){
            enQueue(q, p->lchild);
            r = p->lchild;
        }
        if(p->rchild){
            enQueue(q, p->rchild);
            r = p->rchild;
        }
        if(p == last){
            level++;
            last = r;
        }
        if(tar == p->data) break;
    }
    return level;
}

/**
 * ==========================二叉排序树================================================================
 */
/**
 * 二叉排序树的插入
 * @param root
 * @param k
 * @return
 */
bool BST_insert(BitTree<int> &root, int key){
    //非递归，注意非递归方式分配内存后需要将其与父节点连接起来，不然找不到（p 已经指向其孩子节点，分配内存后
    // 原来的p的child指针仍指向nullptr）
    TreeNode<int> *p = root; //此处用来寻找插入的位置和当前插入位置的父节点
    TreeNode<int> *q = nullptr; //q记录插入位置的父节点用来连接插入的孩子
    while (p) {
        if (p->data == key) {
            return false;			//已经存在，插入失败
        }
        else if (p->data > key) {
            q = p;
            p = p->lchild;
        }
        else {
            q = p;
            p = p->rchild;
        }
    }
    //初始化一个插入结点
    p = (TreeNode<int> *)malloc(sizeof(TreeNode<int>));
    p->data = key;
    p->lchild = nullptr;
    p->rchild = nullptr;

    //将插入结点与之父节点相连
    if (!q) {		//要插入根节点，直接用root指针相连
        root = p;
    }
    else if (q->data > key) {		//插入父节点的左边，将父节点的左孩子指向插入的结点
        q->lchild = p;
    }
    else q->rchild = p;				//插入父节点的右边，将父节点的右孩子指向插入的结点
    return true;
}
bool BST_insert_rvi(BitTree<int> &root, int k){ \
    //递归方式相当是root->child = malloc;所以不会出现非递归的那种错误
   if(root == nullptr){
       root = (TreeNode<int> *)malloc(sizeof(TreeNode<int>));
       root->data = k;
       root->lchild = root->rchild = nullptr;
       return true;
   }else if(root->data == k){
       return false;
   }else if(root->data > k)
       return BST_insert_rvi(root->lchild, k);
   else
       return BST_insert_rvi(root->rchild, k);
}
/**
 * 创建二叉排序树
 * @param root
 * @param str
 * @param len
 */
void create_BST(BitTree<int> &root, int str[], int len){
    root = nullptr;
    int i = 0;
    while(i < len){
        BST_insert_rvi(root, str[i++]);
    }
}
/**
 * 判断二叉树是否排序树
 * @param root
 * @description 二叉排序树的中序遍历序列是一个有序序列
 * @return
 */
bool judgeSortingTree(BitTree<int> root){
    int pre = -1;
    BitTree<int> p = root;
    ListStack<BitTree<int>> stack;
    initListStack(stack);
    while(p || !isEmpty(stack)){
        if(p){
            Push(stack, p);
            p = p->lchild;
        }else{
            Pop(stack, p);
            if(p->data < pre) return false;
            else pre = p->data;
            p = p->rchild;
        }
    }
    return true;
}
/**
 * 指定节点在二叉排序树的层级
 * @param root
 * @param tar
 * @return
 */
int levelInSortingTree(BitTree<int> root, int tar){
    int level = 1;
    TreeNode<int> *p = root;
    while(p && p->data != tar){
        if(tar > p->data)
            p = p->rchild;
        else
            p = p->lchild;
        level++;
    }
    return level;
}

#endif //DATASTRUCTURELIB_TREENODE_H

二叉线索树—ThreadedBinaryTree.h

//
// Created by knight1527 on 2022/7/16.
//

#ifndef DATASTRUCTURELIB_THREADEDBINARYTREE_H
#define DATASTRUCTURELIB_THREADEDBINARYTREE_H


#include <cstdlib>
#include <iostream>
#include "TreeNode.h"
#include "ListQueue.h"

using namespace std;
/**
 * 二叉线索树
 * @tparam T
 */
template <typename T>
struct ThreadNode{
    T data;
    struct ThreadNode<T> *lchild, *rchild;
    /**
     * ltag == 1：表示lchild指向前驱，ltag == 0：lchild指向左孩子；rtag同理
     */
    int ltag, rtag; //左右线索标志
};
template <typename T>
using ThreadTree = ThreadNode<T> *;

//=========================================================================
template <typename T>
void initThreadTree(ThreadTree<T> &root){
    root = (ThreadNode<T> *)malloc(sizeof(ThreadNode<T>));
    root->data = NULL;
    root->lchild = nullptr;
    root->rchild = nullptr;
}
/**
 * 创建一个测试满二叉树
 * @param root
 * @param level
 */
void initTestThreadBitTree(ThreadTree<int> &root, int level){
    if(level == 0)
        return;
    if(root == nullptr){
        initThreadTree(root);
    }
    root->data = rand() % 10;
    initTestThreadBitTree(root->lchild, level - 1);
    initTestThreadBitTree(root->rchild, level - 1);
}
/**
 * 输出二叉树结构(层序遍历)
 * TestBitTree's structure:
 * 1
 * 7 9
 * 4 0 4 8
 * @tparam T
 * @param root
 */
template <typename T>
void print(ThreadTree<T> root){
    if(!root->lchild || !root->rchild){
        cout<<"empty tree"<<endl;
        return;
    }
    int num = 0, level = 1;//节点数和层数
    cout<<"TestThreadBitTree's structure: "<<endl;
    LinkQueue<ThreadTree<T>> q ;
    initQueue(q);
    enQueue(q, root);
    while(!isEmpty(q)){
        ThreadTree<T> tep;
        deQueue(q, tep);
        cout<<tep->data<<" ";
        num++;
        if(num == (int)pow(2, level) - 1){
            level++;
            cout<<endl;
        }
        if(tep->lchild && tep->rchild){
            enQueue(q, tep->lchild);
            enQueue(q, tep->rchild);
        }
    }
}
//======================================================================

/**
 * 二叉树线索化
 */

template <typename T>
ThreadNode<T> *pre = nullptr;

template <typename T>
void visit(ThreadNode<T> *q){
    if(!q->lchild){
        q->lchild = pre<T>;
        q->ltag = 1;
    }
    if(pre<T> && !pre<T>->rchild){
        pre<T>->rchild = q;
        pre<T>->rtag = 1;
    }
    if(pre<T>) {
        cout << q->data << " -pre->" << pre<T>->data << endl;
        cout << pre<T>->data << " -next->" << q->data << endl;
    }
    pre<T> = q;
}
/**
 * 中序线索化, 法1（不直观）
 * @tparam T
 * @param root
 */
template <typename T>
void inThread(ThreadTree<T> root){
    if(root){
        inThread(root->lchild);
        visit(root);
        inThread(root->rchild);
    }
}
template <typename T>
void createInThread(ThreadTree<T> root){
    pre<T> = nullptr;
    if(root){
        inThread(root);
        if(pre<T>->rchild == nullptr){
            pre<T>->rtag = 1; //处理最后一个节点
        }
    }
}
//========================================================================
/**
 * 中序线索化, 法2（言简意赅）
 * @tparam T
 * @Description: 注意pre参数是指针的引用，对比法1中的全局变量，确保pre指针的唯一性
 */
template <typename T>
void inThread2(ThreadTree<T> root, ThreadTree<T> &pre){
    if(root){
        if(root->ltag != 1)
            inThread2(root->lchild, pre);

        if(!root->lchild){
            root->lchild = pre;
            root->ltag = 1;
        }
        if(pre && !pre->rchild){
            pre->rchild = root;
            pre->rtag = 1;
        }
        //=debug=
        if(pre) {
            cout << root->data << " -pre->" << pre->data << endl;
            cout << pre->data << " -next->" << root->data << endl;
        }
        //=======
        pre = root;

        if(root->rtag != 1)
            inThread2(root->rchild, pre);
    }
}
template <typename T>
void createInThread2(ThreadTree<T> root){
    cout<<"中序线索化："<<endl;
    ThreadTree<T> pre = nullptr;
    if(root){
        inThread2(root, pre);
        pre->rchild = nullptr;
        pre->rtag = 1;
    }
}
/**
 * 先序线索化
 * @tparam T
 * @Description: 注意pre参数是指针的引用，对比法1中的全局变量，确保pre指针的唯一性
 */
template <typename T>
void preThread(ThreadTree<T> root, ThreadTree<T> &pre){
    if(root){
        if(!root->lchild){
            root->lchild = pre;
            root->ltag = 1;
        }
        if(pre && !pre->rchild){
            pre->rchild = root;
            pre->rtag = 1;
        }
        //=debug=
        if(pre) {
            cout << root->data << " -pre->" << pre->data << endl;
            cout << pre->data << " -next->" << root->data << endl;
        }
        //=======
        pre = root;

        if(root->ltag != 1) // 避免死循环
            preThread(root->lchild, pre);
        if(root->rtag != 1)
            preThread(root->rchild, pre);
    }
}
template <typename T>
void createPreThread(ThreadTree<T> root){
    cout<<"先序线索化："<<endl;
    ThreadTree<T> pre = nullptr;
    if(root){
        preThread(root, pre);
        if(!pre->rchild){
            pre->rtag = 1;
        }
    }
}
/**
 * 后序线索化
 * @tparam T
 * @Description: 注意pre参数是指针的引用，对比法1中的全局变量，确保pre指针的唯一性
 */
template <typename T>
void postThread(ThreadTree<T> root, ThreadTree<T> &pre){
    if(root){
        if(root->ltag != 1) // 避免死循环
            postThread(root->lchild, pre);
        if(root->rtag != 1)
            postThread(root->rchild, pre);

        if(!root->lchild){
            root->lchild = pre;
            root->ltag = 1;
        }
        if(pre && !pre->rchild){
            pre->rchild = root;
            pre->rtag = 1;
        }
        //=debug=
        if(pre) {
            cout << root->data << " -pre->" << pre->data << endl;
            cout << pre->data << " -next->" << root->data << endl;
        }
        //=======
        pre = root;
    }
}
template <typename T>
void createPostThread(ThreadTree<T> root){
    cout<<"后序线索化："<<endl;
    ThreadTree<T> pre = nullptr;
    if(root){
        postThread(root, pre);
        //处理最后一个节点
        if(!pre->rchild){
            pre->rtag = 1;
        }
    }
}

//================== 中序线索二叉树的遍历==============================
/**
 * 找到当p子树的中序第一个节点和中序最后一个节点
 * @tparam T
 * @param p
 * @return
 */
template <typename T>
ThreadNode<T> *FirstNode(ThreadNode<T> *p){
    while(p->ltag != 1) p = p->lchild;
    return p;
}
template <typename T>
ThreadNode<T> *LastNode(ThreadNode<T> *p){
    while(p->rtag != 1) p = p->rchild;
    return p;
}
/**
 * 找到中序线索二叉树中p的后继和前驱
 * @tparam T
 * @param p
 * @return
 */
template <typename T>
ThreadNode<T> *In_NextNode(ThreadNode<T> *p){
    if(p->rtag != 1) return FirstNode(p->rchild);
    return p->rchild;
}
template <typename T>
ThreadNode<T> *In_PreNode(ThreadNode<T> *p){
    if(p->ltag != 1) return LastNode(p->lchild);
    return p->lchild;
}
/**
 * 中序线索二叉树的遍历
 * @tparam T
 * @param root
 */
template <typename T>
void InOrder(ThreadTree<T> root){
    for (ThreadNode<T> *p = FirstNode(root); p ; p = In_NextNode(p)) {
        // do something!
    }
}
//================== 先序线索二叉树的遍历==============================
/**
 * 找到先序线索二叉树中p的后继，找前驱不方便
 * @tparam T
 * @param p
 * @return
 */
template <typename T>
ThreadNode<T> *Pre_NextNode(ThreadNode<T> *p){
    if(p->rtag != 1) { // 一定有右孩子
        if(p->lchild) // 如果有左孩子，左孩子的根就是后继
            return p->lchild;
    }
    return p->rchild;
}
template <typename T>
void PreOrder(ThreadTree<T> root){
    for (ThreadNode<T> *p = root ; p ; p = Pre_NextNode(p)) {
        // do something!
    }
}
//================== 后序线索二叉树的遍历==============================
/**
 * 找到后序线索二叉树中p的前驱，找后继不方便
 * @tparam T
 * @param p
 * @return
 */
template <typename T>
ThreadNode<T> *Post_PreNode(ThreadNode<T> *p){
    if(p->ltag != 1) { // 一定有左孩子
        if(p->rchild) //如果右孩子存在，则右孩子的根是前驱，否则是左孩子的根
            return p->rchild;
    }
    return p->lchild;
}
/**
 * 从后往前后序的反向遍历
 * @tparam T
 * @param root
 */
template <typename T>
void PostOrder_re(ThreadTree<T> root){
    for (ThreadNode<T> *p = root ; p ; p = Post_PreNode(p)) {
        // do something!
    }
}
#endif //DATASTRUCTURELIB_THREADEDBINARYTREE_H

图

无向图和有向图—Graph.h

//
// Created by knight1527 on 2022/7/24.
//

#ifndef DATASTRUCTURELIB_GRAPH_H
#define DATASTRUCTURELIB_GRAPH_H


#include <cstdlib>
#include <algorithm>
#include <iostream>
#include "ListQueue.h"
#include "ListStack.h"
using namespace std;

#define INF 0x7fffffff

/**
 * 邻接矩阵(适用稠密图)
 */
struct M_Graph{
    int vex[MAXSIZE]; //顶点数组
    int edge[MAXSIZE][MAXSIZE];
    int vexnum, edgenum; //顶点数，边数
};
void init(M_Graph &g){
    for (int i = 0; i < MAXSIZE; ++i) {
        for (int j = 0; j < MAXSIZE; ++j) {
            if (i == j)
                g.edge[i][j] = 0;
            else
                g.edge[i][j] = INF;
        }
    }
}

/**
 * 邻接表
 */
struct ArcNode{ // 边表节点
    int adjvex; // 边终点位置
    struct ArcNode *next; // 指向该节点下一条边的指针
    int wight; // 边权值
};
struct VNode{ // 顶点表节点
    int data; // 顶点信息
    ArcNode *first; // 指向该顶点第一条边
};
using AdjList = VNode[MAXSIZE];
struct L_Graph{
    AdjList vertices; // 领接表
    int vexnum, arcnum; // 顶点数和边数
};

/**
 * 加边
 * @param g
 */
void add(L_Graph &g, int start, int end){
    auto *p = (ArcNode *)malloc(sizeof(ArcNode));
    p->adjvex = end;
    p->next = g.vertices[start].first;
    g.vertices[start].first = p;
}
/**
 * 初始化一个测试无向图
 * @param g
 */
char edges[] = {'1','2','#','1','3','#','1','4','#','2','3','#','3','5','#'};
L_Graph initTestGraph(){
    L_Graph g{};
    g.vexnum = 5;
    g.arcnum = 0;
    for (int i = 1; i < 6; ++i) {
        g.vertices[i].first = nullptr;
    }
    for (int i = 0; i < 15;) {
        int start = edges[i] - '0', end = edges[i + 1] - '0';
        add(g, start, end);
        //无向图加双边
        add(g, end, start);
        g.arcnum += 2;
        i += 3;
    }
    return g;
}
/**
 * 输出边
 * @param g
 */
bool visited[MAXSIZE]; //访问标志

void print(L_Graph g, int start){
    cout<<endl<<"test graph's edges:"<<endl;
    for (int i = 1; i < MAXSIZE; ++i) {
        if(i > start) break;
        ArcNode *p = g.vertices[i].first;
        while(p){
            cout<<i<<"-->"<<p->adjvex<<endl;
            p = p->next;
        }
    }
}
/**
 * 返回节点邻接表中的第一个邻接点
 * @param g
 * @param v
 * @return
 */
int FirstNeighbor(L_Graph g, int v){
    if(g.vertices[v].first)
        return g.vertices[v].first->adjvex;
    else
        return -1;
}
/**
 * 返回v邻接表中w的下一个邻接点
 * @param g
 * @param v
 * @param w
 */
int NextNeighbor(L_Graph g, int v, int &w){
    ArcNode *p = g.vertices[v].first;
    while(p->adjvex != w){
        p = p->next;
    }
    if(p->next)
        return p->next->adjvex;
    else
        return -1;
}
void visit(int w){
    cout<<w<<" ";
}
/**
 * bfs遍历打印
 * @param g
 */
void solve_bfs(L_Graph g, int v){
    visit(v);
    visited[v] = true;
    LinkQueue<int> q{};
    initQueue(q);
    enQueue(q, v);
    while (!isEmpty(q)){
        deQueue(q, v);
        for (int w = FirstNeighbor(g, v); w >= 0; w = NextNeighbor(g, v, w)) {
            if(!visited[w]){
                visit(w);
                visited[w] = true;
                enQueue(q, w);
            }
        }
    }
}
void BFS(L_Graph g){
    cout<<endl<<"bfs: ";
    for (int i = 1; i <= g.vexnum; ++i) {
        visited[i] = false;
    }
    for (int i = 1; i <= g.vexnum; ++i) {
        if(!visited[i]) // 有可能连通分量不为1，确保遍历到所有连通分量
            solve_bfs(g, i);
    }
}
/**
 * dfs遍历打印
 * @param g
 */
void solve_dfs(L_Graph g, int v){
    visit(v);
    visited[v] = true;
    for (int w = FirstNeighbor(g, v); w >= 0; w = NextNeighbor(g, v, w)) {
        if(!visited[w]) //**
            solve_dfs(g, w);
    }
}
void DFS(L_Graph g){
    cout<<endl<<"dfs: ";
    for (int i = 1; i <= g.vexnum; ++i) {
        visited[i] = false;
    }
    for (int i = 1; i <= g.vexnum; ++i) {
        if(!visited[i]) // 有可能连通分量不为1，确保遍历到所有连通分量
            solve_dfs(g, i);
    }
}

//====================================作业题==============================================
/**
 * 判断无向图是否为一棵树（只有n-1条边或者没有回路）（一次遍历能访问完n个节点和n-1条边），下面分别dfs和bfs计数
 * @param g
 * @return
 */
bool isTree_bfs(L_Graph g){ //return g.vexnum == 2*(g.arcnum-1);
    for (int i = 1; i <= g.vexnum; ++i) {//注意写的是1序还是0序
        visited[i] = false;
    }
    int vexNum = 0, eNum = 0;//记录节点数和边数
    LinkQueue<int> q{};
    initQueue(q);
    enQueue(q, 1);
    visited[1] = true;
    vexNum++;
    while(!isEmpty(q)){
        int v;
        deQueue(q, v);
        for (int w = FirstNeighbor(g, v); w >= 0; w = NextNeighbor(g, v, w)) {
            eNum++;
            if(!visited[w]){
                vexNum++;
                visited[w] = true;
                enQueue(q, w);
            }
        }
    }
    return vexNum == g.vexnum && eNum == 2*(g.arcnum - 1);
}
void dfs(L_Graph g, int v, int &Vnum, int & Enum){
    visited[v] = true;
    Vnum++;
    int w = FirstNeighbor(g, v);
    while(w != -1){
        Enum++;
        if (!visited[w])
            dfs(g, w, Vnum, Enum);
        w = NextNeighbor(g, v, w);
    }
}
bool isTree_dfs(L_Graph g){
    for (int i = 1; i <= g.vexnum; ++i) {//注意写的是1序还是0序
        visited[i] = false;
    }
    int vexNum = 0, eNum = 0;
    dfs(g, 1, vexNum, eNum);
    return vexNum == g.vexnum && eNum == 2*(g.arcnum - 1);
}
/**
 * 非递归dfs,利用栈,会从每个单链表最后一个节点开始向下搜（和递归中从左到右的顺序不同）
 * @param g
 * @param v
 */
void dfs_stack(L_Graph g, int v){
    cout<<endl<<"dfs seq:";
    for (int i = 1; i <= g.vexnum; ++i) {
        visited[i] = false;
    }
    ListStack<int> stack;
    initListStack(stack);
    Push(stack, v);
    visited[v] = true;
    while(!isEmpty(stack)){
        int k;
        Pop(stack, k);
        visit(k);
        for (int w = FirstNeighbor(g, k); w >= 0; w = NextNeighbor(g, k, w)) {
            if(!visited[w]){
                visited[w] = true;
                Push(stack, w);
            }
        }
    }
}

/**
 * 分别用dfs和bfs判别是否存在由vi到vj的路径
 */
bool path_exists_dfs(L_Graph g, int vi, int vj){
    for (int i = 1; i <= g.vexnum; ++i) {
        visited[i] = false;
    }
    ListStack<int> stack;
    initListStack(stack);
    visited[vi] = true;
    Push(stack, vi);
    while(!isEmpty(stack)){
        Pop(stack, vi);
        if(vi == vj)
            return true;
        for (int i = FirstNeighbor(g, vi); i >= 0; i = NextNeighbor(g, vi, i)) {
            if(!visited[i]){
                visited[i] = true;
                Push(stack, i);
            }
        }
    }
    return false;
}
bool path_exists_bfs(L_Graph g, int vi, int vj){
    for (int i = 1; i <= g.vexnum; ++i) {
        visited[i] = false;
    }
    LinkQueue<int> q{};
    initQueue(q);
    enQueue(q, vi);
    visited[vi] = true;
    while(!isEmpty(q)){
        deQueue(q, vi);
        if(vi == vj)
            return true;
        for (int i = FirstNeighbor(g, vi); i >= 0; i = NextNeighbor(g, vi,i)) {
            if(!visited[i]){
                visited[i] = true;
                enQueue(q, i);
            }
        }
    }
    return false;
}

/**
 * 打印vi到vj的所有简单路径(dfs)
 * @param g
 * @param vi
 * @param vj
 */
 /**
  * dfs函数
  * @param g
  * @param vi 起点
  * @param vj 终点
  * @param path 路径数组
  * @param index 路径的长度
  * @param tep 保存vi方便打印
  */
void solve_path(L_Graph g, int vi, int vj, int path[], int index, int tep){
    visited[vi] = true;
    if(vi == vj){
        cout<<endl<<"path: "<<tep;
        for (int i = 0; i < index; ++i) {
            cout<<"-->"<<path[i];
        }
    }
    for (int i = FirstNeighbor(g, vi); i >= 0; i = NextNeighbor(g, vi, i)) {
        if(!visited[i]){
            path[index] = i;
            solve_path(g, i, vj, path, index + 1, tep);
        }
    }
    visited[vi] = false;// 回溯，不然节点访问一次就不能再访问，不能达到遍历完所有可能路径的目的
}
void print_path(L_Graph g, int vi, int vj){
    for (int i = 1; i <= g.vexnum; ++i) {
        visited[i] = false;
    }
    int path[MAXSIZE];
    solve_path(g, vi, vj, path, 0, vi);
}

#endif //DATASTRUCTURELIB_GRAPH_H

查找和排序

查找和排序—FindAndSort.h

//
// Created by knight1527 on 2022/8/7.
//

#ifndef DATASTRUCTURELIB_FINDANDSORT_H
#define DATASTRUCTURELIB_FINDANDSORT_H

#include "LinkList.h"
#include "ListStack.h"
#include <cstdlib>
#include <algorithm>
#include <iostream>

using namespace std;

template <typename T>
void Swap(T &a, T &b){
    T tep = a;
    a = b;
    b = tep;
}

/**
 * 递归折半查找
 * @param num
 * @param low
 * @param high
 * @return
 */
int binary_search_rvi(int num[], int low, int high, int tar){
    if(low <= high){
        int mid = (low + high)/2;
        if(num[mid] == tar)
            return mid;
        else if(num[mid] > tar)
            return binary_search_rvi(num, low, mid - 1, tar);
        else
            return binary_search_rvi(num, mid + 1, high, tar);
    } else return -1;
}
/**
 * 高效顺序查找（查找成功改变目标值位置--前移）
 * @param num 顺序表或者单链表
 * @return
 * @attention 值得注意的是数组名做参数传的是数组的地址
 */
int seqEfficientFind(int num[], int len, int tar){ // 顺序表
    int rel = -1;
    for (int i = 0; i < len; ++i) {
        if(num[i] == tar) {
            rel = i;
            if (i - 1 >= 0){
                Swap(num[i - 1], num[i]);
                break;
            }
        }
    }
    return rel;
}
int listEfficientFind(LinkList<int> l, int tar){ // 单链表
    int rel = 1;
    LinkList<int> pre = l, q = l->next;
    while(q) {
        if (q->data == tar) {
            if(pre != l){
                int tep = q->data;
                q->data = pre->data;
                pre->data = tep;
            }
            break;
        } else {
            rel++;
            pre = q;
            q = q->next;
        }
    }
    return rel;
}

//====================================排序======================================
/**
 * 直接插入排序
 * @param a
 * @param start
 * @param len
 * @efficiency S(n) = O(1), T(n) = O(n^2)
 */
void insertSort(int a[], int start, int len){
    for (int i = start + 1; i < start + len; ++i) {
        if(a[i] < a[i-1]){
            int tep = a[i];
            int j;
            for (j = i-1; j >= start && a[j] > tep; j--) {
                a[j+1] = a[j];
            }
            a[j + 1] = tep; // 注意下标
        }
    }
}
/**
 * 希尔排序
 * @param a
 * @param start
 * @param len
 * @efficiency S(n) = O(1), T(n) = O(n^1.3) ~ O(n^2)
 */
void shellSort(int a[], int start, int len){
    for (int d = (start + len)/2; d >=1 ; d/=2) {
        //注意下面插入排序中的增量 d
        for (int i = start + d; i < start + len; ++i) {
            if(a[i] < a[i-d]){
                int tep = a[i], j;
                for (j = i - d; j >= start && a[j] > tep; j-=d) {
                    a[j + d] = a[j];
                }
                a[j + d] = tep;
            }
        }
        //打印每次增量排序的结果
        cout<<"d = "<<d<<" : ";
        for (int i = start; i < start + len; i++){
            cout<<a[i]<<" ";
        }
        cout<<endl;
    }
}
/**
 * 快速排序
 * @param a
 * @param low
 * @param high
 */
int partition_randPivot(int a[], int low, int high);
int partition(int a[], int low, int high){ // 划分
    int pivot = a[low]; //选第一个元素为枢轴
    while(low < high){
        while(low < high && a[high] >= pivot) --high;
        a[low] = a[high];
        while(low < high && a[low] <= pivot) ++low;
        a[high] = a[low];
    }
    a[low] = pivot;
    return low; //枢轴的位置
}
void quickSort(int a[], int low, int high){
    if(low < high){
        int pivot = partition(a, low, high);
        quickSort(a, low, pivot - 1); // 划分左子表
        quickSort(a, pivot + 1, high); // 划分右子表
    }
}
/**
 * 建立大根堆
 * @param a
 * @param len
 */
void heapAdjust(int a[], int k, int len);
void buildMaxHeap(int a[], int len){ // 注意堆的构建方法
    //值的注意的是，大根堆小根堆是一颗完全二叉树，所以下标应该从1开始，不然根节点就失去了左右子节点
    for(int i = len/2; i > 0; i--){// len/2以后的节点都为终端节点，只调整非终端节点
        heapAdjust(a, i , len);
    }
}
void heapAdjust(int a[], int k, int len){ //将以k为根的子树调整为大根堆
    a[0] = a[k];
    for (int i = 2*k; i <= len; i*=2) {//沿k较大的子节点向下筛选
        if(i < len && a[i] < a[i+1]) // 得到较大子节点下标，注意i>=len
            i++;
        if(a[0] >= a[i]) break; // k已经大于其左右子节点
        else{
            a[k] = a[i]; //将k调整为子节点中的较大值
            k = i; // 继续向较大子节点筛选
        }
    }
    a[k] = a[0];
}
/**
 * 小根堆
 * @param a
 * @param k
 * @param len
 */
void minHeapAdjust(int a[], int k, int len){
    a[0] = a[k];
    for (int i = 2*k; i <= len; i*=2) {//沿k较小的子节点向下筛选
        if(i < len && a[i] > a[i+1]) // 得到较小子节点下标，注意i>=len
            i++;
        if(a[0] <= a[i]) break; // k已经小于其左右子节点
        else{
            a[k] = a[i]; //将k调整为子节点中的较小值
            k = i; // 继续向较小子节点筛选
        }
    }
    a[k] = a[0];
}
void buildMinHeap(int a[], int len){
    for (int i = len/2; i > 0; --i) {
        Swap(a[i], a[1]);
        minHeapAdjust(a, i, len);
    }
}
/**
 * 堆排序，增序，基于小根堆则是逆序
 * @param a
 * @param star
 * @param len
 */
void heapSort(int a[], int len, bool reverse){
    if(!reverse){
        buildMaxHeap(a, len);
        for (int i = len; i > 1; --i) {
            Swap(a[i], a[1]);
            heapAdjust(a, 1 ,i - 1);
        }
    }else{
        buildMinHeap(a, len);
        for (int i = len; i > 1; --i) {
            Swap(a[i], a[1]);
            minHeapAdjust(a, 1 ,i - 1);
        }
    }
}

/**
 * 归并排序
 */
void merge(int a[], int low, int mid, int high){
    int *b = (int *)malloc((high - low + 5)*sizeof(int));
    for (int k = low; k <= high; ++k)
        b[k] = a[k];
    int i, j, k;
    for (i = low, j = mid + 1, k = i; i <= mid && j <= high; ++k) {
        if(b[i] >= b[j]){
            a[k] = b[j++];
        }else{
            a[k] = b[i++];
        }
    }
    while(i <= mid) a[k++] = b[i++]; // 将b数组元素全部遍历完
    while(j <= high) a[k++] = b[j++];
}
void mergeSort(int a[], int low, int high){
    if(low < high){
        int mid = (low + high)/2;
        mergeSort(a, low, mid);
        mergeSort(a, mid+1, high);
        merge(a, low, mid, high);
    }
}


//==============================================练习==========================================
/**
 * 非递归快排
 * @param a
 * @param low
 * @param high
 */
void quickSort_inrvi(int a[], int low, int high){
    ListStack<int> stack;
    initListStack(stack);
    Push(stack, low);
    Push(stack, high);
    while(!isEmpty(stack)){
        int pivot, tlow, thigh, tepL, tepH;
        Pop(stack, thigh);
        Pop(stack, tlow);
        tepL = tlow; tepH = thigh; // 把每个区间的首尾下标存下来，因为后面排序会改变tlow和thigh
        pivot = a[tlow]; // 这个枢轴是这个区间的首值，怎么会写到while里面去呢
        while(tlow < thigh){
            while(thigh > tlow && a[thigh] >= pivot) thigh--;
            a[tlow] = a[thigh];
            while(tlow < thigh && a[tlow] <= pivot) tlow++;
            a[thigh] = a[tlow];
        }
        a[tlow] = pivot;
        if(tepL <= tlow - 1){ //注意两个if分开啊，不要犯些低级错误
            Push(stack, tepL);
            Push(stack, tlow - 1);
        }
        if(tlow + 1 <= tepH){
            Push(stack, tlow + 1);
            Push(stack, tepH);
        }
    }
}
/**
 * 双冒泡排序 算法，第一遍将最大元素放在后面，第二遍将最小元素放在前面，交替进行
 * @param a
 * @param low
 * @param high
 */
void doubleBubbleSort(int a[], int low, int high){
    int i = 0;
    while(low < high){
        if(i++%2 == 0){
            for (int j = low; j < high; ++j) {
                if(a[j] > a[j+1])
                    Swap(a[j], a[j+1]);
            }
            high--;
        }else{
            for (int j = high; j > low; --j) {
                if(a[j] < a[j-1])
                    Swap(a[j], a[j-1]);
            }
            low++;
        }
    }
}
/**
 * 将所有奇数移动到所有偶数前
 * @param a
 * @param low
 * @param high
 */
void odd_even_seq(int a[], int low, int high){
    while(low < high){
        while(a[low] % 2 == 1) low++;
        while(a[high]%2 == 0) high--;
        if(low <= high)
            Swap(a[low], a[high]);
    }
}
/**
 * 随机确定快排分割的枢轴
 * @param a
 * @param low
 * @param high
 * @return
 */
int partition_randPivot(int a[], int low, int high){
    Swap(a[low], a[low + rand()%(high - low + 1)]); //把随机枢轴放在low的位置方便套板子
    int pivot = a[low];
    while(low < high){
        while(low < high && a[high] >= pivot) high--;
        a[low] = a[high];
        while(low < high && a[low] <= pivot) low++;
        a[high] = a[low];
    }
    a[low] = pivot;
    return low;
}
/**
 * 返回序列第k小的元素，T(n) = O(n + k*log2N)，王道p339
 * @param a
 * @param low
 * @param high
 * @param k
 * @return
 */
int smallest(int a[], int low, int high, int k){
    int pivot = a[low];
    int low_tep = low;
    int high_temp = high;
    while(low < high){
        while(low < high && a[high] >= pivot) high--;
        a[low] = a[high];
        while(low < high && a[low] <= pivot) low++;
        a[high] = a[low];
    }
    a[low] = a[high];
    if(low == k) {
        return a[low];
    }else if(low < k) {
        return smallest(a, low_tep, low - 1, k);
        //注意，当在这个区间没找到时，去子区间找最终都是第k位处
    }else{
        return smallest(a, low + 1, high_temp, k);
    }
}
/**
 * 将顺序表划分为两个子表，使它们的关键字个数之差最小，所有关键字之和之差最小
 * @param a
 * @param n
 * @return
 * @description 利用快排的思想，n/2的左边的元素全小于右边的元素
 */
int setPartition(int a[], int n){
    int pivot, low = 0, tlow = 0, high = n-1, thigh = n-1, flag = 1, k = n/2;
    int S1 = 0, S2 = 0;
    while(flag){
        pivot = a[low];
        while(low < high){
            while (low < high && a[high] >= pivot) --high;
            a[low] = a[high];
            while (low < high && a[low] <= pivot) ++low;
            a[high] = a[low];
        }
        a[low] = pivot;
        // A1尽量取少一点元素，这样可以保证和差最大，个数之差还是最小，k上取整它们的和差小了，但个数之差并没有变
        if(low == k - 1)
            flag = 0;
        if(low < k - 1){
            tlow = ++low;
            high = thigh;
        }else{
            thigh = --high;
            low = tlow;
        }
    }
    for (int i = 0; i < k; ++i) S1 += a[i];
    for (int i = k; i < n; ++i) S2 += a[i];
    return S2 - S1;
}
/**
 * 以平均值为数轴，平均值不一定是待排元素
 * @param a
 * @param low
 * @param high
 */
void avgQuickSort(int a[], int low, int high){
    int avg = 0, tlow = low, thigh = high;
    for (int i = low; i <= high; ++i) {
        avg += a[i];
    }
    avg /= (high - low + 1);
    if(low < high){
        while(low < high){
            while(high > low && a[high] > avg) high--;
            while(low < high && a[low] < avg) low++;
            if(low < high) {
                Swap(a[low++], a[high--]);
            }
        }
        if(low < thigh && high > tlow) {
            avgQuickSort(a, tlow, high);
            avgQuickSort(a, low, thigh);
        }
    }
}
#endif //DATASTRUCTURELIB_FINDANDSORT_H