Sun数据结构第6章树和二叉树(第12-18讲).ppt

树型结构是一类重要的非线性结构。树型结构是结点之间有分支，并且具有层次关系的结构，它非常类似于自然界中的树。树结构在客观世界中是大量存在的，例如家谱、行政组织机构都可用树形象地表示。;树型结构实例;树型结构实例; 6.1.2 树的定义和基本运算;对比树形结构和线性结构的结构特点;结点(node) 结点的度(degree) 树的度(degree) 分支(branch)结点 叶(leaf)结点 孩子结点、双亲结点 兄弟结点.堂兄弟结点; 1、 树形图表示法:逻辑结构描述直观 2． 嵌套集合表示法（文氏图表示法） 3． 凹入表示法 4． 广义表表示法 ;6.2 二叉树;二叉树的概念;A;二叉树的五种基本形态：;举 例;二叉树的性质;二叉树的性质;二叉树的性质;两类特殊的二叉树：;完全二叉树：树中所含的 n 个结点和满二叉树中编号为 1 至 n 的结点一一对应。;1;例：1、下图所示的4棵二叉树中，（ ）不是完全二叉树。;二叉树的性质;性质5：;A;1、由于二叉树中每个结点的度最大为2，所以二叉树是一种特殊的树。（ ） 2、深度为5的二叉树至多有（ ）个结点，至少（ ）个结点。 3、对一个满二叉树，m个树叶，n个结点，深度为h，则（ ）。 A、n=h+m B、h+m=2n C、m=h-1 D、n=2h-1 ;1．顺序存储结构 用一组地址连续的存储单元，以层序顺序存放二叉树的数据元素，结点的相对位置蕴含着结点之间的关系。;二叉树的顺序存储结构;A;二叉树的顺序存储结构;E;二叉树顺序存储结构仅适用于完全二叉树。 若存储非完全二叉树时有可能对存储空间造成极大的浪费：在最坏的情况下，一个深度为K且只有K个结点的右单支树需要2K-1个结点存储空间。 ;二叉树的链式存储结构;二叉树的链式存储结构;A;typedef char TElemType; typedef struct Node { TElemType data; struct Node *lchild, *rchild; } BiTNode, *BiTree;;A;6.3 二叉树的遍历;遍历二叉树;操作定义为：若二叉树为空，则空操作；否则 （1）访问根结点； （2）先序遍历左子树； （3）先序遍历右子树。;操作定义为：若二叉树为空，则空操作；否则 （1）中序遍历左子树； （2）访问根结点； （3）中序遍历右子树。;操作定义为：若二叉树为空，则空操作；否?? （1）后序遍历左子树； （2）后序遍历右子树； （3）访问根结点。;例如下图所示的二叉树表达式 (a+b*(c-d)-e/f) 若先序遍历此二叉树,按访问结点的先后次序将结点排列起来,其先序序列为： 按中序遍历,其中序序列为： 按后序遍历,其后序序列为： ;a b c d e f g;练习1:已知一棵二叉树的先序和中序序列分别如下，画出该二叉树。 先序序列：ABCDEFGHIJ 中序序列：CBEDAGHFJI;练习题;练习题举例;练习题举例;6.4 线索二叉树;先序：A B C D E F G H K;线索二叉树的结点结构是在原来结点的基础上增加标志域：;线索二叉树结点结构：;-;A;为操作方便，在线索二叉树中： 增设一个头结点， ltag=0、rtag=1，其lchild指向二叉树的根结点，rchild指向按某种次序遍历时访问的最后一个结点； 并将该结点作为遍历访问的第一个结点的前驱和最后一个结点的后继； 最后用头指针指示该头结点。;;练习题;复习;1．双亲存储表示法 用一组地址连续的存储单元来存放树的结点，每个结点有两个域： 　data域-----存放结点的信息；　　 　parent域-----存放该结点唯一的双亲结点的位置（数组下标）;树的双亲表示法示例;双亲表示法的存储结构描述为： #define MaxTreeSize 100 typedef char DataType； typedef struct{ DataType data； int parent； } PTreeNode； typedef struct {? PTreeNode nodes[MaxTreeSize]; int r,n；//根结点的位置和结点个数 }PTree； PTree T；;2、孩子表示法;孩子表示法的存储结构描述为： typedef struct Cnode { ??int child; ??struct CNode *next; } Cnode; /*孩子结点类型说明*/ typed