第六讲 树状结构.ppt

第6章 树状结构 树状结构 树状结构的一些专有名词 二叉树结构 二叉树的表示方法 二叉树的遍历 线索二叉树 如何将一般树化为二叉树和确定惟一的二叉树 树状结构的一些专有名词1 利用图6-1来说明树的一些专有名词。 树状结构的一些专有名词2 节点与边： - 节点代表某项数据，而边是指由一节点到另一节点的分支。 - 如图6-1中有14个节点，其节点的数据是英文字母。 祖先（ancestor）节点与子孙（descendant）节点： - 若从节点X有一条路径通往节点Y，则X是Y的祖先，Y是X的子孙 - 图6-1中，节点A可通往K，故称A是K的祖先，而K是A的子孙。 父节点（parent node）与子节点（children node）： - 若节点X直接到节点Y，则称X为Y的父节点，Y为X的子节点。 - 图6-1中，A为B、C、D的父节点，B、C、D为A的子节点。 树状结构的一些专有名词3 兄弟节点（sibling node）： - 同父节点的子节点。图6-1中，B、C、D为兄弟节点。 非终端节点（non-terminal node）： - 有子节点的节点。 - 图6-1中，除了J、K、L、G、M、N、I外，其余的节点皆为非 终端节点。 终端节点（terminal node）或叶节点（leaf node）： - 没有子节点的节点称为终端节点. - 图6-1中，J、K、L、G、M、N、I皆为叶节点。 树状结构的一些专有名词4 度（degree）： - 一个节点的度是它拥有的子节点数。 树的度： - 是指一个节点所拥有的最大度。 层次（level）： - 树中节点世代的关系，一代为一个层次，树根的层次为1。 森林（forest）： - 是由n个（n≥0）互不相交的树（disjoint trees）所组合 而成的，若移去树根将形成森林。 树状结构的一些专有名词5 树的其他表示方法 二叉树结构1 二叉树结构2 二叉树和一般树的区别 二叉树的特点 二叉树的表示方法1 二叉树的表示方法2 二叉树的遍历 中序遍历的算法 前序遍历的算法 后序遍历的算法 中序遍历的非递归的程序段 中序遍历的非递归的程序段（续） 线索二叉树 二叉树转化成线索二叉树 线索二叉树完全表示法 线索二叉树的优点 线索二叉树的优点 线索二叉树的优点 如何将一般树化为二叉树 一般树化为二叉树（示意图） 森林换为二叉树（示意图） 确定惟一的二叉树 6.* ? 2006 * 21世纪高等院校规划教材 返回总目录 图6-1 树的表示法 高度（height）： - 树中某节点的高度表示此节点至叶节点的最长路径（Path） 长度。 - 如图6-1的A节点高度为3，C节点的高度为1。 树的高度： - 为此棵树的根结点到最深层叶节点的路径长度。 - 如图6-1中，此棵树的高度为3。 深度（depth）： - 某个节点的深度为树根至此节点的路径长度。 - 如图6-1的C节点其深度为1，而M、N节点深度为3，同理E节 点深度为2，而A的深度为0。 树的其他表示方法： 亦可以（A（B（E（J），F（K，L）），C（G），D（H （M,N）,I））来表示，如节点D有两个子节点，分别是H、I；而 节点H又有两个子节点M、N。节点C有一子节点G。节点B有2个子 节点E和F，节点E有1个子点点J。最后节点A有3个子节点B、C、 D。 节点的数据结构： 二叉树是经常出现而且非常重要的一种树状结构。 二叉树的定义： （1）是由节点所组成的有限集合。 （2）这个集合可以是空集合。 （3）还可以是由树根、左子树（left subtree）和右子 树（right subtree）所组成的集合。 空集合的二叉树，如下图所示。其中a的右子树是空集合，b的左 子树是空集合。 a b 满二叉树： 有一棵层次等于k的二叉树，若含有2k-1个节点数时，则称为满二叉树 （fully binary tree）。 完全二叉树： 若含有的节点数少于2k-1，而且节点排列的顺序同满二叉树，则称之为 完全二叉树（complete binary tree）。 二叉树和一般树的区别： 1．二叉