第6章-树二叉树(简化).ppt

《第6章-树二叉树(简化).ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第六章树和二叉树本章主要内容一、树的基本概念二、二叉树三、二叉树的遍历6.1树的基本概念1.定义：是一种常非线性结构树是n（n≥0）个结点的有限集合。若n=0，则称为空树；否则，有且仅有一个特定的结点被称为根，当n>1时，其余结点被分成m（m>0）个互不相交的子集T1，T2，...，Tm，每个子集又是一棵树。递归定义的树的几种形态2.树的特点（1）树的根结点没有前驱结点，除根结点之外的所有结点有且只有一个前驱结点（2）树中所有结点可以有零个或多个后继结点3.树的相关概念1)结点数据元素的内容及其指向其

2、子树根的分支统称为结点2)结点的度结点的分支数。3)终端结点（叶子）度为0的结点。4)非终端结点度不为0的结点。5)结点的层次树中根结点的层次为1，根结点子树的根为第2层，以此类推。6)树的度树中所有结点度的最大值。7)树的深度树中所有结点层次的最大值。8)有序树、无序树如果树中每棵子树从左向右的排列拥有一定的顺序，不得互换，则称为有序树，否则称为无序树。9)森林是m（m≥0）棵互不相交的树的集合。在树结构中，结点之间的关系又可以用家族关系描述，定义如下：10)孩子、双亲结点子树的根称为这个结点的孩子

3、，而这个结点又被称为孩子的双亲。11)子孙以某结点为根的子树中的所有结点都被称为是该结点的子孙。12)祖先从根结点到该结点路径上的所有结点。13)兄弟同一个双亲的孩子之间互为兄弟。14)堂兄弟双亲在同一层的结点互为堂兄弟。4.树的表示法直观表示法嵌套集合表示法凹入表示法//不清晰广义表表示法(1)(2)(3)(4)返回6.2二叉树1.定义：叉树是n（n≥0）个结点的有限集合。当n=0时，称为空二叉树；当n>0时，有且仅有一个结点为二叉树的根，其余结点被分成两个互不相交的子集，一个称为左子集，另一个称为

4、右子集，每个子集又是一个二叉树递归定义的2.二叉树的五种形态例3.二叉树的性质在二叉树的第i层上最多有2i-1个结点（i≥1）深度为K的二叉树最多有2K-1个结点（K≥1）对于任意一棵二叉树BT，如果度为0的结点个数为n0，度为2的结点个数为n2，则n0=n2+1二叉树的总度数＝n1+2n2二叉树的节点数＝n0＋n1＋n2二叉树的总度数＝二叉树的节点数－1n1+2n2=n0＋n1＋n2-1即：n0=n2+14.二叉树的存储顺序存储结构链式存储结构通常二叉树可以用下面两种方式存储：下页介绍(1)顺序存储

5、结构适用完全二叉树，用一组连续的存储单元按照完全二叉树的每个结点编号的顺序存放结点内容如下图所示：下页给出C实现(2)链式存储结构注：Lchild和Rchild是分别指向该结点左孩子和右孩子的指针下页C实现6.3二叉树的遍历定义：按照一定规则访问二叉树的所有节点一次先序遍历TLR、中序遍历LTR和后序遍历LRT层次遍历下页分述TLR(1)先序遍历TLR若二叉树为空，则结束遍历操作；否则访问根结点；先序遍历根的左子树；先序遍历根的右子树递归算法，思考它所对应的非递归算法先看遍历的结果下页C实现（2）中序

6、遍历和后序遍历算法中序遍历若二叉树为空，则结束遍历操作；否则先访问左子树，然后是根结点，最后遍历右子树。后序遍历若二叉树为空，则结束遍历操作；否则先访问左子树，然后遍历右子树，最后是根结点。三种访问序列的结果（4）层次遍历二叉树定义：按照树深度的次序从左到右依次访问二叉树的所有节点下页给出C实现