迪丽热巴全身图片:数据结构教程8

第二十一课

本课主题： 树、二叉树定义及术语

教学目的： 掌握树、二叉树的基本概念和术语，二叉树的性质

教学重点： 二叉树的定义、二叉树的性质

教学难点： 二叉树的性质

授课内容：

一、树的定义：

树是n(n>=0)个结点的有限集。在任意一棵非空树中：

(1)有且仅有一个特定的称为根的结点；

(2)当n>1时,其余结点可分为m(m>0)个互不相交的有限集T1,T2,...Tm,其中每一个集合本身又是一棵树,并且称为根的子树.

二、树的基本概念：

树的结点包含一个数据元素及若干指向其子树的分支。

结点拥有的子树数称为结点的度。

度为0的结点称为叶子或终端结点。

度不为0的结点称为非终端结点或分支结点。

树的度是树内各结点的度的最大值。

结点的子树的根称为该结点的孩子，相应地，该结点称为孩子的双亲。

同一个双亲的孩子之间互称兄弟。

结点的祖先是从根到该结点所经分支上的所有结点。

以某结点为根的子树中的任一结点都称为该结点的子孙。

结点的层次从根开始定义起，根为第一层，根的孩子为第二层。其双亲在同一层的结点互为堂兄弟。树中结点的最大层次称为树的深度，或高度。

如果将树中结点的各子树看成从左至右是有次序的，则称该树为有序树，否则称为无序树。

森林是m(m>=0)棵互不相交的树的集合。

三、二叉树的定义

二叉树是另一种树型结构，它的特点是每个结点至多只有二棵子树（即二叉树中不存在度大于2的结点),并且,二叉树的子树有左右之分,其次序不能任意颠倒。

一棵深度为k且有2(k)-1个结点的二叉树称为满二叉树，如图(a)，按图示给每个结点编号，如果有深度为k的，有n个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应时，称之为完全二叉树。

二叉树的定义如下：

ADT BinaryTree{

数据对象D:D是具有相同特性的数据元素的集合。

数据关系R:

基本操作P:

InitBiTree(&T);

DestroyBiTree(&T);

CreateBiTree(&T,definition);

ClearBiTree(&T);

BiTreeEmpty(T);

BiTreeDepth(T);

Root(T);

Value(T,e);

Assign(T,&e,value);

Parent(T,e);

LeftChild(T,e);

RightChild(T,e);

LeftSibling(T,e);

RightSibling(T,e);

InsertChild(T,p,LR,c);

DeleteChild(T,p,LR);

PreOrderTraverse(T,visit());

InOrderTraverse(T,visit());

PostOrderTraverse(T,visit());

LevelOrderTraverse(T,Visit());

}ADT BinaryTree

三、二叉树的性质

性质１：

在二叉树的第i层上至多有2的i-1次方个结点(i>=1)。

性质２：

深度为k的二叉树至多有2的k次方减1个结点(k>=1)。

性质３：

对任何一棵二叉树T，如果其终端结点数为n0,度为2的结点数为n2,则n0=n2+1。

性质４：

具有n个结点的完全二叉树的深度为|log2n|+1

性质５：

如果对一棵有n个结点的完全二叉树的结点按层序编号，则对任一结点i(1=(1)如果i=1,则结点i是二叉树的根,无双亲;如果i>1,则双亲PARENT(i)是结点i/2
(2)如果2i>n,则结点i无左孩子(结点i为叶子结点);否则其左孩子LCHILD(i)是结点2i
(3)如果2i+1>n,则结点i无右孩子;否则其右孩子RCHILD(i)是结点2i+1

四、总结

回目录 上一课 下一课

第二十二课

本课主题： 实验五 数组实验

教学目的： 掌握二维数组的实现方法

教学重点： 二维数组的存储表示,二维数组的基本操作

教学难点： 二维数组的基本操作

授课内容：

数组的顺序存储表示和实现:

#include

#define MAX_ARRAY_DIM 8

typedef struct {

ElemType *base;

int dim;

int *bounds;

int *constants;

}Array;

Status InitArray(Array &A,int dim,...);

Status DestroyArray(Array &A);

Status Value(Array A,ElemType &e,...);

Status Assign(Array &A,ElemType e,...);

基本操作的算法描述:

Status InitArray(Array &A,int dim,...){

if(dim<1||dim>MAX_ARRAY_DIM) return ERROR;

A.dim=dim;

A.bounds=(int *)malloc(dim *sizeof(int));

if(!A.bounds) exit(OVERFLOW);

elemtotal=1;

va_start(ap,dim);

for(i=1;i

A.bounds[i]=va_arg(ap,int);

if(A.bounds[i]<0) return UNDERFLOW;

elemtotal*=A.bounds[i];

}

va_end(ap);

A.base=(ElemType *)malloc(elemtotal*sizeof(ElemType));

if(!A.base) exit(OVERFLOW);

A.constants=(int *)malloc(dim*sizeof(int));

if(!A.constants) exit(OVERFLOW);

A.constants[dim-1]=1;

for(i=dim-2;i>=0;--i)

A.constants[i]=A.bounds[i+1]*A.constants[i+1];

return OK;

}

Status DestoyArray(Array &A){

if(!A.base) return ERROR;

free(A.base); A.base=NULL;

if !(A.bounds) return ERROR;

free(A.bounds); A.bounds=NULL;

if!(A.constatns) return ERROR;

free(A.constants); A.constants=NULL;

return OK;

}

Status Locate(Array A,va_list ap,int &off){

off=0;

for(i=0;i

ind=va_arg(ap,int);

if(ind<0||ind>=A.bounds[i]) return OVERFLOW;

off+=A.constants[i]*ind;

}

return OK;

}

Status Value(Array A,ElemType &e,...){

va_start(ap,e);

if((result=Locate(A,ap,off))<=0 return result;

e=*(A.base+off);

return OK;

}

Status Assign(Array &A,ElemType e,...){

va_start(ap,e);

if((result=Locate(A,ap,off))<=0) return result;

*(A.base+off)=e;

return OK;

}

回目录 上一课 下一课

第二十三课

本课主题： 二叉树的存储结构

教学目的： 掌握二叉树的两种存储结构

教学重点： 链式存储结构

教学难点： 链式存储二叉树的基本操作

授课内容：

一、复习二叉树的定义

二叉树的基本特征：每个结点的度不大于２。

二、顺序存储结构

#define MAX_TREE_SIZE 100

typedef TElemType SqBiTree[MAX_TREE_SIZE];

SqBiTree bt;

结点编号

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

结点值

1

2

3

4

5

0

0

0

0

6

7

0

0

0

0

第i号结点的左右孩子一定保存在第2i及2i+1号单元中。

缺点：对非完全二叉树而言，浪费存储空间

三、链式存储结构

一个二叉树的结点至少保存三种信息：数据元素、左孩子位置、右孩子位置

对应地，链式存储二叉树的结点至少包含三个域：数据域、左、右指针域。

也可以在结点中加上指向父结点的指针域P。

对结点有二个指针域的存储方式有以下表示方法：

typedef struct BiTNode{

TElemType data;

struct BitNode *lchild,*rchild;

}BiTNode,*BiTree;

基于该存储结构的二叉树基本操作有：

Status CreteBiTree(BiTree &T);

//按先序次序输入二叉树中结点的值（一个字符），空格字符表示空树，

//构造二叉链表表示的二叉树T。

Status PreOrderTraverse(BiTree T,Status(*Visit)(TElemType e));

//采用二叉链表存储结构,Visit是对结点操作的应用函数

//先序遍历二叉树T,对每个结点调用函数Visit一次且仅一次

//一旦visit()失败,则操作失败

Status InOrderTraverse(BiTree T,Status(*Visit)(TElemType e));

//采用二叉链表存储结构,Visit是对结点操作的应用函数

//中序遍历二叉树T,对每个结点调用函数Visit一次且仅一次

//一旦visit()失败,则操作失败

Status PostOrderTraverse(BiTree T,Status(*Visit)(TElemType e));

//采用二叉链表存储结构,Visit是对结点操作的应用函数

//后序遍历二叉树T,对每个结点调用函数Visit一次且仅一次

//一旦visit()失败,则操作失败

Status LevelOrderTraverse(BiTree T,Status(*Visit)(TElemType e));

//采用二叉链表存储结构,Visit是对结点操作的应用函数

//层序遍历二叉树T,对每个结点调用函数Visit一次且仅一次

//一旦visit()失败,则操作失败

四、总结本课内容

顺序存储与链式存储的优缺点。