《信息与通信树》PPT课件.ppt

《《信息与通信树》PPT课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第6章树6.1树的应用实例6.2树的基本概念和术语6.3二叉树6.4遍历二叉树6.5线索二叉树6.6二叉树、树和森林6.7树的应用6.8实习:二叉树的建立和遍历习题66.1树的应用实例例6.1如图6.1为某校计算机系领导结构图。例6.2家族树图6.1某校计算机系领导结构图图6.2家族树6.2树的基本概念和术语6.2.1树的定义树(Tree)是由一个或多个结点组成的有限集合T。其中：(1)有一个特定的结点称为该树的根(Root)结点；(2)除根结点之外的其余结点可分为m(m≥0)个互不相交的有限集合T1，T2，…，Tm，且其中每

2、一个集合本身又是一棵树，称之为根的子树(Subtree)。这是一个递归的定义，即在定义中又用到了树这个术语。它道出了树的固有特性。仅有一个根结点的树是最小树，树中结点较多时，每个结点都是某一棵子树的根。图6.3是一棵由9个结点组成的树T。其中A是根结点，其余结点分为三个互不相交的子集：T1={B,H,I}，T2={C}，T3={D,E,F,G}。T1、T2、T3都是树根A的子树，这三棵子树的根结点分别是B、C、D。每棵子树本身也是一棵树，可继续划分。例如子树T3以D为根结点，它的其余结点又可分为两个互不相交的子集：T31={E

3、}，T32={F，G}，而其中T31可以认为是仅有一个根结点的子树。图6.3树T6.2.2树的表示（1）树形图表示树形图表示是树结构的主要表示方法。   树的树形图表示中：结点用圆圈表示，结点的名字写在圆圈旁边（有时亦可写在圆圈内）。（2）树的其他表示法①嵌套集合表示法   　是用集合的包含关系来描述树结构。 上图(a)树的嵌套集合表示法如图(b)  ②凹入表表示法   　类似于书的目录，上图(a)树的凹入表示法如图(c)③广义表表示法   　用广义表的形式表示的。上图(a)树的广义表表示法如图(d)（A（B（E

4、，F（I，J）），C，D（G，H）））6.2.3树的常用术语1.结点的度和树的度树的结点包含一个数据元素及若干指向其子树的分支。结点拥有的子树数称为结点的度(Degree)。而树的度是指树中结点的度的最大值。如图6.3中，B结点有2个子树，则它的度为2。在树T中，A结点的度最大，值为3，也就是说，树T的度为3。2.分支结点和叶子结点称度不为0的结点为分支结点，也叫非终端结点。称度为0的结点为叶子(Leaf)或终端结点。如图6.3中，分支结点分别为A、B、D、F，而叶子结点分别为H、I、C、E、G。3.孩子、双亲、兄弟、子孙、祖

5、先结点的子树的根称为该结点的孩子(Child)，相应地，该结点称为孩子的双亲(Parent)。同一个双亲的孩子之间互称兄弟(Sibling)。如图6.3中，B、C、D分别是根结点A的子树的根，三个都是A的孩子，相应地，A是它们的双亲，其中，B、C、D三者是兄弟。一棵树上除根结点以外的其它结点称为根结点的子孙。对于树中某结点，从根结点开始到该结点的双亲是该结点的祖先。4.结点的层次和树的高度结点的层次(Level)从根结点开始定义，根为第一层，根结点的孩子为第二层，依次类推，其余结点的层次值为双亲结点层次值加1。树中结点的最大层

6、次值称为树的高度或深度(Depth)。如图6.3所示的树T高度为4。5.无序树、有序树、森林若树中结点的各子树看成从左至右是有次序的(即不能互换)，则称该树为有序树，否则称为无序树。在有序树中最左边的子树的根称为第一个孩子，最右边的称为最后一个孩子。森林(Forest)是m(m≥0)棵互不相交的树的集合。对树中每个结点而言，其子树的集合即为森林。6.3二叉树6.3.1二叉树的定义二叉树(BinaryTree)是n(n≥0)个结点的有限集合。它或为空树(n＝0)，或为非空树；对于非空树有：(1)有一个特定的称之为根的结点；(2)

7、根结点以外的其余结点分别由两棵互不相交的称之为左子树和右子树的二叉树组成。这个递归定义表明二叉树或为空，或是由一个根结点加上两棵分别称为左子树和右子树的互不相交的二叉树组成的。由于左、右子树也是二叉树，则由二叉树的定义，它们也可以为空。由此，二叉树可以有五种基本形态，如图6.5所示。图6.5二叉树的五种基本形态(a)空二叉树;(b)只有一个根结点;(c)有根结点和左子树;(d)有根结点和右子树;(e)有根结点和左、右子树有两种特殊形态的二叉树，它们是满二叉树和完全二叉树。满二叉树：深度为k且含有2k－1个结点的二叉树为满二叉树

8、，这种树的特点是每层上的结点数都是最大结点数，如图6.6(a)所示。对满二叉树的结点可以从根结点开始自上向下，自左至右顺序编号，图6.6(a)中每个结点边的数字即是该结点的编号。完全二叉树：深度为k，含有n个结点的二叉树，当且仅当每个结点的编号与相应满二叉树结点顺序号从1到n