数据结构电子教案-深圳大学-自动化课件-ds

《数据结构电子教案-深圳大学-自动化课件-ds》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第五章树与二叉树数据结构电子教案殷人昆1第五章树与二叉树树和森林的概念二叉树二叉树遍历二叉树的计数线索化二叉树树与森林堆Huffman树2树和森林的概念两种树：自由树与有根树。自由树：一棵自由树Tf可定义为一个二元组Tf=(V,E)其中V={v1,...,vn}是由n(n＞0)个元素组成的有限非空集合，称为顶点集合。E={(vi,vj)

2、vi,vjV,1≤i,j≤n}是n-1个序对的集合，称为边集合，E中的元素(vi,vj）称为边或分支。3自由树有根树：一棵有根树T，简称为树，它是n(n≥0)个结点的有限集合。当n

3、=0时，T称为空树；否则，T是非空树，记作4r是一个特定的称为根(root)的结点，它只有直接后继，但没有直接前驱；根以外的其他结点划分为m(m0)个互不相交的有限集合T1,T2,…,Tm，每个集合又是一棵树，并且称之为根的子树。每棵子树的根结点有且仅有一个直接前驱，但可以有0个或多个直接后继。5树的基本术语子女：若结点的子树非空，结点子树的根即为该结点的子女。双亲：若结点有子女，该结点是子女双亲。1层2层4层3层depth=4DACBIJHGFEMLKheight=36兄弟：同一结点的子女互称为兄弟。度：结点的子

4、女个数即为该结点的度；树中各个结点的度的最大值称为树的度。分支结点：度不为0的结点即为分支结点，亦称为非终端结点。叶结点：度为0的结点即为叶结点，亦称为终端结点。祖先：某结点到根结点的路径上的各个结点都是该结点的祖先。子孙：某结点的所有下属结点，都是该结点的子孙。7结点的层次：规定根结点在第一层，其子女结点的层次等于它的层次加一。以下类推。深度：结点的深度即为结点的层次；离根最远结点的层次即为树的深度。1层2层4层3层depth=4DACBIJHGFEMLKheight=48高度：规定叶结点的高度为1，其双亲结点的高

5、度等于它的高度加一。树的高度：等于根结点的高度，即根结点所有子女高度的最大值加一。有序树：树中结点的各棵子树T0,T1,…是有次序的，即为有序树。无序树：树中结点的各棵子树之间的次序是不重要的，可以互相交换位置。森林：森林是m（m≥0）棵树的集合。9树的抽象数据类型templateclassTree{//对象:树是由n(≥0)个结点组成的有限集合。在//类界面中的position是树中结点的地址。在顺序//存储方式下是下标型,在链表存储方式下是指针//型。T是树结点中存放数据的类型,要求所有结//点的

6、数据类型都是一致的。public:Tree();~Tree();10BuildRoot(constT&value);//建立树的根结点positionFirstChild(positionp);//返回p第一个子女地址,无子女返回0positionNextSibling(positionp);//返回p下一兄弟地址,若无下一兄弟返回0positionParent(positionp);//返回p双亲结点地址,若p为根返回0TgetData(positionp);//返回结点p中存放的值boolInsertChild(

7、positionp,T&value);//在结点p下插入值为value的新子女,若插//入失败,函数返回false,否则返回true11boolDeleteChild(positionp,inti);//删除结点p的第i个子女及其全部子孙结//点,若删除失败,则返回false,否则返回truevoidDeleteSubTree(positiont);//删除以t为根结点的子树boolIsEmpty();//判树空否,若空则返回true,否则返回falsevoidTraversal(void(*visit)(posit

8、ionp));//遍历以p为根的子树};12二叉树的五种不同形态LLRR二叉树(BinaryTree)二叉树的定义一棵二叉树是结点的一个有限集合，该集合或者为空，或者是由一个根结点加上两棵分别称为左子树和右子树的、互不相交的二叉树组成。13二叉树的性质性质1若二叉树结点的层次从1开始,则在二叉树的第i层最多有2i-1个结点。(i≥1)[证明用数学归纳法]性质2深度为k的二叉树最少有k个结点，最多有2k-1个结点。(k≥1)因为每一层最少要有1个结点，因此，最少结点数为k。最多结点个数借助性质1：用求等比级数前k项和的

9、公式20+21+22+…+2k-1=2k-114性质3对任何一棵二叉树，如果其叶结点有n0个,度为2的非叶结点有n2个,则有n0＝n2＋1若设度为1的结点有n1个，总结点数为n，总边数为e，则根据二叉树的定义，n=n0+n1+n2e=2n2+n1=n-1因此，有2n2+n1=n0+n1+n2-1n2=n0-1n0=n2+115定义1满二叉树(F