第5讲+树与二叉树

《第5讲+树与二叉树》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、Chapter5Tree&BinaryTree树的类型定义n(n≥0)个元素的有限集合数据对象D：D是具有相同特性的数据元素的集合。若D为空集，则称为空树。否则:(1)在D中存在唯一的称为根的数据元素root；(2)当n>1时，其余结点可分为m(m>0)个互不相交的有限集T1,T2,…,Tm，其中每一棵子集本身又是一棵符合本定义的树，称为根root的子树。数据关系R：树的类型定义基本术语结点结点的度树的度叶子结点分支结点数据元素+若干指向子树的分支分支的个数树中所有结点的度的最大值度为零的结点度大于零的结点DHIJM(从根到结点的)路径孩子结点、双亲结点兄弟结

2、点、堂兄弟结点祖先结点、子孙结点由从根到该结点所经分支和结点构成ABCDEFGHIJMKL结点的层次树的深度ABCDEFGHIJMKL假设根结点的层次为1，第l层的结点的子树根结点的层次为l+1树中叶子结点所在的最大层次任何一棵非空树是一个二元组Tree=（root，F）其中root被称为根结点F被称为子树森林森林是m（m≥0）棵互不相交的树的集合ArootBCDEFGHIJMKLF(１)有确定的根(２)树根和子树根之间为有向关系有向树有序树子树之间存在确定的次序关系无序树子树之间不存在确定的次序关系对比树型结构和线性结构的结构特点~~~~~~~~~~~~~~~~

3、~~~~~~~~~~~~~~线性结构树型结构第一个数据元素(无前驱)根结点(无前驱)最后一个数据元素(无后继)多个叶子结点(无后继)其它数据元素(一个前驱、一个后继)其它数据元素(一个前驱、多个后继)基本操作：查找类插入类删除类Root(T)//求树的根结点查找类：Value(T,cur_e)//求当前结点的元素值Parent(T,cur_e)//求当前结点的双亲结点LeftChild(T,cur_e)//求当前结点的最左孩子RightSibling(T,cur_e)//求当前结点的右兄弟TreeEmpty(T)//判定树是否为空树TreeDepth(T)//求树

4、的深度TraverseTree(T,Visit())//遍历InitTree(&T)//初始化置空树插入类：CreateTree(&T,definition)//按定义构造树Assign(T,cur_e,value)//给当前结点赋值InsertChild(&T,&p,i,c)//将以c为根的树插入为结点p的第i棵子树ClearTree(&T)//将树清空删除类：DestroyTree(&T)//销毁树的结构DeleteChild(&T,&p,i)//删除结点p的第i棵子树二叉树的类型定义二叉树或为空树，或是由一个根结点加上两棵分别称为左子树和右子树的、互不交叉的

5、二叉树组成ABCDEFGHK根结点左子树右子树二叉树的五种基本形态N空树只含根结点NNNLRR右子树为空树L左子树为空树左右子树均不为空树二叉树的主要基本操作查找类插入类删除类Root(T)Value(T,e)Parent(T,e)LeftChild(T,e)RightChild(T,e)LeftSibling(T,e)RightSibling(T,e)BiTreeEmpty(T)BiTreeDepth(T)查找类PreOrderTraverse(T,Visit())InOrderTraverse(T,Visit())PostOrderTraverse(T,Vis

6、it())LevelOrderTraverse(T,Visit())InitBiTree(&T)Assign(T,&e,value)CreateBiTree(&T,definition)InsertChild(T,p,LR,c)插入类ClearBiTree(&T)DestroyBiTree(&T)DeleteChild(T,p,LR)删除类二叉树的重要特性性质1：在二叉树的第i层上至多有2i-1个结点。(i≥1)用归纳法证明：归纳基：归纳假设：归纳证明：i=1层时，只有一个根结点：2i-1=20=1；假设对所有的j，1≤ji，命题成立；二叉树上每个结点至多有两

7、棵子树，则第i层的结点数≤2i-22=2i-1。性质2：深度为k的二叉树上至多含2k-1个结点（k≥1）。证明：基于上一条性质，深度为k的二叉树上的结点数至多为20+21++2k-1=2k-1。性质3：对任何一棵二叉树，若它含有n0个叶子结点、n2个度为2的结点，则必存在关系式：n0=n2+1。证明：设二叉树上结点总数n=n0+n1+n2又二叉树上分支总数b=n1+2n2而b=n-1=n0+n1+n2-1由此，n0=n2+1。两类特殊的二叉树：满二叉树：指的是深度为k且含有2k-1个结点的二叉树。完全二叉树：树中所含的n个结点和满二叉树中编号为1至n

8、的结点一一