【考研】数据结构复习

一、线性表

1、线性表的顺序表示

（1）定义

静态分配

#define MaxSize 50
typedef struct{
    ElemType data[MaxSize];
    int length;
}SqList;

void InitList(SqList &L){
    for(itn i=0;i<Maxsize;i++)
        L.data[i]=0;
    L.length=0;
}

动态分配

#define InitSize 100
typedef struct{
    ElemType *data;      // 指示动态分配数组的指针
    int MaxSize,length;
}SqList;

void InitList(SqList &L){
    L.data=(ElemType*)malloc(sizeof(ElemType)*InitSize);
    L.length=0;
    L.MaxSize=InitSize;
}

// 初始动态分配
L.data=(ElemType*)malloc(sizeof(ElemType)*InitSize);// C
L.data=new ElemType[InitSize];// C++

（2）基本操作

Ⅰ 插入操作

bool ListInsert(SqList &L,int i,ElemType e){
    if(i<1||i>L.length+1)
        return false;
    if(L.length>=MaxSize)
        return false;
    for(int j=L.length;j>=i;j--)
        L.data[j]=L.data[j-1];
    L.data[i-1]=e;
    L.length++;
    return true;
}

Ⅱ 删除操作

bool ListDelete(SqList &L,int i,ElemType &e){
    if(i<1||i<L.length)
        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;
}

Ⅲ 按值查找

静态分配

int LocateElem(SqList L,ElemType e){
    for(int i=0;i<L.length;i++)
        if(L.data[i]==e)
            return i+1;
    return 0;
}

Ⅳ按位查找

静态分配

ElemType GetElem(SqList L,int i){
    return L.data[i-1];
}

2、线性表的链式表示

单链表

（1）定义

typedef struct LNode{
    ElemType data;
    struct LNode *next;
}LNode,*LinkList;

// 不带头节点
bool InitList(LinkList &L){
    L=NULL;
    return true;
}

// 带头节点
bool InitList(LinkList &L){
    L=(LNode *)malloc(sizeof(LNode));
    if(L==NULL)
        return false;
    L->next=NULL;
    return true;
}

（2）基本操作

Ⅰ 按位序插入

// 不带头节点
bool ListInsert(LinkList &L,int i,RlrmType e){
	if(i<1)
        return false;
    if(i==1){
        LNode *s=(LNode *)malloc(sizeof(LNode));
        s->data=e;
        s->next=L;
        L=s;
        return true;
    }
    LNode *p;
    int j=0;
    p=L;
    while(p!=NULL&&j<i-1){
        p=p->next;
        j++;
    }
    if(p==NULL)
        return false;
    LNode *S=(LNode *)malloc(sizeof(LNode));
    s->data=e;
    s->next=p->next;
    p->next=s;
    return true;
}

// 带头节点
bool ListInsert(LinkList &L,int i,RlrmType e){
	if(i<1)
        return false;
    LNode *p;
    int j=0;
    p=L;
    while(p!=NULL&&j<i-1){
        p=p->next;
        j++;
    }
    if(p==NULL)
        return false;
    LNode *S=(LNode *)malloc(sizeof(LNode));
    s->data=e;
    s->next=p->next;
    p->next=s;
    return true;
}

Ⅱ 后插操作

bool InsertNextNode(LNode *p,ElemType e){
    if(p==NULL)
        return false;
    LNode *s=(LNode *)malloc(sizeof(LNode));
    if(s==NULL)
        return  false;
    s->data=e;
    s->next=p->next;
    p->next=s;
    return true;
}

Ⅳ 前插操作

bool InsertPriorNode(LNode *p,ElemType e){
    if(p==NULL)
        return false;
    LNode *s=(LNode *)malloc(sizeof(LNode));
    if(s==NULL)
        return false;
    s->next=p->next;
    s->data=p->data;
    p->next=s;
    p->data=e;
    return true;
}

Ⅴ 按位序删除

bool ListDelete(LinkList &L,int i,ElemType &e){
    if(i<1)
        return false;
    LNode *p;
    int j=0;
    p=L;
    while(p!=NULL&&j<i-1){
        p=p->next;
        j++;
    }
    if(p==NULL)
        return false;
    if(p->next==NULL)
        return false;
    LNode *q=p->next;
    e=q->data;
    p->next=q->next;
    free(q);
    return true;
}

Ⅵ 指定节点删除

// 不能删除最后一个结点

bool DeleteNode(LNode *p){
    if(p==NULL)
        return false;
    LNode *q=p->next;
    p->data=p->next->data;
    p->next=q->next;
    free(q);
    return true;
}

Ⅶ 按位查找

LNode * GetElem(LinkList L,int i){
    if(i<0)
        return NULL;
    LNode *p;
    int j=0;
    p=L;
    while(p!=NULL&&j<i){
        p=p->next;
        j++;
    }
    return p;
}

Ⅷ 按值查找

LNode * LocateElem(LinkList L,ElemType e){
    LNode *p=L->next;
    while(p!=NULL&&p->data!=e)
        p=p->next;
    return p;
}

Ⅸ 求表长

int Length(LinkList L){
    int len=0;
    LNode *p=L;
    while(p->next!=NULL){
        p=p->next;
        len++;
    }
    return len;
}

Ⅹ 尾插法

LinkList List_TailInsert(LinkList &L){
    int x;
    L=(LinkList)malloc(sizeof(LNode));
    LNode *s,*r=L;
    scanf("%d",&x);
    while(x!=9999){
        s=(LNode *)malloc(sizeof(LNode));
        s->data=x;
        r->next=s;
        r=s;
        scanf("%d",&x);
    }
    r->next=NULL;
    return L;
}

Ⅺ 头插法

LinkList List_HeadInsert(LinkList &L){
    LNode *s;
    int x;
    L=(LinkList)malloc(sizrof(LNode));
    L->next=NULL;
    scanf("%d",&x);
    while(x!=9999){
        s=(LNode *)malloc(sizeof(LNode));
        s->data=x;
        s->next=L->next;
        L->next=s;
        scanf("%d",&x);
    }
    return L;
}

双链表

（1）定义

typedef struct DNode{
    ElemType data;
    struct DNode *prior,*next;
}DNode,*DLinkList;

bool InitDLinkList(DLinkList &L){
    L=(DNode *)malloc(sizeof(DNode));
    if(L==NULL)
        return false;
    L->prior=NULL;
    L->next=NULL;
    return true;
}

（2）基本操作

Ⅰ 判空操作

bool Empty(DlinkList L){
    if(L->next==NULL)
        return true;
    else
        return false;
}

Ⅱ 插入操作

bool InsertNextDNode(DNode *p,DNode *s){
    if(p==NULL||s==NULL)
        return false;
    s->next=p->next;
    if(p->next!=NULL)
    	p->next->prior=s;
    s->prior=p;
    p->next=s;
    return true;
}

Ⅲ 删除操作

// 删除p的后继结点
bool DeeleteNextDNode(DNode *p){
    if(p==NULL)
        return false;
    DNode *q=p->next;
    if(q==NULL)
        return false;
    p->next=q->next;
    if(q->next!=NULL)
        q->next->prior=p;
    free(q);
    return true;
}

// 删除链表
void DestoryList(DLinkList &L){
    while(L->next!=NULL)
        DeeleteNextDNode(L);
    free(L);
    L=NULL;
}

Ⅳ 遍历操作

// 后向遍历
while(p!=NULL){
    p=p->next;
}

// 前向遍历
while(p!=NULL){
    p=p->prior;
}

// 前向遍历（跳过头结点）
while(p->prior!=NULL){
    p=p->prior;
}

循环链表

循环单链表

（1）定义

typedef struct LNode{
    ElemType data;
    struct LNode *next;
}LNode,*LinkList;

bool InitList(LinkList &L){
    L=(LNode *)malloc(sizeof(LNode));
    if(L==NULL)
        return false;
    L->next=L;
    return true;
}

（2）基本操作

Ⅰ 判空操作

bool Empty(LinkList L){
    if(L->next==L)
        return true;
    else
        return false;
}

Ⅱ 是否表尾

bool isTail(LinkList L,LNode *p){
    if(p->next==L)        
        return true;
    else
        return false;
}

循环双链表

（1）定义

typedef struct DNode{
    ElemType data;
    struct DNode *prior,*next;
}DNode,*DlinkList;

bool InitDLinkList(DLinkList &L){
    L=(DNode *)malloc(sizeof(DNode));
    if(L==NULL)
        return false;
    L->prior=L;
    L->next=L;
    return true;
}

（2）基本操作

Ⅰ 判空操作

bool Empty(DLinkList L){
    if(L->next==L)
        return true;
    else
        return false;
}

Ⅱ 是否表尾

bool isTail(DLinkList L,DNode *p){
    if(p->next==L)
        return true;
    else
        return false;
}

Ⅲ 插入操作

bool InsertNextDNode(DNode *p,DNode *s){
    s->next=p->next;
    p->next->prior=s;
    s->prior=p;
    p->next=s;
}

Ⅳ 删除操作

bool DeeleteNextDNode(DNode *p){
    p->next=q->next;
    q->next->prior=p;
    free(q);
    return true;
}

静态链表

（1）定义

#define MaxSize 50
typedef struct Node{
    ElemType data;
    int next;
}SLinkList[MaxSize];

（2）基本操作

二、栈（Stack）

1、顺序栈

（1）定义

#define MaxSize 50
typedef struct{
    ElemType data[MaxSize];
    int top;
}SqStack;

void InitStack(SqStack &S){
    S.top=-1;// S.top=0
}

（2）基本操作

Ⅰ 判空操作

bool StackEmpty(SqStack S){
    if(S.top==-1)// S.top==0
        return true;
    else
        return false;
}

Ⅱ 入栈操作

bool Push(SqStack &S,ElemType x){
    if(S.top==MaxSize-1)// S.top==MaxSize
        return false;
    S.data[++S.top]=x;// S.data[S.top++]=x
    return true;
}

Ⅲ 出栈操作

bool Pop(SqStack &S,ElemType &x){
	if(S.top==-1)// S.top==0
        return false;
    x=S.data[S.top--];// x=S.data[S.top--]
    return true;
}

Ⅳ 读栈顶

bool GetTop(SqStack &S,ElemType &x){
	if(S.top==-1)
        return false;
    x=S.data[S.top];
    return true;
}

共享栈

2、链栈

（1）定义

typedef struct Linknode{
    ElemType data;
    struct Linknode *next;
}Linknode,*LiStack;

// 不带头节点
bool InitStack(LiStack &S){
    S=NULL;
    return true;
}

// 带头节点
bool InitStack(LiStack &S){
    S=(Linknode *)malloc(sizeof(Linknode));
    if(L==NULL)
        return false;
    L->next=NULL;
    return true;
}

（2）基本操作

Ⅰ 入栈操作

Ⅱ 出栈操作

Ⅲ 获取栈顶元素

Ⅳ 判空操作

Ⅴ 判满操作

三、队列

1、队列的顺序存储

（1）定义

#define MaxSize 10
typedef struct{
    ElemType data[MaxSize];
    int front,rear;
    // 1、int size;
    // 2、int tag;// 最近进行的是0：删除，1：插入
}SqQueue;

void InitQueue(SqQueue &Q){
    Q.rear=Q.front=0;
    // 1、Q.size=0;
    // 2、Q.tag=0;
}

（2）基本操作

Ⅰ 判空操作

bool QueueEmpty(SqQueue Q){
    if(Q.rear==Q.front)// 1、Q.size==0
        return true;
    else
        return false;
}

Ⅱ 入队操作（循环队列）

bool EnQueue(SqQueue &Q，ElemType x){
    if((Q.rear++1)%MaxSize==Q.front)// 1、Q.size==MaxSize;2、(Q.rear++1)%MaxSize==Q.front&&Q.tag==1;
        return false;
    Q.data[Q.rear]=x;
    Q.rear=(Q.rear+1)%MaxSize;
    // 1、Q.size++;
    // 2、Q.tag=1;
    return true;
}

Ⅲ 出队操作

bool DeQueue(SqQueue &Q,ElemType &x){
    if(Q.rear==Q.front)// 1、Q.size==0;2、(Q.rear++1)%MaxSize==Q.front&&Q.tag==0;
        return false;
    x=Q.data[Q.front];
    Q.front=(Q.front+1)%MaxSize;
    // 1、Q.size--;
    // 2、Q.tag=0;
    return true;
}

Ⅳ 获取队头元素

bool GetHead(SqQueue Q,ElemType &x){
    if(Q.rear==Q.front)
        return false;
    x=Q.data[Q.front];
    return true;
}

Ⅴ 队列元素个数

(rear+MaxSize-front)%MaxSize;

2、队列的链式存储

（1）定义

typedef struct LinkNode{
    ElemType data;
    struct LinkNode *next;
}LinkNode;

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

// 带头结点
void InitQueue(LinkQueue &Q){
    Q.front=Q.rear=(LinkNode *)malloc(sizeof(LinkNode));
    Q.front->next=NULL;
}

// 带头结点
void InitQueue(LinkQueue &Q){
    Q.front=NULL;
    Q.rear=NULL;
}

（2）基本操作

Ⅰ 判空操作

// 带头结点
bool isEmpty(LinkQueue Q){
    if(Q.front==Q.rear)
        return true;
    else
        return false;
}
// 不带头结点
bool IsEmpty(LinkQueue Q){
    if(Q.front==NULL)
        return true;
    else
        return false;
}

Ⅱ 入队操作

// 带头结点
void EnQueue(LinkQueue &Q,ElemType x){
    LinkNode *s=(LinkNode *)malloc(sizeof(LinkNode));
    s->data=x;
    s->next=NULL;
    Q.rear->next=s;
    Q.rear=s;
}

// 不带头结点
void EnQueue(LinkQueue &Q,ElemType x){
    LinkNode *s=(LinkNode *)malloc(sizeof(LinkNode));
    s->data=x;
    s->next=NULL;
    if(Q.front==NULL){
        Q,front=s;
        Q.rear=s;
    }else{
        Q.rear->neat=s;
        Q.rear=s;
    }
}

Ⅲ 出队操作

// 带头结点
bool DeQueue(LinkNode &Q,ElemType &x){
    if(Q.front==Q.rear)
        return false;
    LinkNode *p=Q.front->next;
    x=p->data;
    Q.front->next=p->next;
    if(Q.rear==p)
        Q.rear=Q.front;
    free(p);
    return true;
}

// 不带头结点
bool DeQueue(LinkNode &Q,ElemType &x){
    if(Q.front==Q.rear)
        return false;
    LinkNode *p=Q.front;
    x=p->data;
    Q.front=p->next;
    if(Q.rear==p){
        Q.rear=NULL;
        Q.front=NULL;
    }
    free(p);
    return true;
}

双端队列

四、串

1、串的顺序存储

（1）定义

#define MAXLEN 255
typedef struct{
    char ch[MAXLEN];
    int length;
}SString;

typedef struct{
    char *ch;
    int length;
}HString;
HString S;
S.ch=(char *)malloc(MAXLEN*sizeof(char));
S.length=0;

（2）基本操作

Ⅰ 求子串

bool SubString(SString &Sub,SString S,int pos,int len){
    if(pos+len-1>S.length)
        return false;
    for(int i=pos;i<pos+len;i++)
        Sub.ch[i-pos+1]=S.ch[i];
    Sun.length=len;
    return true;
}

Ⅱ 比较操作

// 若S>T，则返回值>0；若S<T，则返回值<0；若S=T，则返回值=0.
int StrCompare(SString S,SString T){
    for(int i=1;i<=S.length&&i<=T.length;i++){
        if(S.ch[i]!=T.ch[i])
            return S.ch[i]-T.ch[i];
    }
    return S.;ength-T.length;
}

Ⅲ 定位操作

int Index(SString S,SString T){
    int i=1,n=StrLength(S),m=StrLength(T);
    SString sub;
    while(i<=n-m+1){
        SubString(sub,S,i,m);
        if(StrCompare(sub,T)!=0)
            i++;
        else
            return i;
    }
    return 0;
}

（3）朴素模式匹配

int Index(SString S,SString T){
    int i=1,j=1;
    while(i<=S.length&& j<=T.length){
        if(S.ch[i]==T.ch[j]){
            i++;
            j++;
        }else{
            i=i-j+2;
            j=1;
        }
    }
    if(j>T.length)
        return i-T.length;
    else
    	return 0;
}

（4）KMP

void get_next(SString T,int next[]){
    int i=1,j=0;
    next[1]=0;
    while(i<T.length){
        if(j==0||T.ch[i]==T.ch[j]){
            i++;
            j++;
            next[i]=j;
        }else
            j=next[j];
    }
}

int Index_KMP(SString S,SString T){
    int i=1,j=1;
    int next[T.length+1];
    get_next(T,next);
    while(i<=S.length&&j<=T.length){
        if(j==0||S.ch[i]==T.ch[j]){
            i++;
            j++;
        }else
            j=next[j];
    }
    if(j>T.length)
        return i-T.length;
    else
        return 0;
}

（5）KMP的优化

// 伪代码
void get_nextval(SString T,int nextval[]){
    get_next();
    nextval[1]=0;
    for(int j=2;j<=T.length;j++){
        if(T.ch[next[j]]==T.ch[j])
            nextval[j]=nextval[next[j]];
        else
            nextval[j]=next[j];
    }
}

2、串的链式存储

（1）定义

typedef struct StringNode{
    char ch;
    struct StringNode *next;
}StringNode,* String;

typedef struct StringNode{
    char ch[4];
    struct StringNode *next;
}StringNode,* String;

五、树与二叉树

1、二叉树的顺序存储

（1）定义

#define MaxSize 100
struct TreeNode{
    ElemType value;
    bool isEmpty;
};

TreeNode t[MaxSize];

（2）基本操作

几个重要常考的基本操作

• i的左孩子 2i
• i的右孩子 2i+1
• i的父节点 i/2
• i所在的层次 log n+1

若完全二叉树中共有n个结点，则

• 判断i是否有左孩子？ 2i<=n
• 判断i是否有右孩子？ 2i+1<=n
• 判断i是否是叶子/分支结点 i>n/2

2、二叉树的链式存储

（1）定义

typedef struct BiTNode{
    ElemType data;
    struct BiTNode *lchild,*rchild;
    // struct BiTNode *parent;
}BiTNode,*BiTree;

BiTree root=NULL;

（2）基本操作

Ⅰ 插入根节点

root=(BiTree)malloc(sizeof(BiTNode));
root->data={1};
root->lchild=NULL;
root->rchild=NULL;

Ⅱ 插入新结点

BiTNode *p=(BiTNode *)malloc(sizeof(BiTNode));
p->data={2};
p->lchild=NULL;
p->rchild=NULL;
root->lchild=p;

Ⅲ 先序遍历

// 递归
void PreOrder(BiTree T){
    if(T!=NULL){
        visit(T);
        PreOrder(T->lchild);
        PreOrder(T->rchild);
    }
}

// 非递归
void PreOrder(BiTree T){
    InitStack(S);
    BiTree p=T;
    while(p||!isEmpty(S)){
        if(p){
            visit(p);
            Push(S,p);
            p=p->lchild;
        }else{
            Pop(S,p);
            p=p->rchild;
        }
    }
}

Ⅳ 中序遍历

// 递归
void InOrder(BiTree T){
    if(T!=NULL){
        PreOrder(T->lchild);
        visit(T);
        PreOrder(T->rchild);
    }
}

// 非递归
void InOrder(BiTree T){
    InitStack(S);
    BiTree p=T;
    while(p||!isEmpty(S)){
        if(p){
            Push(S,p);
            p=p->lchild;
        }else{
            Pop(S,p);
            visit(p);
            p=p->rchild;
        }
    }
}

Ⅴ 后序遍历

// 递归
void PostOrder(BiTree T){
    if(T!=NULL){
        PreOrder(T->lchild);
        PreOrder(T->rchild);
        visit(T);
    }
}

// 非递归
void PostOrder(BiTree T){
    InitStack(S);
    BiTree p=T,r=NULL;
    while(p||!isEmpty(S)){
        if(p){
            push(S,p);
        	p=p->lchild;
        }else{
            GetTop(S,p);
            if(p->rchild&&p->rchild!=r)
                p=p-<rchild;
            else{
                pop(S,p);
                visit(p->data);
            	r=p;
            	p=NULL;
            }
        }
    }
}

Ⅵ 层次遍历

void LevelOrder(BiTree T){
    LinkQueue Q;
    InitQueue(Q);
    BiTree p;
    EnQueue(Q,T);
    while(!IsEmpty(Q)){
        Dequeue(Q,p);
        visit(p);
        if(p->lchild!=NULL)
            EnQueue(Q,p->lchild);
        if(p->rchild!=NULL)
            EnQueue(Q,p->rchild);
    }
}

（3）中序前驱

BiTNode *p;           // 指向目标结点
BiTNode *pre=NULL;    // 指向当前访问结点的前驱
BiTNode *final=NULL;  // 用于记录最终结果

void visit(BiTNode *q){
    if(q==p)
        final=pre;
    else
        pre=q;
}

（4）线索二叉树

Ⅰ 中序线索化

typedef struct TreadNode{
    ElemType data;
    struct BiTNode *lchild,*rchild;
    int ltag,rtag;
}TreadNode,*TreadTree;

TreadNode *pre=NULL;

void visit(TreadNode *q){
    if(q->lchild==NULL){
        q->lchild=pre;
        q->lag=1;
    }
    if(pre!=NULL&&q->rchild==NULL){
        pre->rchild=q;
        pre->rag=1;
    }
    pre=q;
}

void InThread(TreadTree T){
    if(T!=NULL){
        PreOrder(T->lchild);
        visit(T);
        PreOrder(T->rchild);
    }
}

void CreateInThread(ThreadTree T){
    pre=NULL;
    if(T!=NULL){
        InThread(T);
        if(pre->rchild==NULL)
            pre->rtag=1;
    }
}

Ⅱ 先序线索化

typedef struct TreadNode{
    ElemType data;
    struct BiTNode *lchild,*rchild;
    int ltag,rtag;// 0:子节点；1:线索指针
}TreadNode,*TreadTree;

TreadNode *pre=NULL;

void visit(TreadNode *q){
    if(q->lchild==NULL){
        q->lchild=pre;
        q->lag=1;
    }
    if(pre!=NULL&&q->rchild==NULL){
        pre->rchild=q;
        pre->rag=1;
    }
    pre=q;
}

void PreThread(TreadTree T){
    if(T!=NULL){
        visit(T);
        if(T->ltag==0)           // !!!!!!!
        	PreOrder(T->lchild);
        PreOrder(T->rchild);
    }
}

void CreateInThread(ThreadTree T){
    pre=NULL;
    if(T!=NULL){
        InThread(T);
        if(pre->rchild==NULL)
            pre->rtag=1;
    }
}

Ⅲ 后序线索化

typedef struct TreadNode{
    ElemType data;
    struct BiTNode *lchild,*rchild;
    int ltag,rtag;
}TreadNode,*TreadTree;

TreadNode *pre=NULL;

void visit(TreadNode *q){
    if(q->lchild==NULL){
        q->lchild=pre;
        q->lag=1;
    }
    if(pre!=NULL&&q->rchild==NULL){
        pre->rchild=q;
        pre->rag=1;
    }
    pre=q;
}

void PostThread(TreadTree T){
    if(T!=NULL){
        PreOrder(T->lchild);
        PreOrder(T->rchild);
        visit(T);
    }
}

void CreateInThread(ThreadTree T){
    pre=NULL;
    if(T!=NULL){
        InThread(T);
        if(pre->rchild==NULL)
            pre->rtag=1;
    }
}

Ⅳ 中序线索二叉树找中序后继

// 找到以p为根的子树中，第一个被中序遍历的结点
ThreadNode *Firstnode(ThreadNode *p){
    while(p->ltag==0)
        p->lchild;
    return p;
}

// 在中序线索二叉树中找到结点p的后继结点
ThreadNode *Nextnode(ThreadNode *p){
    if(p->rtag==0)
        return Firstnode(p->rchild);
    else
        return p->rchild;
}

void InOrder(ThreadNode *T){
    for(ThreadNode *p=Firstnode(T);p!=NULL;p=Nextnode(p))
        visit(p);
}

Ⅴ 中序线索二叉树找中序前驱

// 找到以p为根的子树中，最后一个被中序遍历的结点
ThreadNode *Lastnode(ThreadNode *p){
    while(p->rtag==0)
        p->rchild;
    return p;
}

// 在中序线索二叉树中找到结点p的前驱结点
ThreadNode *Prenode(ThreadNode *p){
    if(p->ltag==0)
        return Lastnode(p->lchild);
    else
        return p->lchild;
}

// 对中序线索二叉树进行逆向中序遍历
void RevInOrder(ThreadNode *T){
    for(ThreadNode *p=Lastnode(T);p!=NULL;p=Prenode(p))
        visit(p);
}

3、树的双亲表示法

（1）定义

#define MAX_TREE_SIZE 100
typedef struct{
    ElemType data;
    int parent;
}PTNode;

typedef struct{
    PTNode nodes[MAX_TREE_SIZE];
    int n;
}PTree;

4、树的孩子表示法

（1）定义

struct CTNode{
    int child;
    struct CTNode *next;
};

typedef struct{
    ElemType data;
    struct CTNode *firstChild;
}CTBox;

typedef struct{
    CTBox nodes[MAX_TREE_SIZE];
    int n,r;  // 结点和根的位置
}CTree;

5、树的孩子兄弟表示法

（1）定义

typedef struct CSNode{
    ElemType data;
    struct CSNode *firstchild,*nextsibling;   // 第一个孩子和右兄弟指针
}CSNode,*CSTree;

6、树的遍历

（1）先根遍历

void PreOrder(TreeNode *R){
    if(R!=NULL){
        visit(R);
        while(R有下一个子树T)
            PreOrder(T);
    }
}

（2）后根遍历

void PostOrder(TreeNode *R){
    if(R!=NULL){
        while(R有下一个子树T)
            PostOrder(T);
        visit(R);
    }
}

（3）层次遍历（广度优先）

7、森林的遍历

（1）先序遍历

（2）中序遍历

8、树和森林的遍历与二叉树遍历的对应关系

树	森林	二叉树
先根遍历	先序遍历	先序遍历
后根遍历	中序遍历	中序遍历

9、二叉排序树（BST）

（1）定义

typedef struct BSTNode{
    int key;
    struct BSTNode *lchild,*rchild;
}BSTNode,*BSTree;

（2）基本操作

Ⅰ 查找操作

BSTNode *BST_Search(BSTree T,int key){
    while(T!=NULL&&key!=T->key){
        if(key<T->key)
            T=T->lchild;
        else
            T=T->rchild;
    }
    return T;
}

// 递归
BSTNode *BSTSearch(BSTree T,int key){
    if(T==NULL)
        return NULL;
    if(key==T->key)
        return T;
    else if(key<T->key)
        return BSTSearch(T->lchild,key);
    else
        return BSTSearch(T->rchild,key);
}

Ⅱ 插入操作

// 递归
int BSTInsert(BSTree &T,int k){
    if(T==NULL){
        T=(BSTree)malloc(sizeof(BSTNode));
        T->key=k;
        T->lchild=T->rchild=NULL;
        return 1;
    }else if(k==T->key)
        return 0;
    else if(k<T->key)
        return BSTInsert(T->lchild,k);
    else
        return BSTInsert(T->rchild,k);
}

Ⅲ 构造操作

void CreatBST(BSTree &T,int str[],int n){
    T=NULL;
    int i=0;
    while(i<n){
        BSTInsert(T,str[i]);
        i++;
    }
}

Ⅳ 删除操作

10、平衡二叉树（AVL）

（1）定义

typedef struct AVLNode{
    int key;
    int balance;
    struct AVLNode *lchild,*rchild;
}AVLNode,*AVLTree;

（2）调整最小不平衡子树

类型	方法
LL	A的左孩子结点右上旋
RR	A的右孩子结点左上旋
LR	A的左孩子的右孩子 先左上旋再右上旋
RL	A的右孩子的左孩子 先右上旋再左上旋

11、哈夫曼树（最优二叉树）

六、图

七、查找

八、排序