[工学]数据结构——树.ppt

树的概念 树的存储 树的遍历 树的应用 二叉树的概念及性质 二叉树的运算及遍历 二叉树的应用 树、森林与二叉树的转换;5.1 树的概念; 除根以外的其它结点划分为m (m ? 0)个互不相交的有限集合T0, T1, …, Tm-1，每个集合又是一棵树，并且称之为根的子树(SubTree)。 每棵子树的根结点有且仅有一个直接前驱，但可以有0个或多个直接后继。;特点：; 树型表示;形式化表示;凹入表表示;嵌套集合表示;结点(node) 数据元素。 结点的度(degree) 结点的子树个数。 树的度(degree) 树中所有结点度的最大值。 分支(branch)结点 度不为0的结点。 叶(leaf)结点 度为0的结点。 孩子(child)结点 某结点子树的根结点。 双亲(parent)结点 某个结点是其子树之根的双亲。 ;兄弟(sibling)结点 具有同一双亲的所有结点 结点所处层次(level) 根结点的层数为1，其余结点的层数为双亲结点的层数加1 树的深度(depth) 树中结点的最大层数 有序树 子树的次序不能互换 无序树 子树的次序可以互换 森林 互不相交的树的集合;? (a);A; 数据对象D：一个集合，该集合中的所有元素具有相同的特性。 数据关系R：若D为空集，则为空树。若D中仅含有一个数据元素，则R为空集，否则R={H}，H是如下的二元关系： (1) 在D中存在唯一的称为根的数据元素root，它在关系H下没有前驱。  (2) 除root以外，D中每个结点在关系H下都有且仅有一个前驱。 ;树的基本操作;5.2 树的存储结构;注意：-1：该结点无双亲结点，该结点为根结点;#define MAXNODE 32 typedef struct { DataType data; \\ 数据域 int parent; \\ 双亲域 } ptree; ptree t[MAXNODE ]; ;改进：;(1).孩子链表示;A;(2)双亲-孩子表示;typedef struct cnode { int child; \\ 孩子结点序号 struct cnode *next; \\ 下一个孩子结点 } link;;(3)左孩子-右兄弟表示法;孩子兄弟表示—C语言描述;5.3 树的遍历;若树非空，则 (1)、依次后序遍历树的各子树 (2)、访问根结点; 按层次顺序（1,2,…）遍历，同一层按从左到右的顺序。;5.4 树的应用;5.5 二叉树 (Binary Tree);二叉树的五种不同形态;8;若二叉树的深度为h，且共有n个结点。对树中结点按从上到下、从左到右的顺序进行编号，若编号为i(1≤i≤n)的结点与满二叉树编号为i的结点位置相同，则此树称为完全二叉树。;显然，一颗满二叉树一定是一颗完全二叉树;(3) 平衡二叉树;性质1 若二叉树的层次从1开始, 则在二叉树的 第 i 层最多有 2i-1 个结点。(i ?1);性质2 高度为h的二叉树最多有 2h-1个结点。 (h? 1);性质3 对任何一棵二叉树, 如果其叶结点个数为 n0, 度为2的非叶结点个数为 n2, 则有 n0＝n2＋1;性质4 具有n个结点的完全二叉树的高度 为 ? log2n ? +1;性质5：具有n个结点的满二叉树， h=log2(n+1)从第一层开始,自上而下逐层从左到右给每个结点编号i,规律有: ①若i≤2h-1-1,结点i的左孩子结点编号为2*i,右孩子结点编号为2*i+1; ②若i1,则结点i的双亲结点的编号为? i/2?. 可见,可以对其采用顺序存贮结构.;性质6 如果将一棵有n个结点的完全二叉树自顶向下，同一层自左向右连续给结点编号1, 2, …, n-1,n，然后按此结点编号将树中各结点顺序地存放于一个一维数组中, 并简称编号为i的结点为结点i (1 ? i ? n)。则有以下关系： ;1;完全二叉树的顺序存储;一般二叉树的顺序存储; 单支树;顺序二叉树结点的描述;链表存储表示;A;二叉树三叉链表表示的示例;三叉链表的静态结构;typedef int DataType; typedef struct node { DataType data; struct node *Lch