数据结构(C 语言版)6.pptVIP

6.1树的定义和基本术语 1.树（Tree）： n个结点的有限集。 非空树的特点： ⑴有且仅有一个特定的根结点； ⑵当n1，有m被称为根的子树的结点个互不相交,并且每一个子树也是 有限集。 树的示例： ①只有根节点的树 ②含有子树的树 T1={B,E,F} T2={C,G} T3={D} 2.树的抽象数据类型定义 ADT Tree{ 数据对象D：D具有相同特性的数据元素集合 数据关系R：若D为空集，则称为空树； 若D仅含一个数据元素，则R为空集，否则 R={H},H是如下二元关系： ⑴D中只有元素root,则H无前驱； ⑵若D-{root} ≠Φ,则存在一个互不相交划分D1,D2…Dn, 唯一存在数据元素xi∈Di,有root, xi ∈H; ⑶对应于D-{root}的划分,H-{root, xi …,root, xn}有 唯一的一个划分H1,H2…Hn,对于任意j ≠k有Hj∩Hk= Φ 任意i，Hi是Di上的二元关系，(Di,{Hi})是一棵符合本定义的 树，称为根root的子树。 基本操作： …. 3.树的逻辑表示方法 ⑴树形表示法 ⑵文氏图表示法 ⑶凹入表示法 ⑷括号表示法 4.树的基本术语 ⑴结点的度与树的度 结点包含的子树个数称为结点的度，树中各 结点度最大的值为数的度。 ⑵分支结点和叶子结点 度为0的结点称为叶子结点，度不为0的称为 分支结点。 ⑶路径与路径长度 对于任意两个结点Ki和Kj,存在一个系列 Ki,Ki1,….Kin,Kj;除Ki外每一个结点都是其前 一个结点的后继，则称Ki到Kj是一条路径，路径长 度就是路径经过的结点数减1 ⑷孩子结点，双亲结点和兄弟结点 在一棵树中，每个结点的后继被称为该结点 的孩子结点，相应的该结点被称为孩子结点 的双亲结点。具有同一双亲的孩子结点互称 为兄弟结点。把每个结点所有子树中的结点 称为该结点的子孙结点，从树根结点到达该 结点的路径上经过的所有结点被称为该结点 的祖先结点。 ⑸结点的层次和数的高度 结点处在一定的层次上，它的层次为其双亲 结点所在的层次加1，根结点为第一层，树中结点 最大的层称为树的高度。 ⑹有序树和无序树 若树中各个结点的子树是按照一定的次序从 左向右安排的，且相对次序是不能随意变换 的，则称为有序树，否则为无序树。 ⑺森林 n个互相不相交的树的集合称为森林。森林和 树的概念十分相近，只要把树的根结点删除 树就成了森林，反之把n个独立的树加上一个 结点，把该结点作为root，则森林就变成树。 6.2 二叉树 6.2.1二叉树的定义 二叉树是树的一种特殊类型，特点是每个结 点至多有两棵子树，并且二叉树的子树有左 右之分，次序不能任意颠倒。 抽象数据类型定义： ATD BinaryTree { ……. } 二叉树的抽象数据类型定义类似于树 二叉树的五种基本形态： ⑴空二叉树 ⑵仅有根结点的二叉树 ⑶右子树为空的二叉树 ⑷左右子树均为非空的二叉树 ⑸左子树为空的二叉树 6.2.2 二叉树的性质 性质1 在二叉树的第i层上至多有2i-1个结点 性质2 深度为k的二叉树至多有2k-1个结点 性质3 对于任一棵二叉树如果终端结点数为 n0,度为2的结点数为n2则n0= n2 +1 性质4 具有n个结点的完全二叉树的深度为 [log2n]+1 性质5 有n个结点的完全二叉树按层编号，则 对于任一结点i有 ⑴如果i=1，则结点i是二叉树的根，无双亲 如果i1,其双亲是结点[i/2] ⑵如果2in,则结点i无左孩子；否则其左孩子 是结点2i ⑶如果2i+1n,则结点无右孩子，否则其右孩 子是结点2i+1 6.2.3二叉树的存储结构 1.顺序存储结构 这种存储只适用于完全二叉树，因为只有完 全二叉树的结点标号可以和顺序存储单元的 标号顺序对应，其定义如下： typedef ElemType SqBiTree[SIZE]; SqBiTree bt; 2.链式存储结构 根据二叉树定义，其一个结点包括一个数据 元素，分别指向其左，右子树的两个分支构 成，所以二叉树的链表中至少包含三个域， 数据域，左右指针域： 为了便于找到结点的双亲，还可以增加一个 指向结点双亲的指针 二叉树二叉链表存储表示定义： typedef struct BiTNode { TElemType data; struct BiTNode *lchild,*rchild; } BiTNode，* BiTree