第6章 树和二叉树-4.5.ppt

数据结构 第6章 树和二叉树 6.1 树的定义和术语 6.1.1 树的定义 1. 树的定义 树（Tree）是n（n≥0）个节点的有限集合T，当n=0时称为空树，否则，称为非空树。 在任一棵非空树中： （1）有且仅有一个称为树根（root）的节点。 （2）除根节点之外的其余节点可分为m（m≥0）个互不相交的集合T1，T2，…，Tm，其中每一个集合本身又都是一棵树，一般称为根的子树（subtree）。 树的定义是一个递归的定义，它反映了树的固有特性，即一棵树由若干棵子树构成，且各子树间互不相交，而每棵子树又由若干棵更小的子树构成。 2. 树的其他表示法 树结构可以用不同的形式来表示，常用的表示形式有4种（以图6.1(b)树为例）： 树形表示法，如图6.1(b)所示。 嵌套集合表示法，如图6.2(a)所示。 凹入表表示法，如图6.2(b)所示。 广义表表示法，如图6.2(c)所示。 6.1.2 基本术语 节点(node) ：表示树中的元素，包含一个数据和若干指向其子树的分支。 节点的度(degree)：一个节点的子树个数称为此节点的度。 叶结点(leaf)：度为0的节点，即无后继的节点，也称为终端结点。 分支节点：度不为0的节点，也称为非终端节点。 孩子节点(child)：一个节点的直接后继称为该节点的孩子节点。 双亲节点(parents)：一个节点的直接前驱称为该节点的双亲节点。 兄弟节点(sibling)：同一双亲节点的孩子节点之间互称兄弟节点。 祖先节点：一个节点的祖先结点是指从根节点到该节点的路径上的所有节点。 子孙节点：一个节点的直接后继和间接后继称为该节点的子孙节点。 树的度：树中所有节点的度的最大值。 节点的层次：从根节点开始定义，根节点的层次为1，根的直接后继的层次为2，依此类推。 树的高度(深度)(depth)：树中所有节点的层次的最大值。 有序树和无序树：如果将树中节点的各子树看成从左至右是有次序的，则称该树为有序树，否则称为无序树。 森林(forest)：m(m≥0)棵互不相交的树的集合。 将一棵非空树的根节点删去，树就变成一个森林； 反之，给森林增加一个统一的根节点，森林就变成一棵树。 6.1.3 树的存储 在许多具体应用中，可以采用多种形式的存储结构表示树； 常用的树的存储结构有四种： 双亲表示法； 孩子链表表示法； 带双亲的孩子链表表示法； 孩子兄弟表示法(二叉链表表示法)。 1. 双亲表示法 双亲表示法利用树中每个节点的双亲唯一性，在存储节点信息的同时，为每个节点附设一个指向其双亲的指针parent，唯一地表示任何一棵树。 实现方法：用一组连续的存储空间来存储树中的节点。数组元素为结构体类型。 每个节点含数据域和双亲域两个域： 数据域中存放节点本身信息； 双亲域指示本节点的双亲结点在数组中的位置。 用C语言定义的存储结构如下： typedef struct node { datatype data; //数据域中存放节点本身信息 int parent; //双亲域指示本结点的双亲结点在数组中的位置 }Node Node t[m]; 分析 优点：用双亲表示法来表示树节点之间的关系，很容易找到每一个节点（根节点除外）的双亲。 缺点：但是谁是该节点的孩子，如何才能找到该节点的孩子，用这种表示法却较难实现，也就是说双亲表示法找双亲容易，找孩子困难。 2. 孩子链表表示法 每个节点的孩子节点用单链表存储，再用含n个元素的结构体数组指向每个孩子链表。 孩子表示法的存储结构包括两个部分： 一部分是表头数组，表头数组中的元素是结构体数据，由一个数据域（结点数据，假设数据类型为datatype）和一个指针域（指向节点的第一个孩子）构成； 另一部分是孩子单链表，每个链表节点由一个整型数据（用来存放表头数组元素的下标）和一个指针域（指向下一个孩子）构成。 一部分是表头数组，表头数组中的元素是结构体数据： 一个数据域（结点数据，假设数据类型为datatype） 一个指针域（指向节点的第一个孩子） 另一部分是孩子单链表，每个链表节点由 一个整型数据（用来存放表头数组元素的下标） 一个指针域（指向下一个孩子）构成。 用C语言定义的存储结构如下： (1) 孩子节点的存储结构 typedef struct node { int child; //该孩子节点在表头数组中的下标 struct node *next; //指向下一个孩子节点 }Node; 用C语言定义的存储结构如下： (2) 表头结点的存储结构 #define M 100 //定义表头数组最大存储容量 typedef struct tnode { Datatype data;