苏州大学数据结构05VIP免费

第五章树与二叉树数据结构电子教案殷人昆第五章树与二叉树树和森林的概念二叉树二叉树遍历二叉树的计数线索化二叉树树与森林堆Huffman树树和森林的概念两种树：自由树与有根树。自由树：一棵自由树Tf可定义为一个二元组Tf=(V,E)其中V={v1,...,vn}是由n(n＞0)个元素组成的有限非空集合，称为顶点集合。E={(vi,vj)|vi,vjV,1≤i,j≤n}是n-1个序对的集合，称为边集合，E中的元素(vi,vj）称为边或分支。自由树有根树：一棵有根树T，简称为树，它是n(n≥0)个结点的有限集合。当n=0时，T称为空树；否则，T是非空树，记作r是一个特定的称为根(root)的结点，它只有直接后继，但没有直接前驱；根以外的其他结点划分为m(m0)个互不相交的有限集合T1,T2,…,Tm，每个集合又是一棵树，并且称之为根的子树。每棵子树的根结点有且仅有一个直接前驱，但可以有0个或多个直接后继。00n,T,...,T,Tr,n,Tm21}{Φ树的基本术语子女：若结点的子树非空，结点子树的根即为该结点的子女。双亲：若结点有子女，该结点是子女双亲。1层2层4层3层depth=4DACBIJHGFEMLKheight=3兄弟：同一结点的子女互称为兄弟。度：结点的子女个数即为该结点的度；树中各个结点的度的最大值称为树的度。分支结点：度不为0的结点即为分支结点，亦称为非终端结点。叶结点：度为0的结点即为叶结点，亦称为终端结点。祖先：某结点到根结点的路径上的各个结点都是该结点的祖先。子孙：某结点的所有下属结点，都是该结点的子孙。结点的层次：规定根结点在第一层，其子女结点的层次等于它的层次加一。以下类推。深度：结点的深度即为结点的层次；离根最远结点的层次即为树的深度。1层2层4层3层depth=4DACBIJHGFEMLKheight=4高度：规定叶结点的高度为1，其双亲结点的高度等于它的高度加一。树的高度：等于根结点的高度，即根结点所有子女高度的最大值加一。有序树：树中结点的各棵子树T0,T1,…是有次序的，即为有序树。无序树：树中结点的各棵子树之间的次序是不重要的，可以互相交换位置。森林：森林是m（m≥0）棵树的集合。树的抽象数据类型templateclassTree{//对象:树是由n(≥0)个结点组成的有限集合。在//类界面中的position是树中结点的地址。在顺序//存储方式下是下标型,在链表存储方式下是指针//型。T是树结点中存放数据的类型,要求所有结//点的数据类型都是一致的。public:Tree();~Tree();BuildRoot(constT&value);//建立树的根结点positionFirstChild(positionp);//返回p第一个子女地址,无子女返回0positionNextSibling(positionp);//返回p下一兄弟地址,若无下一兄弟返回0positionParent(positionp);//返回p双亲结点地址,若p为根返回0TgetData(positionp);//返回结点p中存放的值boolInsertChild(positionp,T&value);//在结点p下插入值为value的新子女,若插//入失败,函数返回false,否则返回trueboolDeleteChild(positionp,inti);//删除结点p的第i个子女及其全部子孙结//点,若删除失败,则返回false,否则返回truevoidDeleteSubTree(positiont);//删除以t为根结点的子树boolIsEmpty();//判树空否,若空则返回true,否则返回falsevoidTraversal(void(*visit)(positionp));//遍历以p为根的子树};二叉树的五种不同形态二叉树的五种不同形态LLRR二叉树(BinaryTree)二叉树的定义一棵二叉树是结点的一个有限集合，该集合或者为空，或者是由一个根结点加上两棵分别称为左子树和右子树的、互不相交的二叉树组成。二叉树的性质性质1若二叉树结点的层次从1开始,则在二叉树的第i层最多有2i-1个结点。(i≥1)[证明用数学归纳法]性质2深度为k的二叉树最少有k个结点，最多有2k-1个结点。(k≥1)因为每一层最少要有1个结点，因此，最少结点数为k。最多结点个数借助性质1：用求等比级数前k项和的公式20+21+22+…+2k-1=2k-1性质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+1定义1满二叉树(...