【郝斌】-数据结构入门

数据结构概述：

定义：如何把现实中大量而复杂的问题以特定的数据类型（个体）和特定的数据结构（个体之间关系）保存到储存器（内存）中，并在此基础上为实现某个功能（比如查找/删除/排序）而执行的相应操作（又叫算法）。

常见数据结构：

链表

树

图（任意节点都和其它节点联系

数据结构=个体+个体的关系

算法=对存储数据的操作

算法（解题的方法和步骤

衡量算法的标准

1.时间复杂度

大概需要执行的次数（非时间）（机器计算能力的不同

2.空间复杂度

算法执行过程中大概所占用的最大内存

3.难易程度（可读性

4.健壮性（输入非法时也能做出正确反应

数据结构的地位：软件中最核心的课程

程序=数据的存储+数据的操作+可以被计算机执行的语言

预备知识：

指针

定义：

地址：

内存单元的编号（从0开始的非负整数

范围：0—FFFFFFFF（4G-1的内存大小

指针：指针《==》地址

指针变量是存放内存单元地址的变量

指针的本质是一个操作受限的非负整数

分类：

1.基本类型的指针

2.

注意：1.指针变量只能存放内存单元地址，而非内容

void f(int *p)//定义了一个形参，名字叫P，类型为int*；

a[3]=*(3+a);

printf("%p\n"，a+3) 16进制输出，等价于输出该对应地址 printf("%p/n",*a+3) <==>输出a[0]+3这个数对应的地址

***：指针变量不论指向的变量占多少字节，本身只占四个。

结构体:

为什么会出现结构体：为了表示某些复杂的数据，而普通的基本类型变量无法满足需求

什么是结构体：用户根据实际需要自行定义的复合数据类型

如何使用结构体

struct stduent

{

}；

int main()

{

struct student st={ , , };

}

int main()

{

struct student *pst=&st;

pst->sid=99;(等价于 （*pst)。sid ，pst所指向的结构体变量中的sid这个成员

}

注意事项

结构体变量不能加减乘除，只能相互赋值；

普通结构体变量和结构体指针变量作为函数传参的问题

例：

int main()

{

gst(st);

gst1(&st);

}

void g(struct studenct st)

{

……；

}

void g1(struct studenct *st)

{

……；

}

将主函数中的所有东西全部赋值到函数g中，浪费空间和内存，没有使用指针g1方便

动态内存的分配与释放：

动态构建一维数组：

int main ()

{

int len;

scanf("%d"，&len);

int *pArr=(int *)malloc(sizeof(int) *len);

//(int *):强制转换 动态数组第一个字节地址（干地址，无实际意义），以确定数组的类型（即所占地址/字节数

free(pArr);//把pArr所代表的动态分配的内存释放；

}

**跨函数申请内存只能通过动态申请内存实现（但是要记得释放）

例：

#include <stdio.h>

int main()

{

int *p;

fun(&p);

}

int fun(int **q)

{

*q= (int *) malloc (sizeof(int));

}

模块一：线性结构【把所有的结点（类似于数组的元素）用一根直线穿起来】

连续储存【数组】

1.什么叫数组：

元素类型相同，大小相等

2.数组的优缺点（与链表相比较）：

优：①：存取速度快（可通过下标查找

缺：①事先必须知道数组的长度

②：插入删除元素慢

③容易受到空间的限制

④：需要大块连续的内存块

样例

#include <stdio.h>

#include <stdlib.h>//包含exit函数

#include <malloc.h>//包含malloc函数

//定义了一个数据类型，该数据类型名字叫struct Arr，该数据类型含有三个成员，分别是*pbase……，没有定义变量

struct Arr

{

int *pBase;//存储数组元素中第一个元素的地址

int len;//数组所能容纳的最多元素的个数

int cnt;//当前数组有效元素的个数

};

void init_arr(struct Arr *pArr,int length);初始化

bool append_arr(struct Arr *pArr,int val);//追加(注意数组满了不能放入）

bool insert_arr(struct Arr *pArr,int pos;int val);//插入到第pos个数 ,pos的值从1开始 表示下标为0的

bool delete_arr(struct Arr *pArr,int pos;int val);

int get();

bool is_empty(strcut Arr *pArr);//判数组是否为空

bool is_full();//判断数组是否满了

void sort_arr(strcut Arr *pArr);//排序

void show_arr(strcut Arr *pArr);//输出

void inversion_arr(strcut Arr *pArr);//倒置

find_val_arr();

deleteAll(4);

int main()

{

struct Arr arr;//粗体只是定义数据类型，此时数组内元素为垃圾值，定义arr才是变量

int val;

init_arr(&arr,6);//

show_arr(&arr);

append(&arr,1);

if (delete_arr(&arr,1,&val))

printf("删除成功！\n");

return 0;

}

void init_arr(struct Arr *pArr,int length)

{

pArr->pBase=(int *) malloc(sizeof(int)*length);

//判断分配地址是否成功

if (NULL ==pAee->pBase)

{

//内存分布失败

exit(-1);

}

array.len=99;

}

void show_arr(strcut Arr *pArr)

{

if is_empty(pArr）//此处pArr已经是arr地址，不可以加取地址符使得另一函数调用现在的*pArr的地址

printf("是空数组\n“);

else for (int i=0;i<=pArr->cnt;i++)

{

pritnf("%d ", pArr->pBase[i]);

}

printf("\n");

}

bool is_empty(strcut Arr *pArr)

{

if (pArr->cnt==0)

return 1;//true

else return 0;//false

}

bool is_full(struct Arr *pArr)

{

if (pArr->cnt==pArr->len)

return 1;//true

else return 0;//false

}

bool append_arr(struct Arr *pArr,int val)

{

if (is_full(pArr)==1)

return 0;//数组满了false

else //不满时追加

{

pArr->pBase[pArr->cnt]=val;

（pArr->cnt）++；

return true;

}

}

bool insert_arr(struct Arr *pArr,int pos;int val)

{

if (is->full(pArr))

return false;

if (pos<1||pos>=pArr->cnt+1)//超出容量

return false;

for (i=pArr->cnt-1;i>=pos-1;i--);

{

pArr->pBase[i]=pArr->pBase[i+1];

}

pArr->pBase[pos-1]=val;

return 1;//true

}

bool delete_arr(struct Arr *pArr,int pos;int *pVal);

{

if (is_empty(pArr))

return 0;//false

if (pos<1||pos>pArr->cnt)

return 0;//false

???//*pVal=pArr->pBase[pos-1];//删除成功时返回被删除的数据 以便撤回

for (i=pos;i<pArr->cnt;i++)

{

pArr->pBase[i]=pArr->pBase[i-1];

}

pArr->cnt --;

}

void inversion_arr(strcut Arr *pArr);//倒置

{

int i=0;

int j=pArr->cnt-1;

while (i<j)

{

t=pArr->pBase[j];

pArr->pBase[i]=pArr->pBase[j];

i++;

j--;

}

}

void sort_arr(st ruct Arr*pArr)(冒泡）

{

int i，j，t ;

for (i=0; i<pArr->cnt ; ++i)

{

for (j=i+1; j<pArr->cnt ; ++j)

{

if (pArr->pBase[i] > pArr->pBaso[j])

{

t = pArr->pBase[i] ;

pArr-> pBase[i]=pArr>pBase[j];

pArr->pBase[j][ = t ;

}

}

}

离散存储【链表】

# include <stdio. h>

typedef int ZHANGSAN; //为int再重新多取一个名字，ZHANGSAN等价于int

typedef struct Student

{

int sid;

char name [100] ;

char sex;

}ST;//除ST外相当于已有的一个数据类型（类似int

ST是为该数据类型重新取得名字

int main(void)

{

int i =10; //等价于 ZHANGSANi=10;

ZHANGSAN j=20;

printf("%d\n", j);

struct Student st ;

struct Student *ps = st ;return 0;

}

若ST换成*PST

一直到*位置都是一个数据类型 使得PST成为指针

typedef struct Student

{

int sid;

char name [100] ;

char sex;

}*PST;

int main(void)

{

struct Student st ;

PST ps=&st;

ps->sid=99;

}

若PSTU后跟上STU

typedef struct Student

{

int sid;

char name [100] ;

char sex;

}*PSTU，STU；//等价ST代表struct student,

PST代表struct Student*

int main(void)

{

STU st ;

PSTU ps=&st;

ps->sid=99;

}

离散存储（链表）

离散：各个结点之间有可以被计算出的间距

定义：①n个节点离散分配②彼此通过指针相连③每个节点有且只有一个前驱和后继节点，首无前驱，尾无后驱）

优点：①空间没有限制②插入删除元素快

缺点：存取数据速度慢

专业术语：

有效节点:存放有效数据的节点

首节点：第一个有效节点

尾节点：最后一个有效节点

头结点：链表中在首节点前加一个没有有效数据的节点，主要是方便对链表的操作，其数据类型和首节点一致

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

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

如果希望通过一个函数来对链表进行处理，我们至少需要知道链表的哪些参数：

头指针 ***（通过头指针可以推算出链表的其他所有信息

（不是头结点 是因为避免操作时结点内数据较多

（首节点非必须，可由头节点退出；

长度非必须，可以通过循环查找结点为NULL时的结点 ++即为长度）

链表的创建

#include <stdio.h>

#include <stdlib.h> 

#include <malloc.h>

typedef struct Node

{

  int data;//数据域

  struct Node *pNext;//指针域

}NODE,*PNODE; 

//NODE 等价于struct Node,PNODE 等价于struct Node*

PNODE create_list(void);

void traverse_list(PNODE pHead);//遍历

bool is_empty(PNODE pHead);

int length_list(PNODE pHead);

void sort_list(PNODE pHead); 

bool delete_list(PNODE pHead,int pos,int *pval);

bool insert_list(PNODE pHead,int pos,int val);

int main()

{  

  int val;

  PNODE pHead = NULL; 

  //等价于struct Node * pHead = NULL;

  pHead = create_list(); //功能：创建一个非循环单链表,将该链表的头结点地址赋值给pHead

  traverse_list (pHead) ;//遍历

  insert_list(pHead,4,-33);//

  if (is_empty(pHead))

    printf("链表为空\n");

  else printf("链表不空\n");

  int len=length_list(pHead);;

  printf("链表的长度是%d\n",len);

  traverse_list(pHead);//遍历

  sort_list(pHead);//排序

  traverse_list(pHead);//检验遍历是否成功

  if (delete_list(pHead,4,&val) )

    printf("删除成功，您删除的元素是:%d\n", val) ;

  else

    printf("删除失败!您删除的元素不存在\n") ;

  return 0;

}

PNODE create_list()

{

    int len;///提示输入链表的长度

    int i;

    int val;//临时存放用户输入节点的值

    //分配一个不存放有效数据的头节点

    PNODE pHead =(PNODE)malloc (sizeof(NODE));

    if (NULL==pHead)

    {

      printf("分配失败\n");

      exit(-1);

    }

    PNODE pTail = pHead;

    pTail->pNext = NULL;//在用户输入0时清空指针域避免出现问题

    printf("输入链表的节点个数:len=");

    scanf("%d",&len);

    printf("\n");

    for (i=0;i<len;i++)

    {

      printf("请输入第%d个节点的值：",i+1); 

      scanf("%d",&val);

      PNODE pNew =(PNODE)malloc (sizeof(NODE));

      if (NULL==pNew)

      {

        printf("分配失败\n");

        exit(-1);

      }

      //使得pnew永远指向尾节点

      pNew->data = val;

      pTail->pNext =pNew;

      pNew->pNext = NULL;

      pTail = pNew;

    }

    return pHead;

}

void traverse_list(PNODE pHead)//遍历

{

  //定义指针p，指向头结点指针域（第一个有效节点），非空则继续，空则输出  

  PNODE p=pHead->pNext;

  while (p!=NULL)

  {

    printf("%d ",p->data);

    p=p->pNext;

  }

  printf("\n");

}

bool is_empty(PNODE pHead)

{

  if (pHead->pNext==NULL)

    return 1;

  else return 0; 

}

int length_list(PNODE pHead)

{

    PNODE p=pHead->pNext;

    int len=0;

    while (NULL!=p)

    {

      len++;

      p=p->pNext; 

    }

    return len;

}

void sort_list(PNODE pHead)

{

  int i,j,t;

  int len= length_list(pHead);

  PNODE p,q;

  for (i=0,p=pHead->pNext;i<len-1;i++,p=p->pNext)

    for (j=i+1,q=p->pNext;j<len;++j,q=q->pNext)

    {

      if (p->data > q->data)

      //类似于数组中的: a[i] > a[j]

      {

        t=p->data; //类似于数组中的t =a[i];

        p->data = q->data;//类似数组中a[i] = a[j]   

q->data = t;

      } 

    }  

}

bool insert_list(PNODE pHead,int pos,int val)//插入

{

    int i = 0;

    PNODE p = pHead;  

    while (NULL!=p && i<pos-1)

    {

      p=p->pNext;

      i++;

    }

    if (i>pos-1 || NULL==p)

      return 0;

    PNODE pNew=(PNODE)malloc(sizeof(NODE)) ;      

    if(NULL ==pNew)

    {

       printf("动态分配内存失败!\n");

       exit(-1) ;

    }

    pNew->data=val;

    PNODE q=p->pNext;

    p->pNext=pNew;

    pNew->pNext=q;

    return 1;

}

bool delete_list(PNODE pHead,int pos,int *pVal)

{

    int i = 0;

    PNODE p = pHead ;  

    while (NULL!=p->pNext && i<pos-1)

    {

      p=p->pNext;

      i++;

    }

    if (i>pos-1 || NULL==p->pNext)

      return 0;

    PNODE q = p->pNext ;

    *pVal =q->data;

    //删除p节点后面的结点

    p->pNext = p->pNext->pNext ;

    free(q) ;

    q= NULL;

    return 1;

}

链表的分类:

单链表

双链表：每个节点有两个指针域，且最后一个节点指针域不指向第一个节点

循环链表：最后一个节点的指针域指向了第一个节点

非循环链表：

算法：

狄义的算法是与数据的存数方式密切相关

广义的算法是与数据的存储方式无关

泛型:

利用某种技术达到的效果款是:不同的存数方式，执行的操作是一样的

遍历

查找

清空

销毁

求长度

排序

删除节点

插入节点

伪算法

①：插入

错误：（p->pNext= q;q->pNext = p->pNext)

//单纯的检索不到原来p后面的节点

正确：定义一临时指针r来指向p后面的节点

(r=p->pNext;p->pNext= q;q->pNext = r;)

(q->pNext=p->pNext;p->pNext=q;)

②：删除(p所指的后一个节点

错误：(p->pNext= p->pNext->pNext ) //内存未释放 使得电脑内存被占用

正确：定义一临时指针r来指向p后面的节点

（r=p->pNext;p->pNext=r->pNext;free(r);)

③：

线性结构的两种常见应用：

1.栈

定义：一种可以实现”先进后出“的存储结构

分类：

静态栈：从下往上存放0123 只能依次从上往下删除3210

动态栈 从下往上存放0123 可以通过最上面的元素删除3210中任意的

算法

出栈

入栈（压栈）

应用

函数调用

中断

表达式求值（2个栈做计算器

内存分配

缓冲处理

迷宫

栈的建立：

#include <stdio.h>

#include <malloc.h>

#include <stdlib. h>

typedef struct Node

{

int data;

struct Node *pNext ;

}NODE,*PNODE;

typedef struct Stack

{

PNODE pTop; //指向栈顶

PNODE pBottom ;//指向栈底

}STACK,*PSTACK;

void init(PSTACK ps)

{

pS->pTop(PNODE)malloc(sizoof(NODE));

if(NULL == pS->pTop)

{

printf(”动态内存分配失败!\n");

exit (-1);

}

else

{

pS->pBottom= ps-> pTop;

pS->pTop->pNext = NULL;

//等价于pS->Bottom->pNext = NULL;

}

}

void push(PSTACK S,int val)

{

PNODE pNew=(PNODE)malloc(sizoof(NODE));

pNew->data = val ;

pNew->pNext =pS->pTop;

//pS->Top不能改成pS->Bottom

ps->pTop = pNew;

return ;

}

void traverse(PSTACK pS)

{

PNODE p = pS->pTop; .

while (p != pS->pBottom)

{

printf ("%d",p->data) ;

p=p->pNext;

}

printf("\n");

return;

}

//把ps所指向的栈出栈一次，并把出栈的元素存入pVal形参所指向的变量中，如果出栈失败返回0（即栈为空），否则返回1

bool empty(PSTACK pS)

{

if (pS->pTop==pS->pBottom)

return 1;

else return 0;

}

//把ps所指向的栈出栈一次并把出栈的元素存入pval所指向的变量中，如果出栈成功返回true，否则false

bool pop(PSTACK pS，int * pVal)

{

if(empty(pS))//pS本身存放的就是S的地址

return 0;

else

{

PNODE r = pS->pTop;

*pVal=r->data;

pS->gTop = r->pNext ;

free(r) ;

r = NULL;

return 1;|

}

}

void clear(PSTACK PS）//只是删除栈中所有数据

{

if (empty(pS))

return;

else

{

PNODE p= pS->pTop;

PNODE q = NULL;

while (p != pS->pBottom)

{

q = p->pNext;

free(p);

p=q;

}

pS->pTop = pS->pBottom;

}

}

int main(void)

{

STACK S;

init(&S);//创建空栈 写S地址才能改变它的值

push(&S,1);//入栈

push(&S,2);//入栈

traverse(&S);//遍历输出

if (pop(&S,&val))

{

printf("出栈成功 出栈元素是%d\n",val);

}

else printf("出栈失败\n");

clear("&S");

traverse(&S);

}

2.队列：

定义：可以满足先进先出的一种存储结构

分类：链式队列（链表

静态队列（数组

静态队列通常必须是循环队列

循环队列的讲解:

1.静态队列为什么必须是循环队列

溢出时回到头

2.循环队列需要几个参数来确定及其含义

需要2个参数来确定

front

rear

2个参数不同场合有不同的含义建议初学者先记住，然后慢慢体会

1)．队列初始化

front 和rear的值都是0

2)．队列非空

front代表的是队列的第一个元素

rear代表的是队列的最后一个有效元素的下一个元素

3)﹒队列空

front和rear的值相等，但不一定是0

3.循环队列各个参数的含义（2已经讲完

4.循环队列入队伪算法讲解

①将值存入r所代表的位置

②r=(r+1)%数组长度

5.循环队列出队伪算法讲解

①f=(f+1)%数组长度（自己判断是否要创建一个val来存储出队的数据）

6.如何判断循环队列是否为空

front=rear

7.如何判断循环队列是否已满

预备知识：front和rear的值大小关系不确定，可大可小可相等

判断方法：

常用：少用一个元素，如果fr紧挨则队列已满

不常用：多增加一个标识参数，长度等于数组长度或者r和f重合时

if((r+1)%数组长度==f) 满;

else 不满

3.队列的具体应用：所有和时间有关的操作

循环队列程序演示

#include <stdio.h>

#include <malloc.h>

struct Queue

{

int * pBase;

int front;

int rear;

}QUEUE;

void init_queue(QUEUE *pQ);//初始化

bool full_queue (QUEUE * pQ)

{

if ( (pQ->rear + 1)% 6 == pQ->front )

return true;

else

return false;

}

bool en_queue(QUEUE *pQ,int val);//入队

{

if ( full_queue (pQ) )

{

return false;

}

else

{

pQ->pBase [pQ->rear] = val;

pQ->rear = (pQ->rear+1)%6 ;

return true;

}

}

bool emput_queue(QUEUE *pQ)

{

if (pQ->front==pQ->rear)

return 1;

else return 0;

}

bool out_queue(QUEUE *pQ,int *pVal)

{

if (emput_queue(pQ))

return 0;

else

{

*pVal = pQ->pBase[pQ->front] ;

pQ->front = (pQ->front+1)%6;

return 1

}

}

void tarverse_queue(QUEUE *pQ)

{

int i=pQ->front;

while (i!=pQ->rear)

{

printf("%d ",pQ->Base[i]);

i=(i+1)%6;

}

}

int main(viod)

{

int val;

QUEUE Q;

init(&Q);

en_queue(&Q,1);

en_queue(&Q,2);

en_queue(&Q,3);

en_queue(&Q,4);

en_queue(&Q,5);

en_queue(&Q,6);

traverse_queue(&Q);

if (out_queue(&Q,&val))

{

printf("出队成功，出队元素是：%d\n“，val;

}

else printf("出队失败\n");

return 0;

}

3.递归：

定义：

一个函数直接或者间接的调用自己

直接：f套f 间接：f套g g套f

递归满足三个条件:

1、递归必须得有一个明确的中止条件

2、该函数所处理的数据规模必须在递减

3、这个转化必须是可解的

循环和递归

递归:

易于理解

速度慢

存储空间大

循环：

不易理解

速度快

存储空间小

注意事项：

当在一个函数的运行期间调用另一个函数时，在运行被调函数之前，系统需要完成三件事:

1.将所有的实际参数,返回地址等信息传递给被调函数保存

2为被调函数的局部变量(也包括形参)分配存储空间

3.将控制转移到被调函数的入口

从被调函数返回主调函数之前，系统也要完成三件事:

1.保存被调函数的返回结果

2释放被调函数所占的存储空间

3.依照被调函数保存的返回地址将控制转移到调用函数

应用：

①、高斯求和

②、阶乘

③、汉诺塔

④、走迷宫

模块二：非线性结构

树

专业定义

1.有且仅有一个根节点

2.有若干个互不相交的子树，这些子树本身也是一棵树

通俗定义：

1.树由节点和边（指针域）组成

2.每个节点只有一个父节点但可以有多个子节点（除根节点无父节点

树的专业术语：

深度:

从根节点到最底层节点的层数称之为深度

根节点是第一层

叶子节点:

没有子节点的节点

非终端节点

实陈就是非叶子节点

度

子节点的个数称为度

树的分类

一般树：任意一个节点的子节点个数都不受限制

二叉树：任意一个节点的子节点最多两个，且子节点的位置不可更改

二叉树的分类

一般二叉树

满二叉树

在不增加树的层数的前提下，无法再增加一个节点的二叉树是满二叉树

完全二叉树

如果只删除了满二叉树最底层最右边的连续若干个节点，这样形成的二叉树是完全二叉树

森林：n个互不相交的树的集合

树的存储

二叉树的存储

连续存储【完全二叉树】

由于先中后三种树的转化方式都无法重新推到出树并且不一致，只能补足

优点：查找某个节点的父节点和子节点（也包括判断有没有

缺点： 耗内存过大

链式存储：

一般树的存储：（无序

双亲表示法

求父节点方便

孩子表示法

求子节点方便

双亲孩子表示法

集以上两种的特长，缺点是编程麻烦

二叉树表示法

把一个普通树转化成二叉树来存储

具体转换方法:

设法保证任意一个节点的左指针域指向它的第一个孩子，右指针域指向它的兄弟

满足此条件，就可以把一个普通树转化为二叉树

森林的存储

先把森林转化为二叉树，再存储二叉树

二叉树的操作

遍历

先序遍历

先访问根节点

再先序访问左子树

先序访问右子树

中序遍历

中序遍历左子树

再访问根节点

再中序遍历右子树

后序遍历[最后访问根节点]

先中序诎历左子树

再中序遍历右子树

再访问根节点

已知两种遍历序列求原始二叉树

通过先序和中序或者中序和后序我们可以 还原出原始的二叉树

但是通过先序和后序是无法还原出原始的二叉树的

先序中序求树技巧

①先序第一个为根节点

②中序中的字母在先序中先出现的为那层的根节点

后序中序求树技巧

①后序最后一个为根节点

②中序中的字母在后序中后出现的为那层的根节点

应用

树是数据库中数据组织一种重要形式

操作系统子父进程的关系本身就是一糅树

面向对象语言中类的维承关系

赫夫曼树

二叉链表的创建(如图

#include <stdio.h>

struct BTNode

{

int dat a;

struct BTNode * pLchild; / /p是指针 L是左 child是孩子

struct BTNode * pRchild;

}

int main(void)

{

struct BTNode * pT = CreateBTree(void) ;

//先中后序遍历

PreTraverseBTree(pT)；

InTraverseBTree(pT);

PostTraverseBTree(pT) ;

return 0;

}

struct BTNode *CreateBTree(void)

{

struct BTNode * pA= (struct BTNode *)malloc(sizeof (struct BTNode));

struct BTNode * pB= (struct BTNode *)malloc(sizeof (struct BTNode));

struct BTNode * pC= (struct BTNode *)malloc(sizeof (struct BTNode));

struct BTNode * pD= (struct BTNode *)malloc(sizeof (struct BTNode));

struct BTNode * pE= (struct BTNode *)malloc(sizeof (struct BTNode));

pA->data = 'A'；

pB->data =‘B’；

pC->data = 'C'；

pD->data = 'D'；

pE->data = ’E’；

pA-> pLchild = pB;

pA->pRchild = pC;

pB-> pLchild = pB-> pRchild = NULL;

pC->pLchild = pD;

pC->pRchild = NULL;

pD->pLchild = NULL;

pD-> pRchild = pE;

pE->pLchild = pE->pRchild=NULL;

return pA ;

}

void PreTraverseBTree(strcut BTNode * PT)；

{

if (pT!=NULL)

{

printf("%c\n",pT->data);

if(NULL != pT-> pLchild)

PreTraverseBTree(pT->pLchild);

if(NULL != pT-> pRchild)

PreTraverseBTree(pT->pRchiid):

}

//pT->pLchild可以代表整个左子树

/*伪算法

先访问根节点

再先序访问左子树

再先序访问右子树*/

}

void InTraverseBTree(struct BTNode * pT)

if (NULL != pT)

{..

if (NULL != pT->pLchild)

InTraverseBree(pT->pLchild) ;

printf("%c\n"，pT->data);

if (NULL != pT->pRchild){

InTraverseBTree(pT->pRchild) :1/pT->pLchild可以代表整个左子树

}

图

{

数据库

字段：反映事物的属性

记录：一个整体的事务

表：同一类事物的集合

}