数据结构学习

数据结构概述

数据结构的定义

如何把现实生活中大量而且复杂的问题，以特定的数据类型和存储结构保存到主存储器（内存）中，为了实现某个功能而执行的相关操作，该操作称之为算法。

数据结构=个体+个体之间的关系，数据结构研究的是如何把个体以及个体之间的关系表示出来然后存进内存的过程。

算法是对数据结构的操作过程。

算法：

算法的定义：解题的方法和步骤

算法的衡量标准
时间复杂度：
算法所执行的大概次数而非时间；要看的是运行次数最多的步骤执行了多少次。
空间复杂度：
执行过程中大概占用的内存；
难易程度：
健壮性：

数据结构预备知识

指针

指针变量声明的时候需要指定指针所指地址中存储的数据类型，赋值的时候默认是该数据在内存中所占用第一个字节的地址，整个指针的范围是从该数据所占的第一个字节到数据的最后一个字节，即该数据类型的大小。

定义：
内存地址：内存单元的编号，是从0开始的非负整数；
指针：指针就是地址，地址就是指针；
指针变量：存放内存单元编号（地址或者指针）的变量；指针的本质是一个操作受限的非负整数。

指针是C语言的灵魂。

#include <stdio.h>
int main(void)
{
    int * p;  // int *  表明定义一个存储int类型变量的指针，p表示该指针的名字
    int i=10;
    int j;
    p=&i;//&i表示变量i的内存地址，复制该地址给p,此时p指向i,*p==i，*p就表示指向地址的值
    j=*p;//把指向地址的值赋值给j
    printf("i=%d,j=%d,*p=%d",i,j,*p);
    return 0;
    //p只存储地址，地址指向的值改变与其无关，p存储的地址改变也与地址里的值无关
}

指针与一维数组

a[i]==*(a+i)
a是数组，也是数组第一个数据的指针，指针加上中括号以及下标，表示获取该地址后移存储类型的i倍大小的地址存储的数据

数组名：
一维数组名是一个指针常量，存放的是数组里的第0个元素的地址，它的值不能被改变。
数组下标与指针关系：
a[i]==*(a+i)
a是指向第0个元素的地址，第i个元素的地址就为 a+(i乘以a地址里面的元素所占内存大小) ，a代表的第0个元素，所以第i个地址就要乘以相应的大小再相加

字节：硬件所能读取的最小单位，单位为B,1K=1024B

不同类型数据的大小不同，占的字节也就不同，同一个类型的数据所占的字节大小是固定的。而指针所指向的数据地址一般为数据所占的所有字节的第一个字节或者最后一个字节的地址。

int、long、float占四个字节 short战两个字节 double占八个字节

指针变量存放数据的地址，地址都是四个字节，所以指针变量都是四个字节大小。

指针的指针

声明指针相关的时候只需要看最后一个*号，该符号之前表示的是指针指向位置存储的数据类型。

//当定义一个变量的时候需要指定该变量的类型；
//声明一个指针的时候需要声明指针所指向数据的类型，即  int * p就是声明一个指针p，该指针指向的地址存储有一个int类型的数据；
//所以，当声明一个指针的指针的时候就需要指明该地址存储的是一个指针，即  int **p,该声明表示这个一个指针，该指针指向的地址存储的数据是一个指针；

结构体

结构体是用户根据实际需要自己定义的复合数据类型，自己定义的数据类型 。是Java中类的前身，但是结构体中没用方法，都是成员，成员类比属性。

struct Student 
{ 
int sid; 
char name[200]; 
int age; 
};//分号不能省 
//相当于声明一个新的变量，所以得加上分号

//使用方式
struct Student st={1000,”zhagnsan”,20}; 
struct Student*pst=&st;   //指针存储的是该数据类型里的第一个成员的地址，该数据类型为struct Student

info 提示块标签

malloc()函数的使用

malloc函数用于动态获取内存

int *p=(int *)malloc(sizeof(int)*5);

//该语句用于向操作系统申请5个整形数据大小的内存，即20个字节的内存；
//malloc函数返回的是申请的空间的第一个字节的地址，返回的地址是void *类型的因此需要类型转换为需要的数据类型；

普通函数使用过程的内存在函数结束之后就会自动释放，而通过malloc申请的内存不会自动释放，需要手动通过free函数就行释放

---

数据结构详解

数据结构分为线性结构和非线性结构。

线性结构

把所有结点用一根线串起来而定数据结构成为线性结构，线性结构的存储方式有顺序存储和离散存储两种。

顺序存储-数组

动态数组指针实现

//实现动态数组
#include <stdio.h>
#include<malloc.h>
#include "stdlib.h"
/*
 * 所有返回值1为真，0为假
 */
struct myarry{//定义数组结构体
    int size;//数组大小
    int * Arry;//数组地址
    int count;//数组数据个数
};
void init(struct myarry * myarry,int len){//初始化数组

 myarry->Arry=(int *)malloc(sizeof (int)*len);//动态分配数组内存
 if(myarry->Arry==NULL){
     printf("分配失败");
     exit(-1);
 } else{
     myarry->count=0;
     myarry->size=len;
 }
    return;
}
int isempty(struct myarry * myarry){//判断数组是否为空
    if(myarry->count==0){
        //printf("arry is null");
        return 1;
    } else
        return 0;
}

void show(struct myarry * myarry){//输出数组
if(isempty( myarry)==1){
    printf("arry is null");
    return;
} else{
    for(int i=0;i<myarry->count;++i){
        printf("%d",myarry->Arry[i]);//int *p, p[1]=*(p+1*sizeof(int))
    }
    printf("\n");
}
}

int isfull(struct myarry * myarry){//判断数组是否已满
    if(myarry->count==myarry->size)
        return 1;
    else
        return 0;
}

int append(struct myarry * myarry,int value){//追加数据
    if(isfull(myarry)==1){
        printf("arry is full,append fail");
        return 0;
    } else{
        myarry->Arry[(myarry->count)]=value;
        (myarry->count)++;
        return 1;
    }
}

int insert(struct myarry * myarry,int value,int position){//指定位置插入数据
    if(isfull(myarry)==1){
        printf("arry is full,insert fail");
        return 0;
    } else{
        if(position<0||position>myarry->size){
            printf("out of inedx for insert");
            return 0;
        }
        for(int i=myarry->count;i>=position;i--) {
                myarry->Arry[i]=myarry->Arry[i-1];
        }
        myarry->Arry[position]=value;
        (myarry->count)++;
        return 1;
    }
}

int delete(struct myarry * myarry,int position,int * value){//删除指定位置数据
    if(isempty(myarry)==1){
        printf("arry is null,delete fail");
        return 0;
    } else{
        if(position<0||position>myarry->size){
            printf("out of inedx for delete");
            return 0;
        }
        *value=myarry->Arry[position];
        for(int i=position;i<myarry->count;i++) {
            myarry->Arry[i]=myarry->Arry[i+1];
        }
        (myarry->count)--;
        return 1;
    }
}


int inversion(struct myarry * myarry){//数组数据反转
    if(isempty(myarry)==1){
        printf("arry is null,delete fail");
        return 0;
    } else{
        int i=0,j=myarry->count-1,temp;
        while (i<j){
            temp=myarry->Arry[i];
            myarry->Arry[i]=myarry->Arry[j];
            myarry->Arry[j]=temp;
            i++;
            j--;
        }
        return 0;
    }
}

int sort(struct myarry * myarry){//数组冒泡排序
    if(isempty(myarry)==1){
        printf("arry is null,delete fail");
        return 0;
    } else{
        int temp;
        for(int i=0;i<myarry->count;i++){
            for(int j=i+1;j<myarry->count;j++){
                if(myarry->Arry[i]>myarry->Arry[j]){
                    temp=myarry->Arry[i];
                    myarry->Arry[i]=myarry->Arry[j];
                    myarry->Arry[j]=temp;
                }
            }
        }
        return 1;
    }
}

int main(void) {
   struct myarry  myarry;
   int deletevalue;
   init(&myarry,6);
   //show(&myarry);
   append(&myarry,1);
   append(&myarry,2);
   append(&myarry,3);
   append(&myarry,4);
   append(&myarry,5);
   append(&myarry,6);
   delete(&myarry,2,&deletevalue);
    show(&myarry);
   insert(&myarry,100,2);
   show(&myarry);
   inversion(&myarry);
    show(&myarry);
    sort(&myarry);
    show(&myarry);
}

typedef的使用

typedef用于给已有的数据类型起一个别名。

typedef int myint;//给int类型起一个myint别名，后定义int类型数据可使用  myint i=0;
typedef int * myintpoint;//给int* 类型起一个myinpintt别名，后定义int*类型数据可使用  myintpoint i=&i;
typedef int * myintpoint,myint;//给int* 类型起一个myinpintt别名,给int类型起一个myint别名;

typedef struct Student{
    int id;
    int age;
}  mystudent;// 给该结构体数据类型起一个别名，后定义该类型数据可使用  mystudent student;
typedef struct Student{
    int id;
    int age;
} *  mystudentpoint;//给该结构体指针数据类型起一个别名，后定义该类型数据可使用  mystudentpoint studentpoint;
typedef struct Student{
    int id;
    int age;
} *  mystudentpoint,mystudent;//给该结构体指针数据类型起一个别名,给该结构体数据类型起一个别名

离散存储-链表

链表

链表的相关定义

定义：

• 离散存储的——n个节点离散分配
• 线性结构——节点之间通过指针相连；
• 每一个节点只有一个前驱结点和后继节点，除了首节点和尾节点，首节点为前驱，尾节点无后继；

首节点：链表中的第一个节点，也是第一个存放有效数据的节点；

尾节点:链表中最后一个存放有效数据节点；

头结点：首节点前面指向首节点的一个节点，不存放有效数据，头结点的作用主要是方便对链表的操作；头结点和首节点的数据类型相同。

头指针：指向头结点的指针变量

尾指针：指向尾节点的指针变量

当对一个链表进行操作的时候，需要的数据只有————头指针，通过头指针可以得到整个链表而定所有信息。

链表里的相关数据

链表里的每一个数据的数据类型是相同的，通常用结构体进行表示。

typedef struct  node{     //每一个链表数据由两部分组成，数据域和指针域
    int data;//数据域，用来存放有效数据
    struct node * pnext;//指针域，存放指向下一个数据的指针
} * pnode,node;  //给该数据类型起一个别名为node，该数据类型的指针类型别名为pnode

链表的分类

• 单向链表
• 双向链表——两个指针域分别指向前一个数据和后一个数据；
• 循环链表——首尾节点相连，能通过任何一个节点找到任意一个节点；
• 非循环链表

链表某一数据的插入和删除

在q之后插入p

//第一种方式，中间值互换
temp=q->pnext;
q->next=p;
p->next=temp;
//第二种方式，直接填入
p->pnext=q->pnext;
q->next=p;

删除q之后的数据

//最直观方法
q->pnext=q->pnext->pnext;
//该方法会造成内存泄漏，垃圾数据越来越多,因此需要释放删除数据的内存

temp=q->pnext;
q->pnext=q->pnext->pnext;
free(temp);
//释放temp指向地址的数据，即被删除的数据

链表的初始化

typedef struct node {
    int value;
    struct node * pnext;
} node,*pnode;//定义链表里的数据类型

pnode init(void){
    pnode phead=(pnode)malloc(sizeof (node));//分配头结点的内存空间
    if(phead==NULL){
        printf("init fail!!! ");
        exit(-1);
    }
    pnode plast=phead;
    plast->pnext=NULL;//定义声明尾指针，尾指针的指针域为NULL
    int number;
    int value;//接收每一个数据
    printf("enter your number:");
    scanf("%d",&number);
    for(int i=0;i<number;i++){
        printf("enter the NO %d:",i+1);
        scanf("%d",&value);
        pnode pnew=(pnode)malloc(sizeof (node));//为每一个有效节点分配内存
        if(phead==NULL){
            printf("init fail!!! ");
            exit(-1);
        }
        plast->pnext=pnew;
        pnew->value=value;
        pnew->pnext=NULL;//每一个新插入的有效节点都是尾节点，因此指向为NULL
        plast=pnew;//定义尾节点为新插入的节点
    }
    return phead;
}

链表的遍历

针对链表的遍历，只需要判断每一个数据的指针域是否为空即可遍历到最后一个节点。

typedef struct node {
    int value;
    struct node * pnext;
} node,*pnode;

void travelList(pnode phead){
    pnode  ptemp=phead->pnext;
    while (ptemp!=NULL){
        printf("%d\t",ptemp->value);
        ptemp=ptemp->pnext;
        i++;
    }
    printf("\n");
}

链表的排序

int len_list(pnode phead){//获得链表长度
    int i=0;
    pnode  ptemp=phead->pnext;
    while (ptemp!=NULL){
        ptemp=ptemp->pnext;
        i++;
    }
    return i;
}

void sort_list(pnode phead){
    int len=len_list(phead);//先获取长度
    int i,j,t;//定义循环条件初始值
    pnode  p,q;//定义循环条件初始值，把链表的排序与数组排序进行类比
    for( i=0,p=phead->pnext;i<len-1;i++,p=p->pnext){//首先定义初始值的数据，i=0,类比p=p->phead->pnext,首节点是第一个有效数据，即初始化为0；
        //i<len-1，定义循环结束条件，类比p->pnext!=NULL，当指针域为空时说明遍历到最后一个数据
        //i++,循环的循环条件，每次加一，类比p=p->pnext，指针挪到下一位
       for(j=i+1,q=p->pnext;j<=len-1;j++,q=q->pnext){//设置第二重遍历，j=i+1,第二重遍历开始条件是第一重的下一个，即类比指针挪到下一位，q=p->next;
           //设置循环结束条件，遍历条件，指向下一个
           if(p->value>q->value){//判断数据的大小，类比数组a[i]>a[j]
               t=p->value;//交换数据
               p->value=q->value;
               q->value=t;
           }
       }
    }
    
    
  //类比之后的写法
       for( p=phead->pnext;p!=NULL;p=p->pnext){
        for(q=p->pnext;q!=NULL;q=q->pnext){
            if(p->value>q->value){
                t=p->value;
                p->value=q->value;
                q->value=t;
            }
        }
    }
}

狭义上的算法与数据类型以及存储方式有关，广义上的算法与数据类型和存储方式无关；
广义的算法是思想上的，狭义算法是实现上的；
泛型定义：通过不同的技术达到某种效果——数据类型存储方式不同，操作却相同；

链表的插入

//在索引为position处插入一个数据
void insert(pnode phead,int position,int value){
    pnode p=phead;//设定索引P遍历，防止出现在索引0处插入数据，所以要从头结点开始
    int i=0;
    for(i;i<position,p->pnext!=NULL;i++)
    p=p->pnext;//向后遍历到要插入的索引前一个位置
    //指针P最开始位于头结点，因此遍历到插入索引的前一个位置需要执行position次
}
if(i>position||p->pnext==NUL){
    return 0;
}
pnode pnew=(pnode)malloc(sizeof(pnode));
if( pnew==NULL){
   printf("fail");
}
pnew->pnext=p->pnext;
pnew->value=value;
p->pnext=pnew;//若遍历从首节点开始则插入索引0的数据会插入到索引1

链表的删除

//与插入操作相同，遍历至索引前一个位置，将想要删除的索引位置的pnext传入到前一位置指针域即可，记得释放内存
void delete(pnode phead,int position,int * temp){//传入一个数据地址返回要删除的数据
    pnode p=phead;
    int i;
    for ( i = 0, p; i <position ; ++i) {
        p=p->pnext;
    }
    if(i>position||p->pnext==NUL){
    return 0;
}
   *temp=p->pnext->value;
    pnode pnode1=p->pnext;//得到要删除的数据地址释放内存
    p->pnext=p->pnext->pnext;
    free(pnode1);
}

栈

栈是一种特殊的线性数据结构，具有先进后出的特性。

栈分为静态栈和动态栈，静态栈基于数组实现，动态栈是基于链表实现的

静态栈

静态栈的实现靠数组
静态栈里面有两个数据，数组以及数组最顶部的数据索引，该索引指向最后一个数据的再后一个数据的位置，因此索引大小与数组数据的个数相等
初始化静态数组的时候没有数据，数据索引指向0号
当入栈的时候，向索引位置赋值，使索引加一
出栈时索引减一即可，当栈里面只有一个数据的时候，出栈后索引为就为-1，栈为空

动态栈的实现

//定义所存储的数据类型
typedef struct Node{
    int data;
    struct Node * pnext;
}node,* pnode;
//定义一个栈
//对于一个栈，要有两个基本节点ptop和pbottom
//1.pbottom指针始终指向最底部节点的下一个节点指针，类比链表的头指针，但是不存储任何有效数据，指针域为空，是为了方便链表操作
//2.ptop指针始终指向最顶部节点的指针，当两个指针都指向同一节点的时候说明栈为空
typedef struct stack{
    pnode  ptop;
    pnode pbottom;
}stack,*pstack;
//栈的初始化
int  init(pstack pstack){//栈的初始化主要是赋值给所需要的两个指针，初始时栈空，所以两个指针指向同一个节点
    pstack->pbottom=(pnode)malloc(sizeof (pnode));
    if( pstack->pbottom==NULL){
        printf("distribution fail!");
        return 0;
    }
    pstack->pbottom->pnext=NULL;
    pstack->ptop=pstack->pbottom;
    return 1;
}
//压栈/入栈
void push(pstack pstack,int value){//压栈只需要把新的数据的指针域指向原来的ptop，再把ptop的指向新加入的数据即可，新加入的数据永远在最顶部
    pnode pnew=(pnode)malloc(sizeof (pnode));
    pnew->pnext=pstack->ptop;
    pnew->data=value;
    pstack->ptop=pnew;
}
//出栈
int pop(pstack pstack,int* pvalue){//出栈即删除最顶部元素，只需要把顶部指针ptop指向下一个数据后释放原顶部数据内存即可
    if(pstack->ptop==pstack->pbottom){
        printf("delete fail,stack is null!");
        return 0;
    }
    pnode p=pstack->ptop;
    *pvalue=p->data;
    pstack->ptop=p->pnext;
    free(p);
    return 1;
}
//栈的遍历
void travel(pstack pstack){//栈的遍历即从顶部指针开始往下，遍历到底部指针即可
    pnode p=pstack->ptop;
    while (p!=pstack->pbottom){
        printf("%d\n",p->data);
        p=p->pnext;
    }
}
//栈的清空
int clear(pstack pstack){//栈的清空与遍历类似，但是每遍历一个数据都得释放内存，释放内存时会把地址所在内存全部清空，所以得在释放之前把下一个节点的数据保存，释放之后重新赋值到下个节点继续释放
    pnode p=pstack->ptop;
    pnode q=NULL;
    while (p!=pstack->pbottom){
     q=p->pnext;
     free(p);
     p=q;
    }
    pstack->ptop=pstack->pbottom;
    return 1;
}

队列

队列是一种先进先出的线性存储结构。

链式队列

静态队列

静态队列通常必须是循环队列，用数组实现

静态队列通常必须是循环队列
队列中使用front队列的出口，在队列中删除数据即出队只能从front出去，使用rear表示队列的入口，添加数据即入队则只能从rear口进入；
队列遵循先进先出，front永远指向第一个数据，rear指向最后一个数据位置的下一个位置，并且front与rear只能增不能减；
当向一个循环队列入队的时候，rear指向后移一位，索引加一，到达数组最大值时则回到第一位，当出队时，front指向加一。到达最大值时也回到第一位；
当一个循环队列的front与rear指向同一个位置时说明该循环队列为空；

静态队列实现思想

• 如何实现队列的插入——入队
  当队列入队的时候，参数rear则需要往后挪一位，由于需要实现循环，因此rear=(rear+1)%len,即加一对长度取余

• 如何实现队列的删除——出队
  当队列出队的时候，参数front则需要往后挪一位，由于需要实现循环，因此front=(front+1)%len,即加一对长度取余

• 判断队列是否为空
  当rear==front 的时候，队列为空；

当然，当一个循环队列rear==front时候，可能为空也可能是满的，这时候就需要判断。

• 判断队列是否已满

判断队列是否已满有两种方法：
1.添加一个参数存储队列的元素个数，当出队入队时进行相应的操作，当该参数与队列容量相等时队列已满
2.减少一个元素，当rear与front相邻的时候就认定该队列已满
(rear+1)%len==front则队列认为是满的，此时存储的有len-1个元素

静态队列实现

typedef struct Queue{//定义一个队列数据类型，一个数组加两个索引
    int *Pbase;
    int front;
    int rear;
}Queue,* Pqueue;

void init(Pqueue pqueue){//初始化队列，索引都为零
    pqueue->Pbase=(int)malloc(sizeof (int)*6);
    pqueue->front=0;
    pqueue->rear=0;
}

int isfull(Pqueue pqueue){//判断是否为空——front索引是否在rear后一位
    if(pqueue->front==(pqueue->rear+1)%6){
        return 1;
    } else
        return 0;
}

int input_queue(Pqueue pqueue,int value){//入队操作，数据传入rear索引位置，rear加一
    if(isfull(pqueue)) {
        printf("queue is full!\n");
        return 0; }
    pqueue->Pbase[pqueue->rear]=value;
    pqueue->rear=(pqueue->rear+1)%6;
    printf("input success!\n");
    return 1;
}

int output_queue(Pqueue pqueue,int* pvalue){//出队操作，front加一
    if(pqueue->front==pqueue->rear)
    {
        printf("queue is empty!");
        return 0;
    }
    *pvalue=pqueue->Pbase[pqueue->front];
    pqueue->front=(pqueue->front+1)%6;
    return 1;
}

void travle_list(Pqueue pqueue){//遍历操作，从front遍历到rear前一位
    int i=pqueue->front;
    while (i!=pqueue->rear){
        printf("%d\n",pqueue->Pbase[i]);
        i++;
    }
}

函数的调用

当在一个函数的运行期间调用另一个函数时，在运行被调函数之前，系统需要完成三件事：
1.将所有的实际参数，返回地址等信息传递给被调函数保存
2.为被调函数的局部变量（也包括形参）分配存储空间
3.将控制转移到被调函数的入口

从被调函数返回主调函数之前，系统也要完成三件事
1.保存被调函数的返回结果
2.释放被调函数所占的存储空间
3.依照被调函数保存的返回地址将控制转移到调用函数

当有多个函数相互调用时，按照“后调用先返回”的原则，上述函数之 间信息传递和控制转移必须借助”栈”来实现，即系统将整个程序运行时所需的数据空间安排在一个栈中，
每当调用一个函数时，就在栈顶分配一个存储区，进行压栈操作，每当一个函数退出时，就释放它的存储 区，就行出栈操作，当前运行的函数永远都在栈顶位置.

非线性结构

树

树的定义

专业定义：
1、有且只有一个称为根的节点；
2、有若干个互不相交的子树，这些子树本身也是一棵树； 即整个树的构成依赖于子树，子树构成又依赖于子树的子树；

通俗的定义：
1、树是由节点和边组成；
2、每一个节点都只有一个父节点，但是有多个子节点；
3、根节点没有父节点；

相关属性：

• 深度： 根节点到最底层节点的层数，根节点所在层数是第一层；
• **度：**树中子节点最多的节点的子节点个数；
• **叶子节点：**没有子节点的节点；当只有一个根节点的时候根节点也是叶子节点；
• 非终端节点（非叶子节点）：不是叶子节点的节点，当根节点有子节点的时候就是非叶子节点；

树的分类

• 一般树
• 二叉树： 树中包含的各个节点的度不能超过 2，即只能是 0、1 或者 2；且子节点的顺序不可更改；
• **森林：**n个不相交的树的集合；

二叉树分类

• 完全二叉树： 如果二叉树中除去最后一层节点为满二叉树，且最后一层的结点依次从左到右分布，则此二叉树被称为完全二叉树。
• 满二叉树： 如果二叉树中除了叶子结点，每个结点的度都为 2，则此二叉树称为满二叉树。

树的存储

二叉树的存储：

**顺序存储：**顺序存储必须把二叉树转换为完全二叉树，采用数组进行存储，存储树的数据，通过转化为完全二叉树来存储树的结构。最后达到通过存储的顺序结构就能够得到树的整体结构；

优点：可以迅速的查找某个节点的父节点和子节点；

缺点：占用内存过大；

**链式存储：**指针域指向子节点地址即可

树的存储表示：

双亲表示法：在数组中，数据的指针域指向父节点数据的索引；

孩子表示法：在数组中，数据的指针域指向子节点数据的链表表示；

双亲孩子表示法：两个指针域分别指向父节点和子节点；

**二叉树表示法(孩子兄弟表示法）：需要先将树装换为二叉树，在进行存储表示；
转换方法：从根节点开始，左子节点指向第一个子节点，右子节点指向第一个兄弟节点； 转换的二叉树都没有右子树；

二叉树遍历

先序遍历

针对一个二叉树，首先访问根节点，再访问根节点的左节点，最后访问根节点的右节点，访问中遇到的每一个节点都需要先访问对应子树的根节点，子树的左节点，子树的右节点；

先序遍历二叉树为： A-B-D-E-H-C-F-G-J

中序遍历

对于一个二叉树，首先访问左节点，再访问根节点，最后访问子节点，中途的每一个节点都需要按照左-中-右的顺序访问；

中序遍历二叉树为：D-B-H-E-A-F-C-G-J

后序遍历

对于一个二叉树，首先访问左节点，再访问右节点，最后访问根节点，中途每个节点的访问顺序相同；

后序遍历二叉树为：D-H-E-B-F-J-G-C-A

所谓的前中后就是在哪一个位置放根节点，前序首先访问根节点，中序中间访问，后序最后访问；

遍历的程序实现

//首先定义每个节点的数据类型，链表实现，两个指针域分别指向左右子节点
typedef struct Btree{
    int data;
    struct Btree * Lchildern;
    struct Btree * Rchildern;
}Btree,* pbtree;

//初始化二叉树，没有子节点的左右子节点的指向为空
pbtree init(void ){
    pbtree p1=(pbtree)malloc(sizeof (struct Btree));
    pbtree p2=(pbtree)malloc(sizeof (struct Btree));
    pbtree p3=(pbtree)malloc(sizeof (struct Btree));
    pbtree p4=(pbtree)malloc(sizeof (struct Btree));
    pbtree p5=(pbtree)malloc(sizeof (struct Btree));
    p1->data=1;
    p2->data=2;
    p3->data=3;
    p4->data=4;
    p5->data=5;
    p1->Lchildern=p2;
    p1->Rchildern=p4;
    p2->Lchildern=NULL;
    p2->Rchildern=p3;
    p3->Lchildern=NULL;
    p3->Rchildern=NULL;
    p4->Lchildern=NULL;
    p4->Rchildern=p5;
    p5->Lchildern=NULL;
    p5->Rchildern=NULL;
    return p1;
}


//开始二叉树的遍历，递归实现，一直查找到某个节点没有左右节点即叶子节点，输出该节点即可，节点输出顺序不同则方式不同；
void travel(pbtree p){
    if(p!=NULL){
        printf("%d",p->data);//先序遍历输出根节点数据
        if(p->Lchildern!=NULL)//左子树不为空则开始遍历
            travel(p->Lchildern);
        //printf("%d",p->data);//中序遍历输出
        if(p->Rchildern!=NULL)//右子树不为空则开始遍历
            travel(p->Rchildern);
        //printf("%d",p->data);后序遍历输出
    }
}