资源描述：
《Windows程序设计-第2章算法与数据结构(2)》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、Windows程序设计第2章算法与数据结构(2)谢晓芹Topics检索Search快速排序Quicksort大O记法Big“Oh”VectorsListsTreesHashTablesSummary2Windows程序设计TreesAbinarytreeiseitherNULLorcontainsanodewithaleftandrightchildwhicharethemselvestrees.NodescontainvaluesInabinarysearchtree(BST)thevaluesintheleftchildaresmallerthanthevalueatthenodeandt
2、hevaluesintherightchildaregreaterthanthevalueatthenode.O(logn)expectedsearchandinsertiontimein-ordertraversalprovideselementsinsortedorder.3Windows程序设计Trees《数据结构》中的树的定义树是n个结点的有限集。在一棵非空树中(1)有且仅有一个特点的称为根的结点；(2)当n>1时，其余结点可分为m(m>0)个互不相交的有限集T1,T2,…,Tm,其中每一个集合本身又是一棵树，称为根的子树。形式化定义:Tree=(D,R)D是具有相同特性的数据元素的集
3、合；若D只含一个数据元素，则R为空集，否则R是D上某个二元关系H的集合，即R={H}.H为以下三种二元关系:(1)在D中存在唯一的根元素root,它在关系H下无前驱(2)若D-{root}!=ф,则存在D-{root}的一个划分D1,D2,…Dm,对于j!=k,有Dj∩Dk=ф,且对任意i,唯一存在数据元素xi∈Di,有(root,xi)∈H;(3)对应于D-{root}的划分，H-{(root,x1),…,(root,xm)}有唯一的一个划分H1,H2,…,Hm,对任意j!=k,有Hj∩Hk=ф,且对任意i,Hi是Di上的二元关系，(Di,{Hi})是一棵符合本定义的树，称为root的子树.
4、4Windows程序设计Trees树:一种分层性数据结构。在一棵树里存储着一组项.每个项保存一个值，它可以有指针指向0个或多个元素，但只能被另一个项所指。树根是其中惟一的例外，没有其他项的指针向它.树的应用语法树家族树文件系统目录结构5Windows程序设计6Windows程序设计Trees树的效率由于树的许多结点包含多个指向其他元素的指针，所以，很多在表或者数组结构中需要O(n)时间的操作，在树中只需要O(logn)时间。结点存在多个指针能减少为寻找一个结点所需要访问的结点个数，从而降低操作的复杂性。7Windows程序设计Trees二叉树:要么为空树;要么包含这样一个结点，其具有一个左孩子
5、和右孩子,左孩子和右孩子本身也是二叉树.二分检索树(binarysearchtree,BST):由结点中存储的值定义树的结构．对于一个特定节点,其左孩子的值比该节点的值小,其右孩子的值比该节点的值大.8Windows程序设计Trees－BinarySearchTreetypedefstructNamevalNameval;structNameval{char*name;intvalue;Nameval*left;/*lesser*/Nameval*right/*greater*/};“smiley”0x263A“zeta”0x03b6NULLNULL“smiley”0x263A“smiley”
6、0x263A“smiley”0x263A“Aacute”0x00c1“smiley”0x263A“Acirc”0x00c2NULLNULL“smiley”0x263A“AElig”0x00c6NULLNULL树结点定义注释指明链接性质9Windows程序设计Trees二分检索树的建构方式：在树里递归地向下，根据情况确定向左或向右，直到找到了链接新结点的正确位置。结点初始化为Nameval类型的对象，它包含一个名字、一个值和两个空指针。新结点总是作为叶子加进去的，它没有子结点。已知条件:结点,位置规则:值的大小,叶子结点10Windows程序设计Trees重复项的处理weprintf打印错误信息
7、，在输出信息的前面加上前缀词warning，不终止程序执行．11Windows程序设计Trees希望由树根到所有叶结点的最长距离与树全部结点个数成对数关系平衡二叉树定义（数据结构）或者是一棵空树，或者是具有下列性质的二叉树：其左右子树都是平衡树，且左右子树的深度之差的绝对值不超过１．在平衡树里做项检索是个O(logn)操作，因为不同可能性的数目在每一步减少一半，就像在二分检索中那样。特殊情况如果项
