第五章 树.pptVIP

第五章 树 [内容提要] 二叉树的定义、性质和存储结构； 二叉树的遍历和线索化； 树的定义和存储结构； 树、森林与二叉树转换； 树和森林的遍历以及树的应用。 树的定义及特点 定义： 树是由n（n≥0）个结点组成的有限集合，当n＝0时称为空树，否则，在任一非空树中： １）必有一个特定的称为根的结点； ２）当n1时，其余结点可分为m(m0)个互不相交的有限集T1,T2,……Tm，其中每一个集合本身又是一棵树，称为根的子树。 树的表示法 树的基本术语 结点——表示树中的元素，包括数据项及若干指向其子树的分支 结点的度——结点拥有的子树数 叶子——度为0的结点，也叫终端结点 分支结点——度不为0的结点，也叫非终端结点 内部结点——除根结点之外，分支结点也称为内部结点 树的基本术语 树的度——一棵树中最大的结点度数 孩子——结点子树的根称为该结点的孩子 双亲——孩子结点的上层结点叫该结点的双亲 兄弟——同一双亲的孩子之间互成为兄弟 祖先——结点的祖先是从根到该结点所经分支上的所有结点 子孙——以某结点为根的子树中的任一结点都成为该结点的子孙 树的基本术语 结点的层次——从根结点算起，根为第一层，它的孩子为第二层…… 堂兄弟——其双亲在同一层的结点互称为堂兄弟。 深度——树中结点的最大层次数 有序树—— 如果将树中结点的各子树看成从左至右是有次序的（即不能互换），则称该树为有序树，否则称为无序树。在有序树中最左边的子树的根称为第一个孩子，最右边的称为最后一个孩子。 森林——m(m?0)棵互不相交的树的集合 树的基本操作 ⑴初始化操作 INITATE(T)。置T为空树； ⑵求根函数 ROOT(T)或ROOT(x)。求树T的根或求结点X所在的树的根结点。若T是空或X不在任何一棵树上，则函数值为“空”； 树的基本操作（续） ⑸求右兄弟函数 RIGHT_SIBLING(T,x)。求树T中结点x右边的兄弟，若结点x是其双亲的最右边的孩子结点或结点x不在树T中，则函数值为“空”； ⑹建树函数 CRT_TREE(x,F)。生成一颗以x结点为根，以森林F为子树森林的树； ⑺插入子树操作 INS_CHILD(y,i,x)。置以结点x为根的树为结点y的第i棵子树，若原树中无结点y或结点y的子树个数小于i-1，则空操作； 二叉树的定义及特点 定义： 二叉树是结点的有限集合，这个集合或者是空的，或者由一个根结点或两棵互不相交的称为左子树的和右子树的二叉树组成。 二叉树的五种基本形态 满二叉树 定义： 一颗深度为k的满二叉树，是由２k －１个结点的深度为K的二叉树。２k -１个结点是二叉树所具有的最大结点个数。 为从第一层的结点（即根）便于访问满二叉树的结点，对满二叉树开始，自上而下，从左到右，按顺序给结点编号，便得到满二叉树的一个顺序表。 完全二叉树 定义：一颗具有n个结点、深度为K的二叉树，当且仅当其所有结点对应于深度为k的满二叉树中编号由1到n的那些结点时，该二叉树便是完全二叉树。 二叉树的基本操作 ⑴初始化操作 INITIATE(BT)：置BT为空树； ⑵求根函数 ROOT(BT) 或 ROOT(x)：求二叉树BT的根结点或求结点x所在二叉树的根结点，若BT是空树或x不在任何二叉树上，则函数值为“空”； 二叉树的基本操作 ⑸求兄弟函数 LSIBLING(BT,x)和RSIBLING(BT,x)：分别求二叉树BT中结点x的左兄弟和右兄弟结点，若结点x是根结点或不在BT中或是其双亲的左/右子树根，则函数值为“空”； ⑹建树操作 CRT_BT(x,LBT,RBT)：生成一棵以结点x为根、二叉树LBT和RBT为左、右子树的二叉树； 二叉树的基本操作 ⑼遍历操作 TRAVERSE(BT)：按某个次序依次访问二叉树中各个结点，并使每个结点只被访问一次； ⑽清除结构操作 CLEAR(BT)：将二叉树BT置为空树。 二叉树的性质： 性质5.1 在二叉树第i层上至多有２i-1 个结点（i≥1）。 性质5.2 深度为k的二叉树至多有 ２k -1个结点（k≥1）。 二叉树的性质： 性质5.3 对任何一颗二叉树T如果其终端结点数为n0 ，度为2的结点数为n2 , 则n0 = n2 +1。 性质5.4 具有n个结点的完全二叉树的深度为 ?log2 n」+1。 二叉树的性质： 性质5.5 如果对一棵有n个结点的完全二叉树的结点按层序号编号（从第1层到?log2 n? +1层，每层从左到右），则对任一结点i（1≤i≤n），有： ⑴ 如果i=1，则结点i是根结点，否则结点i的父结点为结点 ?i/2? 。 ⑵ 如果2in，则结点i无左孩子（结点i为叶子结点）；否则其左孩子LCHILD(i)是结点2