计算机软件技术基础-课件 06ch3(1)-DS

线性结构（线性表、栈、队、串、数组）数据结构逻辑结构物理（存储）结构数据运算非线性结构树结构图结构顺序结构链式结构插入运算删除运算修改运算查找运算排序运算数据结构课程的内容第三章非线性结构3.1树和二叉树

3.1.1树的定义和基本术语

3.1.2树的存储结构

3.1.3二叉树定义和性质 3.1.4二叉树的存储与实现

3.1.5二叉树的遍历

3.1.6树、森林和二叉树的转换3.2图

3.2.1图的定义和基本概念 3.2.2图的存储结构 3.2.3图的遍历非线性结构★非线性结构：至少存在一个数据元素有两个或两个以上的直接前驱（或直接后继）元素的数据结构。★树型结构、图型结构。树形结构,用于描述层次结构的关系。图型结构,用于描述网状结构的关系。3.1树（

Tree）和二叉树3.1.1树的定义和基本术语3.1.2树的存储结构3.1.3二叉树定义和性质3.1.4二叉树的存储与实现3.1.5二叉树的遍历3.1.6树、森林和二叉树的转换特点：

非线性结构，一个直接前驱，但可能有多个直接后继（1：n）,是具有层次关系的数据结构，又是一种递归结构。 3.1.1树的定义和基本术语

1、树的定义

定义：树(Tree)是n(n>=0)个结点的有限集T当n＝0时，T称为空树；当n>0时，它必须满足如下两个条件：（1）有且仅有一个特定的称为根(Root)的结点；（2）其余的结点可分为m(m>=0)个互不相交的子集T1,T2,T3…Tm，其中每个子集又是一棵树，并称其为子树(Subtree)。注：树的定义具有递归性，即“树中还有树”。树的定义：n（n0）个结点的有限集合。

A

C

G

T2D

H

I

T3J

M

B

E

L

KT1

F3.1.1树的定义和基本术语例某校学生档案管理的组织方式3.1.1树的定义和基本术语树形结构——结点间具有分层次的连接关系3.1.1树的定义和基本术语树形结构——结点间具有分层次的连接关系

总理

国防部

总统

司法部

体育部

内政部…国家警察总局巴黎分局国家宪兵法国的警察机构结点（Node）： 树中的元素，包含数据项及若干指向其子树的分支。根，即根结点(没有前驱)2.树的基本术语结点的度（Degree）：结点拥有的子树数。树的度：树中各结点的度的最大值。叶结点（Leaf）：度为零的结点，也称终端结点（没有后继）。分枝结点：度不为0的结点，也称非终端结点（除了根节点外，也称内部结点）。问：右上图中的结点数＝；树的度＝；133ABCGEIDHFJFLK子结点：一个结点的直接后继。

父结点：一个结点的直接前驱。2.树的基本术语兄弟结点：同一父结点的子结点之间。祖先结点：从根结点到该结点所经分支上的所有结点。子孙结点：以一个结点为根的子树中的任一结点称为该结点的子孙结点。ABCGEIDHFJFLK结点的层次：从根结点到该结点的层数。根结点层次为1；其余结点层次等于其父结点的层次加1。2.树的基本术语树的深度（高度）：树中结点的最大层次。有序树：在树T中，各子树之间有先后次序。森林(Forest)：m(m>=0)棵互不相交的树的集合。问：右上图中树的深度＝4ABCGEIDHFJFLK3.树的基本操作1)建立一空树：Initree()

2)创建树CreatTree(T,规则)3)判断树是否为空：IsEmptyTree(T)

4)求树的深度：DepthTree(T)

5)求树T的树根结点：RootTree(T,x)6)求树T中结点p的父结点：ParentTree(T,p)7)求树T中结点p的最左边的子结点：LeftChild(T,p)树的基本操作8)求树T中结点p的最右边的子结点：RightChild(T,p)9)按某种方式遍历树T：TraverseTree(T)3.1.2树的存储结构讨论1：树是非线性结构，该怎样存储？

——顺序存储、链式存储?

1、树的逻辑结构特点：一对多（1:n），有多个直接后继（如家谱树、目录树等等），但只有一个根结点，且子树之间互不相交。

2、树的物理结构2、树的物理结构1．)子结点表示法也称树的标准形式存储结构。每一个结点用包含一个结点信息域和多个（指向该结点子结点的）指针域的结构来表示各指针域反映树中结点与结点之间的关系。子结点表示法的结点结构图结点信息子结点1子结点2…子结点m树的子结点表示法的结构图ATBC^^^DEFGHIJ^^K^^^1．)子结点表示法

如何安排指针域的个数？每个结点的指针域个数有两种设置方法：(1)等于该结点的度。(2)等于树的度。2．)父结点表示法结点信息父结点父结点表示法的结点结构图树的父结点表示的结构图A^BCDEFGHIJKT树的示例

树的逆形式存储结构。树中每一个结点用包含一个结点信息域和一个指向该结点父结点的指针域来表示。左图所示的树的父结点表示法如右图所示。3.)子结点兄弟结点表示法子结点兄弟结点表示法的结点结构图A^B^CD^^E^F^G^^H^IJ^^K^对树中结点用包含该结点的信息域、一个指向该结点第一个子结点的指针域和一个指向其下一个兄弟结点的指针域来表示。子结点兄弟结点表示法的结点结构图结点信息指向子结点的指针指向下一个兄弟结点指针树的示例

研究意义：二叉树的结构最简单，规律性最强，算法操作简单；任何树都可以转为唯一对应的二叉树；解决了树的存储结构及其运算中存在的复杂性。二叉树(BinaryTree)二叉树(BinaryTree)3.1.3二叉树定义和性质3.1.4二叉树的存储与实现3.1.5二叉树的遍历3.1.6树、森林和二叉树的转换3.1.3二叉树定义和性质定义：是n（n≥0）个结点的有限集合，该集合或为空、或由一个根结点以及两棵互不相交的、分别称为左子树和右子树的二叉树组成。逻辑结构：

一对二（1：2）

基本特征:①每个结点最多只有两棵子树（不存在度大于2的结点）；②左子树和右子树次序不能颠倒（有序树）。1.二叉树的定义二叉树的五种基本形态空二叉树仅有根结点右子树为空左子树为空左右子树均非空3.1.3二叉树定义和性质基本形态：3.1.3二叉树定义和性质问：具有3个结点的二叉树可能有几种不同形态？

有5种。树与二叉树的区别：A．树中结点的最大度数没有限制，二叉树结点最大度数为2。B．树的结点子树无左、右之分，二叉树的结点子树有明确的

左、右之分。

二叉树树2.二叉树的性质性质1

二叉树的第i层上至多有2i-1（i

1）个结点。423167891011121314155第三层上(i=3)，有23-1=4个节点。第四层上(i=4)，有24-1=8个节点。2.二叉树的性质(3+2)性质2

深度为k的二叉树中至多含有2k-1个结点。此树的深度h=4，共有24-1=15个结点。2.二叉树的性质(3+2)深度为k的二叉树的最大的结点数为二叉树中每层上的最大结点数之和，由性质1得到每层上的最大结点数：20+21+22+……+2k-1=2k-1423167891011121314155性质3

对于任意一棵非空二叉树，如果叶子结点数为n0，度为2的点有n2个，则有n0=n2+1n0=8n2=72.二叉树的性质(3+2)物理意义：叶子数＝2度结点数＋1423167891011121314155性质3

对于任意一棵非空二叉树，如果叶子结点数为n0，度为2的点有n2个，则有n0=n2+12.二叉树的性质(3+2)证明：1、二叉树中全部结点数n＝n0+n1+n2

(叶子数＋1度结点数＋2度结点数)2、二叉树中的分支数，除根结点外，其余结点都有一个进入分支，设B为二叉树中的分支总数，则有：n＝B＋1。3、而分支总数

B=n1+2n2

(1度结点必有1个直接后继，2度结点必有2个)三式联立可得：n0+n1+n2=

n1+2n2+1,即n0=n2+13.二叉树的分类满二叉树一棵深度为k且有2k-1个结点的二叉树。

（特点：每层都“充满”了结点）AOBCGEKDJFIHNML深度为4的满二叉树2）完全二叉树如果深度为k、有n个结点的二叉树，按层编号，如果编号为i(1≤i≤

n)的结点与深度为k的顺序编号的满二叉树中编号为i的结点相对应，则称这样的二叉树为完全二叉树A深度为4的完全二叉树BCGEIDHFJ满二叉树和完全二叉树有什么区别？答：满二叉树是叶子一个也不少的树，而完全二叉树虽然前k-1层是满的，但最底层却允许在右边缺少连续若干个结点。满二叉树是完全二叉树的一个特例。2.二叉树的性质(3+2)对于两种特殊形式的二叉树（满二叉树和完全二叉树），还特别具备以下2个性质：性质4：具有n个结点的完全二叉树的深度为

log2n＋1符号

X表示不大于x的最大整数。假设此二叉树的深度为k，则根据性质2及完全二叉树的定义得到：2k-1－1<n≤2k-1或2k-1≤n<2k取对数得到：k－1≤log2n<k

因为k是整数。所以有：k＝

log2n

＋1。4231678910

11125

完全二叉树性质5

对于具有n个结点的完全二叉树，如果按照从上到下和从左到右的顺序对二叉树中的所有结点从1开始顺序编号，则对于任意的序号为i的结点有：（3）如i＝1，则序号为i的结点是根结点，无父结点；如i>1，则序号为i的结点的父结点序号为

i/2；（1）如(2×i)>n，则序号为i的结点无左子结点；如(2×i)≤n，则序号为i的结点的左子结点的序号为2×i；（2）如(2×i＋1)>n，则序号为i的结点无右子结点；如(2×i＋1)≤n，则序号为i的结点的右孩子结点的序号为2×i+1；2.二叉树的性质(3+2)一、顺序存储结构按二叉树的结点“自上而下、从左至右”编号，用一组连续的存储单元存储。ABCDEFGHI[1][2][3][4][5][6][7][8][9]ABCGEIDHF问：顺序存储后能否复原成唯一对应的二叉树形状？答：若是完全/满二叉树则可以做到唯一复原。而且有规律：下标值为i的父结点，其左子结点的下标值必为2i，其右孩子的下标值必为2i＋1（即性质5）。

例如，对应[2]的两个孩子必为[4]和[5]，即B的左孩子必是D，右孩子必为E。T[0]一般不用3.1.4二叉树的存储与实现顺序存储结构的描述:#defineMAXNODE100//二叉树的最大结点数TypedefElemTypeSqBiTree[MAXNODE]

//0号单元存放根结点SqBiTree bt;

//将bt定义为含有MAXNODE个ElemType类型元素的一维数组。讨论：不是完全二叉树怎么办？答：一律转为完全二叉树！方法很简单，将各层空缺处统统补上“虚结点”，其内容为空。AB^C^^^D^…E[1][2][3][4][5][6][7][8][9]…[16]ABECD缺点：①浪费空间；②插入、删除不便；二、链式存储结构用二叉链表即可方便表示，每个结点由数据域、左子结点域和右子结点域组成。一般从根结点开始存储。

（相应地，访问树中结点时也只能从根开始）datalchildrchilddataleft_childright_childlchildDatarchildA^DB^C^^E^^F^一般二叉树的二叉链表结构AECBDF二、链式存储结构二叉树链式存储举例：^AB^D^C^^E^优点：①不浪费空间；②插入、删除方便

ABECD二叉树结点数据类型定义：typedefcharElemType;typedefstructbitnode{ElemTypedata;

//数据域

structbitnode

*lchild;//左指针域

structbitnode*rchild;//右指针域}BiTNode,*BiTree;

BiTNode*BT;//定义BT为指向BiTNode类型的指针注：如果需要查询某结点的父结点?如何实现可以再增加一个指向父结点的指针域（直接前驱），将二叉链表变成三叉链表。二、链式存储结构方法二(三叉链表)：每个结点由数据域、左子结点域、右子结点域和父结点域组成。lchildDataParentrchildA^^DB^C^^E^^F^一般二叉树的三叉链表结构AECBDF二、链式存储结构三、二叉树的基本操作3.1.5二叉树的遍历定义：按某条搜索路径遍访树中的每一个结点，使得每一个结点均被访问一次，而且仅被访问一次。用途：是树结构插入、删除、修改、查找和排序运算的前提，是二叉树一切运算的基础和核心。方法：寻找一种规律，以便使二叉树上的结点能排列在一个线性队列上，从而便于遍历。对每个结点的查看通常都是“先左后右”。遍历规则———二叉树由根、左子树、右子树构成，定义为D、L、RD:processingtheDataofthenode;L:traversingtheLeftsubtreeR:traversingtheRightsubtree注：“先、中、后”的意思是指访问结点的D是先于子树出现还是后于子树出现。

D、L、R的组合定义了六种可能的遍历方案：LDR,LRD,DLR,DRL,RDL,RLD

若限定先左后右，则有三种实现方案：

DLRLDRLRD先(根)序遍历中(根)序遍历后(根)序遍历1遍历二叉树的递归实现例1：先序遍历的结果是：中序遍历的结果是：后序遍历的结果是：ABDE

CFDBEAFCDEB

FCA口诀：DLR—先序遍历，即先根再左再右LDR—中序遍历，即先左再根再右LRD—后序遍历，即先左再右再根

ABCDEF二叉树的二叉链表存储用C语言描述如下：typedefstructbinode{ElemTypedata;structbinode*lchild;*rchild;//左右子结点指针}BiTNode;

1遍历二叉树的递归实现BiTNode*BT;//定义BT为指向BiTree类型的指针

1)先序遍历(DLR)

先序遍历的递归过程为：若二叉树为空，遍历结束。否则，

(1)访问根结点；

(2)先序遍历根结点的左子树；

(3)先序遍历根结点的右子树。算法如下：voidPreOrder(BiTNode*bt){//先序遍历二叉树btif(bt!=NULL) {visit(bt->data);//访问结点的数据域

PreOrder(bt->lchild);//先序递归遍历bt的左子树

PreOrder(bt->rchild);//先序递归遍历bt的右子树 }}1遍历二叉树的递归实现算法如下：voidInOrder(BiTNode*bt){//中序遍历二叉树btif(bt!=NULL){

InOrder(bt->lchild);//中序递归遍历bt的左子树visit(bt->data);//访问结点的数据域

InOrder(bt->rchild);//中序递归遍历bt的右子树}}1遍历二叉树的递归实现

2)中序遍历(LDR)

中序遍历的递归过程为：若二叉树为空，遍历结束。否则，

(1)中序遍历根结点的左子树；

(2)访问根结点；

(3)中序遍历根结点的右子树。

算法如下：voidPostOrder(BiTNode*bt){//后序遍历二叉树btif(bt!=NULL){

PostOrder(bt->lchild);//后序递归遍历bt的左子树

PostOrder(bt->rchild);//后序递归遍历bt的右子树visit(bt->data);//访问结点的数据域 }}1遍历二叉树的递归实现3)后序遍历(LRD)

后序遍历的递归过程为：若二叉树为空，遍历结束。否则，

(1)后序遍历根结点的左子树；

(2)后序遍历根结点的右子树。

(3)访问根结点；1遍历二叉树的递归实现问题：怎样从顶部开始逐层输出二叉树结点数据?（即按ABCDEF顺序来遍历，二叉树的层次遍历）先序遍历的结果是：中序遍历的结果是：后序遍历的结果是：ABDECFDBEAFCDEBFCA

ABCDEF采用队列结构。遍历从二叉树的根结点开始，首先将根结点指针入队列，然后从队头取出一个元素，每取一个元素，执行下面两个操作：(1)访问该元素所指结点；(2)若该元素所指结点的左、右子结点非空，则将该元素所指结点的左子结点指针和右子结点指针顺序入队。此过程不断进行，当队列为空时，二叉树的层次遍历结束。在层次遍历算法中，二叉树以二叉链表存放，一维数组Queue[MAXNODE]用以实现队列，变量front和rear分别表示当前队首元素和队尾元素在数组中的位置。2二叉树的层次遍历

所谓二叉树的层次遍历，是指从二叉树的第一层(根结点)开始，从上到下逐层遍历，在同一层中，则按从左到右的顺序对结点逐个访问。

ABCDEFvoidLevelOrder(BiTNode*bt)//层次遍历二叉树bt{BiTNode

*Queue[MAXNODE];intfront,rear;if(bt==NULL)return;

front=-1;rear=-1;rear++;Queue[rear]=bt;while(front!=rear){front++;visit(Queue[front]->data);//访问队首结点的数据域

if(Queue[front]->lchild!=NULL)

//将队首结点的左子结点入队列

{rear++;Queue[rear]=Queue[front]->lchild;}

if(Queue[front]->rchild!=NULL)

//将队首结点的右子结点入队列

{rear++;Queue[rear]=Queue[front]->rchild;}}}3二叉树遍历的非递归实现（*）⊕⊕⊕⊕⊕⊕⊕*******△△△△△△△ABDCEFG4二叉树遍历的应用（*）5由遍历序列恢复二叉树1).重构二叉树是遍历二叉树的逆运算

先序遍历的结果是：中序遍历的结果是：后序遍历的结果是：ABDE

CFDBEAFCDEB

FCA问题：如何根据遍历结果重构二叉树？

ABCDEF问题：若已知先序/后序遍历结果和中序遍历结果，

能否“恢复”出二叉树？答：由一棵二叉树的先序/后序序列和中序序列可唯一确定这棵二叉树。

5由遍历序列恢复二叉树1).重构二叉树是遍历二叉树的逆运算

用DLR(先序序列)+LDR(中序序列)

或LRD(后序序列)+LDR(中序序列)重构二叉树2)特点先序遍历序列(DLR)特点：<根>

<左子树上的所有结点><右子树上的所有结点>中序遍历序列(LDR)特点：<左子树上的所有结点>

<根><右子树上的所有结点>3)构造步骤：1)从DLR中找出第一个结点为二叉树的根，然后在LDR中找出根结点，根结点前面的结点序列就是左子树的LDR，根结点后面的结点序列就是右子树的LDR。2)对左子树的DLR和LDR及右子树的DLR和LDR，再执行第一步，直到找到所有的叶子结点。5由遍历序列恢复二叉树中序遍历：BDCEAFHG

后序遍历：DECBHGFA（BDCE）（FHG）ABF（DCE）（HG）CDEGHABBFF例：已知一棵二叉树的中序序列和后序序列分别是BDCEAFHG和DECBHGFA，请画出这棵二叉树。分析：①由后序遍历特征，根结点必在后序序列尾部（即A）；②由中序遍历特征，根结点必在其中间，而且其左部必全部是左子树子孙（即BDCE），其右部必全部是右子树子孙（即FHG）；③继而，根据后序中的DECB子树可确定B为A的左孩子，根据HGF子串可确定F为A的右孩子；以此类推。二叉树小结树二叉树森林1、定义和性质2、存储结构3、遍历顺序结构链式结构二叉链表三叉链表中序遍历后序遍历先序遍历层次遍历3.1.6树、森林和二叉树的转换树转换成二叉树森林转换成二叉树二叉树转换为森林方法：加线—抹线—旋转

abeidfhgc树转二叉树举例：abeidfhgc兄弟相连长兄为父孩子靠左根结点没有右子结点！转换步骤：step1:在树中所有兄弟结点之间加一连线;step2:只保留结点与最左子结点的连线，删除结点与其它子结点的连线；step3:以树根为轴心，顺时针旋转45度角。加线抹线旋转树